Linked List

정의

데이터 요소들이 노드로 연결되어있는 선형 데이터 구조

용어 및 구성요소

Node : data, next pointer로 구성
data : 실제 값
next pointer : 다음 노드의 메모리 주소

head & tail : list의 첫 노드와 마지막 노드의 위치

특징

각 element 들은 불연속적인 메모리 위치를 가진다.
각 노드는 data와 pointer를 가지고 있다.

장점

• 삽입/삭제 속도가 빠르다
  • 삽입/삭제의 경우 인접 노드의 next pointer 주소만 변경하면 되기 때문에 빠르다
  • O(1)의 시간 복잡도를 가진다.
• 크기가 동적이다.

단점

• 조회 속도가 느리다.
  • 조회의 경우 random access가 불가능 하기 때문에 head 노드에서 순차적으로 탐색해 조회해야 하므로 느리다
  • O(n)의 시간 복잡도를 가진다.
• 캐시의 비효율성
  • 인접한 메모리를 할당하지 않으므로 공간의 연속성이 낮아 캐시 성능이 비효율적이다.

종류

• Single Linked List
  
  • 각 노드는 data와 next pointer를 가진다.
  • 단방향 탐색만 가능
• Double Linked List
  
  • 각 노드는 data와 next pointer, prev pointer를 가진다.
  • 양방향 탐색 가능
• Circular Linked List
  
  • 각 노드는 data와 next pointer, (prev pointer)를 가진다.
  • 마지막 노드가 head의 주소를 가지고 있어서 순환탐색 가능

참고자료

geeksforgeeks-linked-list