Linked List 연결리스트

• 데이터를 링크로 연결해서 관리
• 자료의 순서는 정해져 있지만, 메모리 상의 연속성은 보장하지 않는다.

장점

• 데이터의 공간을 미리 할당할 필요가 없다.

• 리스트의 길이가 가변적임
  -> 데이터의 추가, 삭제가 용이하다.

단점

• 연결 구조 위한 별도의 공간 필요
• 연결 정보 찾는데 시간이 필요
  -> 상대적으로 접근 속도가 느리다.
• 데이터의 추가, 삭제 시 앞뒤 데이터의 연결을 재구성 해줘야 한다.

단방향 연결리스트 기본 구조

• 사용되는 노드의 구조

class Node {
	T data;
    Node next;
    
    Node(){}
    Node(T data, Node next) {
    	this.data = data;
        this.next = next;
    }
}

• 일방통행적인 노드 연결 구조
• 한 방향으로만 탐색이 가능함
  • ex. 노드 D 찾기
    노드A (Head) -> 노드B -> 노드C -> 노드D
  • ex. 노드 F 찾기
    노드A (Head) -> 노드B -> 노드C -> 노드D -> 노드E -> 노드F
    

단방향 연결리스트 구현 코드

양방향 연결리스트 기본 구조

• 사용되는 노드의 구조

class Node {
	T data;
    Node next;
    Node prev;
    
    Node(){}
    Node(T data, Node next, Node prev) {
    	this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

• 양방향으로 동작하는 노드 연결구조
• 좌측으로의 탐색도, 우측으로의 탐색도 가능
  • ex. 노드 B 찾기
    노드A (Head) -> 노드B
  • ex. 노드 Y 찾기
    노드 Y <- 노드 Z (Tail) <- 노드A (Head)