연결 리스트 (Linked List) 자료구조 완벽 가이드

배열(Array)과 함께 선형 자료구조의 양대 산맥을 이루는 **연결 리스트(Linked List)**에 대해 알아보겠습니다. 두 자료구조의 차이점과 장단점을 비교하는 질문은 면접 단골 소재입니다.

1. 연결 리스트란?

연결 리스트는 연속적인 메모리 공간에 데이터를 저장하는 배열과 달리, 크기가 동적으로 변할 수 있으며 데이터가 메모리상의 여러 군데에 흩어져서 존재하는 자료구조입니다.

흩어져 있는 데이터를 하나로 묶기 위해, 각 데이터는 자신의 값(Value/Data)뿐만 아니라 **‘다음 데이터의 위치를 가리키는 포인터(Next Pointer)‘**를 함께 저장합니다. 이렇게 데이터와 포인터가 결합된 하나의 단위를 **노드(Node)**라고 부릅니다.

Node (노드): 연결 리스트를 구성하는 기본 단위. (데이터 필드 + 링크(포인터) 필드)
Head (헤드): 연결 리스트의 가장 첫 번째 노드를 가리키는 참조값. 리스트의 시작점입니다.
Tail (테일): (선택적) 연결 리스트의 가장 마지막 노드를 가리킵니다.

2. 배열(Array)과의 핵심 차이 및 시간 복잡도

연결 리스트를 이해하는 가장 좋은 방법은 배열과 비교하는 것입니다.

연산 / 특징	배열 (Array)	연결 리스트 (Linked List)
메모리 할당	정적 (컴파일 타임에 크기 결정, 연속적 공간)	동적 (런타임에 크기 변경, 비연속적 공간)
임의 접근 (조회)	$O (1)$ (인덱스로 즉시 접근)	$O (N)$ (Head부터 순차적으로 탐색해야 함)
삽입 / 삭제	$O (N)$ (데이터를 밀거나 당겨야 함)	$O (1)$ (삽입/삭제할 위치를 안다는 가정하에 포인터만 변경)
공간 오버헤드	적음 (데이터만 저장)	큼 (데이터 외에 포인터 저장 공간이 추가로 필요)

중요 포인트: 연결 리스트의 삽입/삭제 시간 복잡도가 $O (1)$ 이라는 것은, 삽입/삭제할 특정 노드의 위치(포인터)를 이미 알고 있을 때를 의미합니다. 만약 특정 ‘값’을 찾아서 삭제해야 한다면, 탐색에 $O (N)$ 이 걸리므로 총합 시간은 $O (N)$ 이 됩니다. 가장 강점을 가지는 곳은 맨 앞(Head)에 노드를 추가하거나 삭제할 때입니다.

3. 연결 리스트의 종류

단일 연결 리스트 (Singly Linked List): 각 노드가 ‘다음’ 노드를 가리키는 포인터 하나만 가집니다. 일방통행으로만 순회할 수 있으며, 뒤로 되돌아갈 수 없습니다.
이중 연결 리스트 (Doubly Linked List): 각 노드가 ‘이전’ 노드(Prev)와 ‘다음’ 노드(Next)를 가리키는 두 개의 포인터를 가집니다. 양방향 순회가 가능하여 앞뒤로 이동이 자유롭지만, 메모리(포인터 공간)를 더 차지하고 구현이 복잡합니다.
원형 연결 리스트 (Circular Linked List): 마지막 노드의 포인터가 Null(None)이 아니라, 다시 첫 번째 노드(Head)를 가리켜 원형을 이루는 구조입니다. 단일 또는 이중 연결 리스트 모두 원형으로 만들 수 있습니다.

4. 파이썬을 이용한 단일 연결 리스트 구현 예시

파이썬에는 기본적으로 리스트(list)가 배열과 연결 리스트의 장점을 혼합한 동적 배열(Dynamic Array) 형태로 잘 구현되어 있습니다. 하지만 인터뷰나 알고리즘 이해를 위해 직접 구현하는 코드를 자주 봅니다.

# 노드(Node) 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# 단일 연결 리스트(Singly Linked List) 클래스 정의
class LinkedList:
    def __init__(self):
        self.head = None
 
    # 맨 뒤에 노드 추가 (Append)
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
 
    # 리스트 출력
    def display(self):
        current = self.head
        while current:
            print(f"[{current.data}]", end=" -> ")
            current = current.next
        print("None")
 
# 사용 예시
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display() # 출력: [10] -> [20] -> [30] -> None

5. 연결 리스트의 활용 사례

동적 크기가 필요한 데이터: 데이터의 크기를 미리 알 수 없거나 잦은 크기 변화가 발생할 때 유용합니다.
다른 자료구조의 기반: 스택, 큐, 해시 테이블의 체이닝(Chaining), 그래프의 인접 리스트 등을 구현하는 뼈대가 됩니다.
LRU 캐시 (Least Recently Used Cache): 가장 최근에 사용된 데이터를 빠르게 갱신하기 위해 해시 맵과 ‘이중 연결 리스트’를 결합하여 $O (1)$ 성능의 캐시를 구현합니다. (면접 단골 문제)
운영체제 메모리 관리: 사용 가능한 여유 메모리 블록들을 연결 리스트로 관리합니다.
텍스트 에디터의 실행 취소(Undo): 상태나 글자 단위의 변경 사항을 이중 연결 리스트로 관리하여 앞뒤로 이동합니다.

요약

연결 리스트(Linked List)는 데이터의 물리적 위치에 구애받지 않고 포인터로 연결하여 동적인 크기를 지원하는 선형 자료구조입니다. 배열(인덱스를 통한 빠른 임의 접근)과 연결 리스트(포인터 조작을 통한 빠른 삽입/삭제)의 상반된 특성과 트레이드오프(Trade-off)를 명확히 설명할 수 있어야 합니다. 특히 ‘이중 연결 리스트’를 활용한 LRU 캐시 구현 등은 고급 인터뷰에서 매우 자주 다루는 주제입니다.

anonymous.rs

Explorer

자료구조: 연결 리스트 (Linked List)