연결 리스트 (Linked List)
쉽게 풀면
기차 칸을 떠올려 보세요. 각 객차는 바로 다음 객차와만 연결 고리로 이어져 있고, 객차 전체가 한 줄로 붙어있을 필요는 없습니다. 연결 리스트도 마찬가지입니다.
데이터를 담은 "칸(노드)" 하나하나가 메모리 어디에 흩어져 있어도 상관없이, 각 칸이 "다음 칸은 여기야"라는 화살표(포인터)만 갖고 있으면 전체가 하나의 줄로 이어집니다. 배열처럼 처음부터 자리를 예약해두지 않아도 되고, 중간에 새 칸을 끼워 넣거나 빼는 것도 앞뒤 화살표만 바꿔주면 되니 비교적 간단합니다.
다만 몇 번째 칸인지 바로 찾아가려면 처음부터 하나씩 따라가야 해서, 배열처럼 "몇 번째 칸"을 한 번에 짚어내지는 못합니다.
왜 중요한가
연결 리스트는 배열과 함께 자료구조 교육과 시스템 설계에서 가장 기본이 되는 선택지 중 하나이기 때문에, 자료구조·알고리즘 논문뿐 아니라 운영체제, 데이터베이스, 컴파일러 등 실제 시스템을 다루는 논문에서도 배경 설명이나 구현 세부사항으로 자주 등장합니다.
삽입·삭제가 잦고 크기를 미리 알 수 없는 데이터를 다뤄야 하는 상황에서 연결 리스트 기반 설계는 성능과 메모리 사용의 트레이드오프를 논의하는 출발점이 됩니다.
또한 스택, 큐, 해시테이블의 체이닝, 그래프의 인접 리스트 표현 등 더 복잡한 자료구조들이 연결 리스트 개념 위에서 만들어지기 때문에, 이를 정확히 이해하는 것이 다른 자료구조를 다루는 논문을 읽는 데도 도움이 됩니다.
핵심 정리
- 연결 리스트는 각 칸(노드)이 값과 다음 칸의 위치(포인터)를 함께 가지고 줄줄이 이어진 자료구조입니다. 시작점을 가리키는 head를 알면 전체를 따라갈 수 있습니다.
- 변형: 다음 칸만 가리키는 단일 연결 리스트, 앞뒤를 모두 가리키는 이중 연결 리스트, 마지막이 처음으로 이어지는 원형 연결 리스트.
- 배열은 칸이 메모리에 나란히 놓여 번호로 바로 찾아가지만, 연결 리스트는 칸이 흩어져 있어 앞에서부터 따라가야 합니다.
| 연산 | 연결 리스트 | 배열 |
|---|---|---|
| i번째 접근 | O(n) | O(1) |
| 맨 앞 삽입 | O(1) | O(n) |
| 노드를 이미 가리키고 있을 때 뒤에 삽입 | O(1) | O(n) |
| 값으로 탐색 | O(n) | O(n) |
삽입이 O(1)이려면 삽입할 자리의 노드를 이미 알고 있어야 합니다. 그 자리를 찾는 비용은 따로 듭니다(Cormen et al., 2009).
예시로 보기
세 노드 3 → 7 → 9 에서 7 뒤에 8을 끼워 넣으면 다음 두 줄이면 됩니다.
새노드.next = 7노드.next7노드.next = 새노드
결과는 3 → 7 → 8 → 9 입니다. 뒤의 노드를 하나도 옮기지 않았다는 점이 배열과 다릅니다. 반대로 3번째 값을 읽으려면 head에서 두 번 따라가야 합니다.
이 구조는 스택·큐 구현, 해시 테이블의 체이닝(같은 칸에 걸린 값을 줄로 잇기), 그래프의 인접 리스트, 메모리 할당기의 빈 블록 목록 등에 쓰입니다.
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| 연결 리스트는 배열보다 항상 삽입·삭제가 빠르다. | 삽입 자리를 찾는 시간까지 합치면 O(n)일 수 있습니다. 또한 노드가 메모리에 흩어져 있으면 CPU 캐시 효율이 떨어져 실제로는 배열이 더 빠른 경우가 많습니다. |
| 메모리를 덜 쓴다. | 노드마다 포인터를 더 저장하므로 같은 데이터에서 보통 메모리를 더 씁니다. |
| 크기를 미리 몰라도 된다는 건 크기에 한계가 없다는 뜻이다. | 필요할 때 노드를 할당하지만 전체 메모리 한도는 그대로입니다. |
| 스택·큐와 같은 말이다. | 스택·큐는 넣고 빼는 규칙(추상 자료형)이고, 연결 리스트나 배열은 이를 구현하는 방법입니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 "해당 모듈이 배열이 아니라 노드들을 포인터로 연결한 구조를 사용했고, 그 덕분에 데이터를 추가하거나 제거하는 연산이 데이터 개수와 무관하게 일정한 시간에 끝난다"는 뜻입니다.
이 문장은 "메모리를 관리하는 프로그램이 비어 있는 메모리 조각들을 앞뒤 양쪽 모두를 가리키는 연결 리스트로 관리해서, 어떤 조각이 해제되면 바로 앞뒤 조각과 합칠 수 있다"는 뜻입니다.
이 문장은 "그래프를 표현할 때 각 노드마다 자신과 연결된 다른 노드들을 연결 리스트로 나열해 저장하는 방식이, 연결이 적은 그래프에서는 모든 쌍을 표로 저장하는 방식보다 메모리를 덜 쓴다"는 뜻입니다.
조금 더 깊게 보면
연결 리스트는 각 노드가 다음 노드만 가리키는 단일 연결 리스트(singly linked list)와, 앞뒤 노드를 모두 가리키는 이중 연결 리스트(doubly linked list), 마지막 노드가 다시 첫 노드를 가리켜 원형을 이루는 원형 연결 리스트(circular linked list)로 나뉩니다.
논문에서 구현 세부사항을 설명할 때는 어떤 변형을 사용했는지, 그리고 삽입·삭제·탐색 각 연산의 시간복잡도가 노드 개수에 따라 어떻게 달라지는지를 함께 언급하는 경우가 많습니다.
또한 실제 시스템에서는 캐시 지역성(cache locality) 문제 때문에 연결 리스트가 배열보다 느리게 동작할 수 있는데, 이는 노드들이 메모리 여기저기 흩어져 있어 CPU 캐시를 효율적으로 활용하기 어렵기 때문입니다.
주의할 점
연결 리스트는 삽입·삭제가 빠르다는 장점만 부각되기 쉽지만, 특정 위치의 데이터를 읽으려면 처음부터 순서대로 따라가야 하므로 임의 접근(random access) 속도는 배열보다 느립니다. 또한 각 노드가 다음 노드를 가리키는 포인터를 별도로 저장해야 해서 메모리도 더 사용합니다. 알고리즘의 효율을 판단할 때는 이런 시간복잡도와 빅오 표기법 차이를 함께 고려해야 합니다.
헷갈리기 쉬운 용어
| 용어 | 성격 |
|---|---|
| 연결 리스트 | 노드를 포인터로 잇는 구현 방식(자료구조) |
| 스택과 큐 | 넣고 빼는 순서 규칙(추상 자료형). 연결 리스트로도, 배열로도 구현 |
참고 문헌
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.