리스트 List

: 크기를 동적으로 변경할 수 있는 선형 자료구조

순차 리스트 ArrayList

: 인덱스로 객체를 관리하고, 동적으로 크기를 할당하는 "동적 배열"

• 특징

  • 연속된 메모리 공간 할당 → 인덱스로 접근 시 빠름
  • 설정한 저장용량을 넘어 더 많은 객체가 입력되면 배열의 크기를 증가시킴
  • 객체가 삽입, 삭제될 때마다 데이터 이동

  → 물리적인 메모리 순서를 맞추기 위한 작업으로,
    시간과 메모리 측면에서 비효율적

  → 조회, 검색이 많은 경우 사용

public class LinkedList_Sequantial {
	private String[] arr;
	private String[] prevArr;
	private int size;
	
	public LinkedList_Sequantial() {
		this.arr = new String[10];
		this.size = 0;
	}
	
	// 조회
	public String get(int idx) {
		if(idx < 0 || idx >= size) return null;
		return arr[idx];
	}
	
	// 첫번째 삽입
	public void addFirst(String data) {
		// 꽉 찼다면 더 큰 배열 새로 생성
		if(size == arr.length) {
			this.prevArr = this.arr;
			this.arr = new String[size + 10];
			// 뒤에서부터 하나씩 밀어내면서 자료 옮기기
			for(int i = size - 1 ; i >= 0; i--) {
				arr[i+1] = prevArr[i];
			}
		} else {
			// 뒤에서부터 하나씩 밀어내고 자료 옮기기
			for(int i = size-1 ; i >= 0; i--) {
				arr[i+1] = arr[i];
			}
		}
		arr[0] = data;
		size++;
	}
	
	// 첫번째 삭제
	public String remove() {
		String data = arr[0];
		for(int i = 1; i < size; i++) {
			arr[i-1] = arr[i];
		}
		size--;
		return data;
	}

 

---

연결 리스트 LinkedList

: 개별적으로 위치한 객체들이 다음 객체의 주소를 저장하여 연결된 자료구조
의 주소를 연결하여 이루어진 자료

• 특징

  • 검색 시 순차적으로 객체 주소를 따라가야 하므로 시간복잡도 O(n)
  • 삽입, 삭제 시 변경위치의 앞뒤에 있는 객체의 주소만 수정하면 됨

  → 삽입, 삭제가 많은 경우 사용

 

• 구성

  • Node 노드 : 연결 리스트의 자료 단위

    • Data field : 값 저장
    • Link field : 인접 노드의 주소 저장

  • Head 헤드 : 첫 노드를 가리키는 레퍼런스

 

1. 단순 연결 리스트 Singly Linked List

• 노드 클래스

public class Node {
	public String data;	// 데이터
	public Node link;	// 링크
	
	public Node() {}
	
	public Node(String data) {
		this.data = data;
	}
}

• 단순 연결 리스트 구현

public class LinkedList_Singly {
	private Node head;
	private int size;
	
	public LinkedList_Singly() {
		this.head = null;
	}
	
	// 조회
	public Node get(int idx) {
		Node cur = head;
		
		for(int i = 0; i < idx; i++) {	// idx 위치까지 이동
			cur = cur.link;
		}
		
		return cur;
	}
	
	// 첫번째 원소 삽입
	public void addFirst(String data) {
		Node node = new Node(data);	// 노드 만들기
		
		node.link = head;	// 새 노드의 링크는 head가 가리키는 노드
		head = node;		// head가 새 노드를 가리키게 변경

		size++;
	}
	
	// 마지막 원소 삽입
	public void addLast(String data) {
		Node node = new Node(data);

		if(size == 0) {
			addFirst(data);
			return;
		}
		
		// 마지막 노드 찾아가기
		Node cur = head;
		while(cur.link != null) {
			cur = cur.link;
		}
		cur.link = node;
		size++;
	}
	
	// 중간 원소 삽입
	public void add(int idx, String data) {
		if(idx < 0 || idx > size) return;
		if(idx == 0) {
			addFirst(data);
			return;
		}
		if(idx == size) {
			addLast(data);
			return;
		}
        
        Node node = new Node(data);
		Node pre = get(idx-1);		// 이전 노드 정보 가져오기
		node.link = pre.link;
		pre.link = node;
		
		size++;
	}
	
	// 첫번째 원소 삭제
	public String remove() {

		String data = head.data;
		head = head.link;
		size--;
		
		return data;
	}
	
	// 중간 원소 삭제
	public String remove(int idx) {
		if(idx < 0 || idx > size) return null;
		
		Node pre = get(idx - 1);
		Node rmNode = pre.link;
		
		pre.link = rmNode.link; 	// 기존 연결 끊어지고, 다음 노드로 연결
		size--;
        
		return rmNode.data;
	}

 

2. 이중 연결 리스트 Doubly Linked List

• 특징

  • 양쪽으로 순회할 수 있도록 하는 두 개의 링크 필드를 가짐
    → 단순 연결 리스트에서는 최악의 경우 n번의 탐색을 해야하지만,
    이중 연결 리스트에서는 얻고자 하는 데이터의 위치가 뒤쪽에 가깝다면
    역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있음