[자료구조] Linked List (연결 리스트) - 정의, 예제, 시간복잡도, 장단점

# 자료 구조 시리즈

1. Array (배열)
2. Linked List (연결 리스트)
3. Stack
4. Queue
5. Tree (Binary / Segment)
6. Graph
7. Deque
8. Heap & Priority Queue
9. Trie

---

자료구조(Data Structure)에서는 자료에 효율적으로 접근하고 수정할 수 있도록, 데이터를 구성하고 저장하는 방법을 공부합니다. 자료구조는 데이터의 형태에 따라 크게 선형과 비선형으로 구분됩니다. 선형 자료구조는 데이터가 일렬로 나열되어 있는 반면, 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다는 것이 핵심입니다. 전자의 예시로는 Array, Linked List, Stack, Queue 등이 있으며 후자에는 Tree, Graph 등이 있습니다.

 

Linked List (연결 리스트)

---

1. 정의

  Linked List(연결 리스트)는 Node(노드; 데이터와 포인터의 묶음으로, Vertex라고도 함)를 저장할 때 다음 순서의 노드 위치를 가리키는 방식, 즉 노드끼리 연결한 자료 구조입니다. 제일 앞에 있는 노드는 Head, 제일 끝에 있는 노드는 Tail이라고 부릅니다. 아래 Singly Linked List 모식도에서 볼 수 있듯 40 데이터를 가지고 있는 Tail 노드는 링크(포인터)가 없습니다.

 

https://opentutorials.org/module/1335/8821

  Linked List의 종류로는 Singly(단일) Linked List, Doubly(이중) Linked List, Circular(원형) Linked List가 존재합니다. Singly Linked List는 다음 노드의 주소(next)만 알고 있기 때문에, 특정 값을 갖고 있는 노드를 탐색하거나 마지막 노드(Tail)를 삭제하기 위해서 알아야하는 이전 노드(prev)를 찾기 위해 처음부터 탐색해야한다는 단점이 있습니다. 이러한 문제를 보완한 것이 Doubly Linked List입니다. Doubly Linked List는 앞 노드와 뒷 노드가 연결되어 있고 Circular Linked List는 Tail 노드가 Head 노드를 가리키고 있다는 것이 가장 큰 차이점입니다. 

 

 

Doubly Linked List

 

Circular Linked List

---

 

  Linked List에 노드를 삽입하는 방법은 세 가지가 존재합니다. (Singly Linked List를 기준으로 설명하겠습니다!)

1) 맨 앞에 노드를 삽입
2) 맨 뒤에 노드를 삽입
3) 중간에 노드를 삽입

 

  1) 맨 앞에 노드를 삽입

  Linked List가 비어 있는 경우(즉, head == null이면), 데이터 100을 포함하는 새로운 노드를 만들어 head가 이 노드를 가리키도록 합니다.

 

반응형

---

2. Linked List의 시간복잡도

 

  1) Singly(단일) Linked List의 시간복잡도

  세 가지 Linked List의 데이터 탐색 시간복잡도는 O(N)입니다. Array는 index를 사용하여 상수 시간인 O(1)만에 데이터를 탐색할 수 있는 반면, Linked List는 N개의 데이터 중 특정 데이터를 찾기 위해서는 첫 번째 노드부터 순차적으로 접근해야 합니다. 즉, 최악의 경우 O(N)만큼의 시간복잡도가 소요됩니다.

 

  하지만 데이터 삽입/삭제에서는 Linked List의 진가가 발휘됩니다. Array는 데이터 삽입 시 index와 함께 나머지 데이터들을 앞/뒤로 한 칸씩 밀거나 당겨야 합니다. 만약 첫 번째 index에 새로운 원소를 삽입한다면 나머지 N개의 원소들을 모두 한 칸씩 밀어내야 합니다. (Singly) Linked List에서는 새로운 노드가 추가될 때 이전 노드의 pointer만 업데이트해주면 되므로 O(1)의 시간복잡도로 표기할 수 있습니다.

