연결 리스트는 각 요소를 포인터로 연결하여 관리하는 데이터 집합체다.
기본적으로 노드(node)와 헤드(head)로 이루어져 있고, 경우에 따라 꼬리(tail)도 포함이 된 구조이다.
- 노드(node) : 데이터와 다른 노드와 연결 짓는 포인터로 구성
- 헤드(head) : 리스트의 첫 노드를 가리키는 포인터
- 꼬리(tail) : 리스트의 마지막 노드를 가리키는 포인터
배열이 “1번, 2번, 3번…”처럼 index로 접근한다면, 연결 리스트는 “철수 다음 영희, 영희 다음 민수…“처럼 노드 참조로 순서를 유지한다
연결 리스트 종류 및 구조 형태
연결 리스트의 기본 구조는 포인터를 기점으로 리스트를 순회하는 구조이다.
이때 포인터는 1개 혹은 2개가 될 수 있으며, 각 노드들의 참조 방식에 따라 단방향 혹은 양방향으로 순회가 가능하다.
노드는 두 가지 참조 방식이 존재한다.
다음 노드만을 참조하는 방식과 이전 노드도 포함하여 참조하는 방식이 있다.
노드 간 참조 형식으로 인해 리스트를 수정할 땐 각 데이터의 위치를 수정할 필요 없이 참조하는 노드 정보만 변경해 주면 되기 때문에 노드의 위치를 알고 있다면 성능면으로 이점을 얻을 수 있다.
하지만 인덱스로 접근하는 방식은 헤드 포인터를 기점으로 순차적으로 순회하여 접근하기 때문에 성능면으로 불이점을 얻게 된다.
연결 리스트는 크게 세 분류로 구분된다.
- 단일 연결 리스트 (Singly Linked List)
- 이중 연결 리스트 (Doubly Linked List)
- 원형 연결 리스트 (Circular Linked List)
단일 연결 리스트 (Singly Linked List)
단일 연결 리스트는 연결 리스트의 기본적인 형태라고 보면 된다.

위 그림을 참조하여 단일 연결 리스트의 구조적 특징을 살펴보면,
헤드 포인터 하나만을 가지고 순회하는 구조이다.
그림에서 볼 수 있듯이 한 방향으로만 순회하기 때문에 각 노드들은 데이터를 포함하여 다음 노드를 참조하는 형태가 되고, 마지막 노드의 경우 NULL을 참조하여 노드의 끝을 알리고 있다.
정리하면 다음과 같다.
- 헤드 포인터를 기점으로 모든 노드들을 연결함
- 각 노드들은 다음 노드만을 참조함
- 마지막 노드는 NULL을 참조해 끝을 알림
- 한 방향으로만 데이터를 조회할 수 있음
위 특징들을 바탕으로 삽입과 삭제 과정에 대해 알아보자.
변경전 : [A] -> [C] ( [B]를 삽입 하려는 상황 )
변경후 : [A] -> [B] -> [C]B를 A와 C사이에 넣는 상황이라면 A 다음 노드 정보를 새로 생성된 B를 대입해 주고 B 다음 노드 정보에 C를 대입해 주면 모든 게 끝난다.
그렇기 때문에 삽입의 시간 복잡도는 O(1)이 된다.
변경전 : [A] -> [B] -> [C] ( [A]를 삭제 하려는 상황 )
변경후 : [B] -> [C]
변경전 : [A] -> [B] -> [C] ( [B]를 삭제 하려는 상황 )
변경후 : [A] -> [C]삭제의 경우 리스트 첫 번째를 삭제한다면 헤드 포인터에 다음 노드를 대입해주기만 하면 끝나지만,
중간 삭제의 경우 A와 C를 이어 주기 위해 B 외로 A의 정보까지 필요하기 때문에 순회과정이 필요하다.
그렇기 때문에 삭제의 시간 복잡도는 첫 노드시 O(1) 그 외에는 O(n)이 된다.
이중 연결 리스트 (Doubly Linked List)
이중 연결 리스트는 단방향에서 양방향으로 바뀐 형태이다.

이중 연결 리스트의 구조적 특징은 헤드 포인터와 꼬리 포인터를 통해 순회하는 구조이다.
그림에서 볼 수 있듯이 양방향으로 순회하기 때문에 각 노드들은 다음 노드뿐만 아니라 이전 노드를 포함하여 참조하게 된다.
또한 리스트의 끝은 양방향 순회로 인해 헤드와 꼬리 모두 끝을 알리는 NULL을 참조하게 된다.
정리하면 다음과 같다.
- 헤드 포인터와 꼬리 포인터를 기점으로 모든 노드들을 연결함
- 각 노드들은 다음 및 이전 노드를 참조함
- 양방향으로 데이터 조회가 가능
- 헤드와 꼬리 모두 NULL을 참조하여 리스트의 끝을 알림
이중 연결 리스트의 삽입과 삭제는 단일 연결 리스트와 크게 다를거 없지만 삭제 과정이 좀 달라진다.
변경전 : [A] -> [B] -> [C] ( [B]를 삭제 하려는 상황 )
변경후 : [A] -> [C]단방향의 경우 중간 삭제시 이전 노드의 정보를 얻기 위해 리스트를 순회해야하는 번거로움이 있었지만,
이중 연결 리스트의 경우 양방향 순회가 가능하므로 B 노드만으로 A와 C의 참조 관계를 수정할 수 있어 번거로움이 없어진다.
그로 인해 삭제의 시간 복잡도는 O(1)이 되게 된다.
처리 시간에 대해선 성능적 이점을 얻긴하지만, 그만큼 더 많은 정보를 가져야 되므로 메모리 사용량에 대해선 기존 보다 불이점을 얻게 된다.
원형 연결 리스트 (Circular Linked List)

원형 연결 리스트의 구조적 특징은 끝이 존재하지 않는 것이다.
위 그림을 보면 헤드 포인터를 기점으로 순회하며 리스트의 끝에 도달하면 다시 리스트의 첫 위치로 이동하는 것을 확인할 수 있다.
원형 연결 리스트의 구조는 끝이 존재하지 않다는 특징 외로 연결 리스트와 똑같으므로 상황에 맞게 단일 혹은 이중으로 설계하면 된다.
정리하면 다음과 같다.
- 끝이 없는 순회구조
- 단일 혹은 이중으로 설계
원형 연결 리스트를 순회할 땐 끝이 존재하지 않아 무한 순회를 하게 될 수 있어 설계시 순회 끝 조건을 잘 설계 해야한다.
'Study' 카테고리의 다른 글
| 자료구조 - 배열 (Array) (0) | 2026.09.03 |
|---|---|
| Sync 및 Async와 Blocking 및 Non-blocking (2) | 2024.10.08 |
| Synchronous vs Asynchronous & Blocking vs Non-blocking (0) | 2024.10.07 |
| 자료구조 해시 테이블(HashTable) (0) | 2024.09.25 |
| 싱글톤(Singleton) 클래스와 정적(Static) 클래스 (0) | 2024.08.25 |



























