연결 리스트 자료구조, 노드와 포인터로 이해하기
연결 리스트는 노드가 다음 노드를 가리켜 이어지는 자료구조다. 중간 삽입·삭제는 O(1)이지만 n번째 접근은 O(n)이다. 배열과의 차이, 단일·이중·원형 형태, 자바 LinkedList·C++ list·파이썬 deque의 구현을 정리했다.
연결 리스트(linked list)는 데이터를 담은 '노드(node)'가 다음 노드의 위치를 가리키는 참조(포인터)를 들고 사슬처럼 이어진 자료구조다. 배열처럼 메모리에 한 덩어리로 붙어 있지 않아서, 원소를 중간에 끼우거나 빼낼 때 뒤 원소를 밀 필요가 없다. 대신 n번째 원소로 곧장 건너뛰지 못하고 앞에서부터 하나씩 따라가야 한다. 이 한 문장에 연결 리스트의 장단점이 모두 들어 있다.
이 글은 개발자 관점에서 연결 리스트의 동작 원리, 배열과의 트레이드오프, 단일·이중·원형 형태의 차이, 그리고 자바·C++·파이썬 표준 라이브러리가 이를 어떻게 제공하는지를 다룬다. 특정 언어의 문법 강의나 코딩 테스트 풀이는 다루지 않는다. 표준 라이브러리 동작은 Oracle 자바 공식 문서와 cppreference의 컨테이너 규격을 근거로 삼았다.
노드와 포인터로 이어지는 구조
노드 하나는 두 부분으로 이뤄진다. 저장할 값과, 다음 노드의 주소를 담은 참조다. 리스트의 시작점은 첫 노드를 가리키는 head 포인터가 잡고 있고, 마지막 노드의 참조는 아무 곳도 가리키지 않는다는 뜻으로 null(C++의 nullptr, 파이썬의 None에 해당)을 담는다. 이 null이 곧 리스트의 끝 표시다.
그래서 리스트를 훑는 코드는 head에서 출발해 참조를 따라 다음 노드로 넘어가다가, 참조가 null이 되는 순간 멈춘다. C로 쓰면 형태가 이렇게 단순하다.
struct Node {
int value;
struct Node *next; // 다음 노드 주소
};
struct Node *cur = head;
while (cur != NULL) {
visit(cur->value); // 값 처리
cur = cur->next; // 다음으로 이동
}노드가 메모리 어디에 있든 상관없다. 새 값을 넣을 자리를 알고 있다면, 그 앞 노드의 참조를 새 노드로 돌리고 새 노드의 참조를 원래 다음 노드로 걸어 주면 끝이다. 원소가 100만 개든 이 연결 작업 자체는 포인터 몇 번 대입으로 끝난다. 배열이라면 뒤쪽을 통째로 밀어야 하는 지점이다.
배열과 무엇이 다른가
가장 큰 차이는 메모리 배치와 접근 비용이다. 배열은 원소가 연속된 메모리에 놓여서 인덱스만 알면 주소를 바로 계산해 O(1)에 접근한다. 연결 리스트는 노드가 흩어져 있어 n번째 원소를 보려면 앞에서부터 n번 따라가야 하므로 O(n)이다.
삽입과 삭제는 정반대다. 배열은 중간에 원소를 넣으면 그 뒤를 전부 한 칸씩 밀어야 해서 O(n)이 든다. 연결 리스트는 대상 노드를 이미 손에 쥐고 있다면 참조 몇 개만 바꿔 O(1)에 끝난다. 아래 표가 이 대비를 요약한다.
| 연산 | 배열 | 연결 리스트 |
|---|---|---|
| n번째 원소 접근 | O(1) | O(n) |
| 맨 앞 삽입·삭제 | O(n) | O(1) |
| 찾아둔 노드 뒤 삽입·삭제 | O(n) | O(1) |
| 메모리 배치 | 연속 | 노드별로 흩어짐 |
표에 안 담긴 실무 변수가 하나 더 있다. 캐시 지역성이다. 배열은 원소가 붙어 있어 CPU가 한 번에 여러 원소를 캐시로 끌어와 순회가 빠르다. 연결 리스트는 노드가 힙 여기저기에 흩어져 있어 다음 노드로 넘어갈 때마다 캐시 미스가 날 확률이 높다. 그래서 같은 O(n) 순회라도 배열 계열이 실제 벽시계 시간에서 앞서는 경우가 많다.
단일·이중·원형, 세 가지 형태
연결 리스트는 노드가 든 참조의 개수와 방향에 따라 갈린다.
- 단일 연결 리스트: 노드가 next 참조 하나만 든다. 앞에서 뒤로만 이동하고 메모리를 가장 적게 쓴다.
- 이중 연결 리스트: next와 prev 두 참조를 둬 양방향으로 오간다. 노드마다 포인터가 하나 더 붙어 메모리를 더 쓴다.
- 원형 연결 리스트: 마지막 노드가 다시 head를 가리켜 고리를 이룬다. 순서를 돌아가며 처리하는 라운드로빈 스케줄링 같은 곳에 맞는다.
cppreference에 따르면 C++ 표준 라이브러리의 std::forward_list는 단일 연결 리스트, std::list는 이중 연결 리스트다. 노드가 다른 노드를 가리킨다는 발상 자체는 각 노드가 여러 노드를 가리키는 그래프로 자연스럽게 확장되는데, 이 구조로 실행 흐름을 제어하는 이야기는 노드와 엣지로 흐름을 제어하는 그래프 오케스트레이션에서 따로 다뤘다.
표준 라이브러리는 연결 리스트를 어떻게 제공하나
바닥부터 노드를 짤 일은 실무에서 드물다. 주요 언어가 이미 구현을 제공한다.
자바는 java.util.LinkedList를 준다. Oracle 자바 공식 문서에 따르면 이 클래스는 List와 Deque 인터페이스를 함께 구현한 이중 연결 리스트이며, get(i)처럼 인덱스로 접근할 때는 리스트의 앞이나 뒤 중 목표 인덱스에 가까운 쪽에서 순회를 시작한다. 즉 인덱스 접근은 여전히 O(n)이라는 뜻이다. 메서드별 동작은 Oracle 공식 API 문서에서 확인할 수 있다.
C++는 두 갈래로 나눠 준다. cppreference의 컨테이너 규격에 따르면 std::list는 양방향 이터레이터를 지원하는 이중 연결 리스트이고, std::forward_list는 C++11에서 추가된 단일 연결 리스트로 전방 이터레이터만 지원하는 대신 노드당 포인터가 하나뿐이라 메모리를 덜 쓴다.
파이썬에는 고전적인 연결 리스트 클래스가 없다. 대신 collections.deque가 그 자리를 채운다. CPython 구현은 원소를 하나씩 노드로 만들지 않고 64개 포인터를 담는 블록을 이중으로 연결하는 방식이라, 양쪽 끝에서의 추가·제거가 O(1)로 끝난다. 순수한 단일 연결 리스트가 필요하면 직접 클래스를 정의하는 편이 보통이다.
언제 쓰고, 언제 피하나
양쪽 끝이나 이미 찾아둔 위치에서 삽입·삭제가 잦고 인덱스 임의 접근이 드물면 연결 리스트가 맞다. 반대로 인덱스로 마구 접근하거나 순회 속도, 메모리 밀도가 중요하면 동적 배열이 낫다. 자바 ArrayList, C++ std::vector, 파이썬 list 같은 동적 배열이 대부분의 상황에서 기본값이 되는 이유가 여기 있다.
연결 리스트가 진가를 내는 자리는 정해져 있다. 양 끝 삽입·삭제가 핵심인 큐와 데크, 그리고 이중 연결 리스트와 해시맵을 엮어 가장 오래된 항목을 O(1)에 밀어내는 LRU 캐시가 대표적이다. 이런 패턴에서는 노드를 포인터로 직접 떼었다 붙이는 성질이 그대로 이득이 된다.
마지막으로 흔한 오해 하나. 연결 리스트의 삽입·삭제가 O(1)이라는 말에는 '대상 노드를 이미 알고 있을 때'라는 전제가 붙는다. 세 번째 노드 뒤에 값을 넣으려고 그 노드를 인덱스로 찾아가는 순간, 앞에 O(n) 탐색이 먼저 붙는다. 이 전제를 빼먹으면 연결 리스트를 엉뚱한 자리에 쓰게 된다.
