📌 연결 리스트

연결 리스트 (Linked List)는 "중간에 원소를 삽입 / 삭제할 수 없다."는 배열의 단점을 보완하기 위해 만들어진 자료구조이다.
데이터(Data)와 링크 / 포인터(Link / Pointer)로 구성된 노드(Node)들이 일렬로 연결되어 있는 선형 자료구조이다.
데이터의 크기가 자주 변하거나 데이터의 추가 / 삭제가 빈번하게 일어나는 경우 사용하기 적합하다.

💡 용어

• 노드(Node) : 연결 리스트의 기본 단위, 데이터와 포인터로 나뉘어져 있다.
• 링크 / 포인터(Link / Pointer) : 이전 / 다음 노드와의 연결 정보를 가지고 있다.
• 헤드(Head) : 가장 처음 위치하는 노드를 가리키는 포인터
• 테일(Tail) : 가장 마지막에 위치하는 노드를 가리키는 포인터

💡 특징

1. 가장 처음 노드를 가리키는 헤드 포인터가 존재하며, 헤드 포인터를 통해 참조한다.
2. 가장 마지막 노드를 가리키는 테일 포인터가 존재한다.

💡 종류

1. 단일 연결 리스트

각 노드가 다음 노드를 가리키는 포인터만 가지는 연결 리스트이다.
이전 노드에 대한 정보가 없으므로 역방향 탐색이 불가능하다.

2. 이중 연결 리스트

각 노드가 다음 노드에 대한 포인터 뿐만 아니라 이전 노드를 가리키는 포인터도 가지고 있는 연결 리스트이다.
역방향 탐색은 가능해졌지만 이전 노드 포인터로 인해 추가적인 메모리 오버헤드가 발생한다.

3. 원형 연결 리스트

테일 노드의 포인터가 헤드 노드를 가리키는 순환 구조를 가지는 연결 리스트이다.

💡 시간 복잡도

• 읽기(read) : O(n)
• 삽입(insert) : O(1)
• 삭제(delete) : O(1)
• 탐색(search) : O(n)

💡 장 / 단점

장점

1. 데이터의 크기를 동적으로 조절할 수 있다.
2. 데이터의 삽입 / 삭제가 쉽고 빠르다.
3. 데이터가 연속적으로 할당되지 않기 때문에 메모리를 효율적으로 사용할 수 있다.

단점

1. 임의 접근(Random Access)이 불가능하다.
2. 각 노드마다 다음 노드를 가리키는 포인터를 가지기 때문에 추가적인 메모리 오버헤드가 발생한다.

---

Reference

연결 리스트 - 위키백과
[자료구조] C - 연결리스트(linkedlist) - 1. 단순연결리스트
[Java/자료구조] 선형구조 - 연결 리스트 이해하기 : 단순, 이중, 순환 연결리스트
연결리스트 (Linked List)
1-5. [자료구조이론] Linked List (연결 리스트)