연결 리스트

연결 리스트

• 데이터가 자료의 주소 값으로 서로 연결 되어있는 구조
• 단순 연결 리스트, 이중 연결 리스트, 환형 연결 리스트 등의 구조가 있다.

배열 vs 연결 리스트

연결리스트의 시간 복잡도

• $i$번째 원소 접근: $O(N)$
• 원소 삽입: $O(N)$ (삽입할 원소의 위치까지 탐색 $O(N)$ + 원소 삽입 $O(1)$)
• 원소 제거: $O(N)$ (제거할 원소의 위치까지 탐색 $O(N)$ + 원소 제거 $O(1)$)

연결 리스트의 종류

단순 연결 리스트 (Singly Linked List)

• 각 노드에서 단방향으로 연결되는 리스트이다.
• 후행 노드에는 쉽게 접근 가능하지만, 선행 노드 접근이 조금 복잡하다.
• 마지막 노드의 next는 NULL 포인터이다.
• HEAD를 기억해두고 사용하면 된다.
• 한 쪽 끝의 노드를 추가/제거하는데 용이하다.
  • Stack 처럼 사용시, PUSH, POP을 하는데 $O(1)$의 시간이 걸린다.

struct Node<T> {
    Node<T> *next;
    T data;
}

이중 연결 리스트 (Doubly Linked List)

• 각 노드에서 양방향으로 연결되는 리스트이다.
• 양방향으로 접근이 편하지만, 메모리를 추가적으로 이용한다.
• 첫번째 노드의 prev와 마지막 노드의 next는 NULL 포인터이다.
• HEAD와 TAIL을 기억해두고 사용하면 된다.
• 양 끝의 노드를 추가/제거하는데 용이하다.
  • Stack 처럼 사용시, PUSH, POP을 하는데 $O(1)$의 시간이 걸린다.
  • Queue 처럼 사용시, ENQUEUE, DEQUEUE를 하는데 $O(1)$의 시간이 걸린다.

struct Node<T> {
    Node<T> *prev;
    Node<T> *next;
    T data;
}

원형 연결 리스트 (Circular Linked List)

• 각 노드에서 단방향으로 진행되는 리스트
• 한 노드에서 모든 노드로 접근이 가능
• 어떤 한 노드만 알아도 모든 노드를 순회할 수 있다.
• 모든 노드의 next가 임의의 노드를 가리킨다.

struct Node<T> {
    Node<T> *next;
    T data;
}

연결 리스트의 동작

데이터의 삽입