---

  2) Doubly(이중) Linked List의 시간복잡도

  Doubly Linked List는 Singly Linked List와 달리 Head 노드부터 데이터를 탐색할 필요가 없습니다. Head는 물론 Tail에서부터 접근할 수 있기 때문에 index를 활용하면 처음과 끝, 어디서 더 가까운지 아는 상황에서 N 번을 탐색하는 것이 아닌N/2 만으로도 충분합니다. 물론 시간복잡도를 나타내는 Big O 표기법으로는 상수(constant)를 무시하기 때문에 Doubly Linked List도 O(N)으로 표기됩니다.

 

  또한, 첫 번째 노드와 마지막 노드를 모두 알고 있기 때문에 양 끝 지점에 데이터를 삽입/삭제하는데 시간복잡도가 O(1)밖에 소비되지 않습니다. 이러한 장점 덕에 Doubly Linked List는 뒤에서 다룰 큐(queue)를 구현함에 있어 완벽한 자료 구조가 됩니다. 

 

  각 노드에 포인터가 두 개씩 존재하여 성능상으로 유연하게 이후(next) 및 이전(prev) 노드를 가리키는 것이 가능하지만, 더 많은 메모리가 필요하다는 점에서 데이터 탐색 시 절반으로 줄일 수 있었던 시간복잡도(Big O 표기법으로는 여전히 O(N)임에 주의!)와 트레이드 오프(trade-off) 관계가 존재합니다.

---

  3) Circular(원형) Linked List의 시간복잡도

  마지막 노드가 null을 가리키는 Single Linked List와 달리, Circular Linked List는 마지막 노드가 첫 번째 노드, 즉 Head 노드를 가리킵니다. 그렇기 때문에 어느 노드부터 탐색해도 무방하다는 점에서 데이터 탐색에 있어 차이는 존재하지만 시간복잡도는 차이가 없습니다. Circular Linked List는 Queue, Circular Buffer(마지막에 새로운 원소를 추가하고 앞에서 오래된 원소를 제거), Circular List(노래 목록 반복 재생) 구현에 사용됩니다.

---

3. Linked List의 장단점

  1) 장점

1. Dynamic Size : Linked List는 노드를 쉽게 추가/제거할 수 있기 때문에 필요에 따라 리스트의 크기가 자유롭게 변합니다. 크기가 고정되어 Array 내부에 원소를 쉽사리 추가/제거할 수 없는 것과 대조적입니다.

2. 삽입/삭제 : 원소 삽입/삭제 시 앞뒤 노드의 next 포인터만 업데이트하는 것이 삽입/삭제 시 뒤 원소들을 모두 이동시켜야 하는 Array에 비해 효율적입니다.

3. 메모리 효율성 : Linkied List는 전체 요소가 아닌 다음 노드에 대한 참조만 저장하기 때문에 Array보다 메모리를 덜 사용합니다. 사이즈가 큰 List로 작업하거나 제한된 메모리 환경에서 유용합니다.

---

   2) 단점

1. Random Access : Head 노드에서 시작하여 원하는 데이터에 도달할 때까지 next 포인터를 따라야 하기 때문에 개별 원소 탐색에 있어 비효율적입니다. index를 사용하여 상수 시간에 모든 원소에 접근할 수 있는 Array와의 차이점입니다.

2. Memory Overhead : Linked List의 각 노드는 추가 메모리를 사용할 수 있는 다음 노드에 대한 추가 참조가 필요합니다.

3. Not Cache-friendly : Linked List에서는 원소가 메모리에 연속적으로 저장되지 않기 때문에 캐시 친화적이지 않습니다. 특히 원소가 순서대로 접근할 수 없는 경우에서는 Linked List의 접근 속도가 Array의 요소에 접근하는 것보다 느릴 수 있습니다.

 

 

탐색이나 정렬이 자주 이뤄지는 자료구조에는 Array를,
데이터 추가/삭제가 빈번하게 이뤄지는 자료구조에는 Linked List를 사용합시다!

---

참고자료 
 - https://yoongrammer.tistory.com/43
 - https://opentutorials.org/module/1335/8821 
 - https://code-lab1.tistory.com/2 
 - https://gitub.com/Seogeurim/CS-study

 

 

 

[GitHub] 깃허브 잔디 심는 법 - GitHub Contributions

[인공지능] 생성 모델 (Generative AI Model)이란? (1) : AutoEncoder, VAE, GAN

[Kubernetes] CKA(Certified Kubernetes Administration) 자격증 후기/접수 방법/출제 범위/할인바우처 (+CKAD, CKS