close
프로필 배경
프로필 로고

개냥이

CodingTest/자료구조-알고리즘 · 2026. 3. 16. fullscreen 넓게보기

연결 리스트 (Linked List)

연결 리스트란

연결 리스트는 노드(Node)들이 사슬처럼 이어진 자료구조다. 각 노드는 두 가지를 담고 있다. 하나는 실제 데이터인 값(value)이고, 다른 하나는 다음 노드를 가리키는 참조(next)다. 마지막 노드의 참조는 None으로 끝난다.

연결 리스트의 시작점을 head라고 부른다. head를 알면 연결된 모든 노드를 순서대로 따라갈 수 있다. 배열처럼 인덱스로 건너뛰는 것은 불가능하고, 반드시 head부터 한 칸씩 이동해야 한다.

보물찾기에 비유할 수 있다. 각 쪽지에는 힌트와 함께 다음 쪽지가 있는 장소의 주소가 적혀 있다. 처음 쪽지(head)부터 시작해서 하나씩 따라가야만 원하는 쪽지에 도달할 수 있다. 중간 쪽지를 건너뛰고 바로 다섯 번째 쪽지로 이동하는 방법은 없다.

head → [10 | *] → [20 | *] → [30 | *] → None

배열과 연결 리스트의 핵심 차이는 삽입과 삭제에서 드러난다. 배열의 중간에 원소를 삽입하려면 그 뒤에 있는 원소들을 전부 한 칸씩 뒤로 밀어야 한다. O(n)이 필요하다. 연결 리스트는 앞뒤 노드의 참조만 바꾸면 된다. 참조 변경 자체는 O(1)이지만, 해당 위치까지 도달하는 데 O(n)이 필요하다.

인덱스 접근에서는 반대다. 배열은 인덱스를 계산해 바로 접근하므로 O(1)이다. 연결 리스트는 head부터 하나씩 따라가야 하므로 O(n)이다. Python의 list는 이름과 달리 연결 리스트가 아니라 동적 배열이다. 내부에 배열을 두고, 용량이 부족하면 더 큰 배열을 새로 할당해 복사한다. 덕분에 인덱스 접근이 O(1)이고 끝에서의 삽입·삭제가 평균 O(1)이다.

연결 리스트에는 세 가지 종류가 있다. 이 글에서 다루는 단일 연결 리스트는 각 노드가 다음 노드만 가리킨다. 이중 연결 리스트는 다음과 이전 노드 모두 가리킨다. Python의 collections.deque가 내부적으로 이중 연결 리스트로 구현되어 있다. 원형 연결 리스트는 마지막 노드가 다시 첫 번째 노드를 가리켜 순환 구조를 이룬다.

Python에서 연결 리스트 구현하기

표준 라이브러리

Python에는 단일 연결 리스트를 직접 다룰 수 있는 전용 라이브러리가 없다. collections.deque는 이중 연결 리스트 기반이지만, 노드 단위의 삽입·삭제·탐색 연산은 지원하지 않는다. 코딩 테스트에서 연결 리스트 구현이 요구될 때는 직접 만들어야 한다.

클래스로 직접 구현

연결 리스트를 단계적으로 쌓아 올리며 각 메서드의 동작 원리를 살펴본다.

Step 1: Node 클래스와 수동 연결

연결 리스트를 이루는 기본 단위는 Node다.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

노드 세 개를 수동으로 연결하고 순회해 보면 연결 리스트의 구조가 그대로 보인다.

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.next = node3

current = node1
while current:
    print(current.value)
    current = current.next

출력:

10
20
30

current가 None이 될 때 while 루프가 끝난다. 이 순회 과정을 자동화한 것이 LinkedList 클래스다.

Step 2: LinkedList 기본 클래스와 append/appendleft

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def appendleft(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

append는 head부터 마지막 노드까지 순회한 뒤 새 노드를 연결한다. 리스트 길이에 비례하므로 O(n)이다. appendleft는 새 노드의 next를 기존 head로 연결하고 head를 새 노드로 교체한다. 참조 변경 두 번으로 끝나므로 O(1)이다.

Step 3: __str__과 __contains__

매직 메서드를 추가하면 print(ll)과 20 in ll 같은 자연스러운 문법을 사용할 수 있다.

class LinkedList:
    ...

    def __str__(self):
        result = []
        current = self.head
        while current:
            result.append(str(current.value))
            current = current.next
        return ' -> '.join(result)

    def __contains__(self, value):
        current = self.head
        while current:
            if current.value == value:
                return True
            current = current.next
        return False
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.appendleft(5)

print(ll)
print(20 in ll)
print(99 in ll)

출력:

5 -> 10 -> 20 -> 30
True
False

Step 4: popleft와 pop

class LinkedList:
    ...

    def popleft(self):
        if self.head is None:
            raise IndexError("연결 리스트가 비어 있습니다")
        value = self.head.value
        self.head = self.head.next
        return value

    def pop(self):
        if self.head is None:
            raise IndexError("연결 리스트가 비어 있습니다")
        if self.head.next is None:
            value = self.head.value
            self.head = None
            return value
        prev = None
        current = self.head
        while current.next:
            prev = current
            current = current.next
        prev.next = None
        return current.value

popleft는 head를 다음 노드로 옮기는 것만으로 충분하다. O(1)이다. pop은 마지막 노드 바로 앞 노드(prev)를 추적하며 끝까지 순회해야 한다. O(n)이 필요하다. 이것이 단일 연결 리스트의 한계다. 이중 연결 리스트라면 마지막 노드에서 바로 이전 노드를 참조할 수 있어서 O(1)이 된다.

Step 5: insert와 remove

class LinkedList:
    ...

    def insert(self, index, value):
        if index == 0:
            self.appendleft(value)
            return
        new_node = Node(value)
        current = self.head
        for _ in range(index - 1):
            if current is None:
                raise IndexError("인덱스 범위를 초과했습니다")
            current = current.next
        if current is None:
            raise IndexError("인덱스 범위를 초과했습니다")
        new_node.next = current.next
        current.next = new_node

    def remove(self, value):
        if self.head is None:
            raise ValueError("연결 리스트가 비어 있습니다")
        if self.head.value == value:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                return
            current = current.next
        raise ValueError(f"{value}를 찾을 수 없습니다")

insert(2, 15)는 인덱스 1 노드까지 이동한 뒤, 그 뒤에 새 노드를 끼워 넣는다.

삽입 전:  [5] → [10] → [20] → [30]
                current↑
새 노드:  new_node = [15]
참조 변경:
  1. new_node.next = current.next   →  [15] → [20]
  2. current.next = new_node        →  [10] → [15]
삽입 후:  [5] → [10] → [15] → [20] → [30]

remove는 삭제할 노드의 이전 노드에서 그다음 노드로 참조를 우회한다. 삭제할 노드가 head라면 head를 다음 노드로 교체한다.

Step 6: reverse

class LinkedList:
    ...

    def reverse(self):
        prev = None
        current = self.head
        while current:
            ahead = current.next
            current.next = prev
            prev = current
            current = ahead
        self.head = prev

[1] → [2] → [3]을 뒤집는 과정을 단계별로 따라가면 다음과 같다.

초기:   prev=None   current=[1]   head=[1]→[2]→[3]
1단계:  ahead=[2]   [1].next=None   prev=[1]   current=[2]
2단계:  ahead=[3]   [2].next=[1]    prev=[2]   current=[3]
3단계:  ahead=None  [3].next=[2]    prev=[3]   current=None
결과:   head=[3]→[2]→[1]→None

ahead에 current.next를 먼저 저장해두지 않으면 current.next = prev 이후에 원래 다음 노드로 이동할 방법이 없어진다.

Step 7: 전체 코드

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def appendleft(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def __str__(self):
        result = []
        current = self.head
        while current:
            result.append(str(current.value))
            current = current.next
        return ' -> '.join(result)

    def __contains__(self, value):
        current = self.head
        while current:
            if current.value == value:
                return True
            current = current.next
        return False

    def popleft(self):
        if self.head is None:
            raise IndexError("연결 리스트가 비어 있습니다")
        value = self.head.value
        self.head = self.head.next
        return value

    def pop(self):
        if self.head is None:
            raise IndexError("연결 리스트가 비어 있습니다")
        if self.head.next is None:
            value = self.head.value
            self.head = None
            return value
        prev = None
        current = self.head
        while current.next:
            prev = current
            current = current.next
        prev.next = None
        return current.value

    def insert(self, index, value):
        if index == 0:
            self.appendleft(value)
            return
        new_node = Node(value)
        current = self.head
        for _ in range(index - 1):
            if current is None:
                raise IndexError("인덱스 범위를 초과했습니다")
            current = current.next
        if current is None:
            raise IndexError("인덱스 범위를 초과했습니다")
        new_node.next = current.next
        current.next = new_node

    def remove(self, value):
        if self.head is None:
            raise ValueError("연결 리스트가 비어 있습니다")
        if self.head.value == value:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                return
            current = current.next
        raise ValueError(f"{value}를 찾을 수 없습니다")

    def reverse(self):
        prev = None
        current = self.head
        while current:
            ahead = current.next
            current.next = prev
            prev = current
            current = ahead
        self.head = prev

종합 사용 예제:

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
print(ll)

ll.appendleft(5)
print(ll)

ll.insert(2, 15)
print(ll)

print(20 in ll)
print(99 in ll)

ll.remove(15)
print(ll)

popped = ll.pop()
print(popped)
print(ll)

ll.reverse()
print(ll)

출력:

10 -> 20 -> 30
5 -> 10 -> 20 -> 30
5 -> 10 -> 15 -> 20 -> 30
True
False
5 -> 10 -> 20 -> 30
30
5 -> 10 -> 20
20 -> 10 -> 5

연결 리스트의 주요 연산과 시간 복잡도

연산 설명 시간 복잡도
appendleft 앞에 삽입 O(1)
append 끝에 삽입 O(n)
popleft 앞에서 제거 O(1)
pop 끝에서 제거 O(n)
insert 임의 위치 삽입 O(n)
remove 값으로 삭제 O(n)
탐색 특정 값 찾기 O(n)

tail 포인터를 별도로 관리하면 append를 O(1)로 만들 수 있다. 큐 구현에서 rear를 두는 방식이 그것이다.

연산 Python list 연결 리스트
인덱스 접근 O(1) O(n)
앞에 삽입/삭제 O(n) O(1)
끝에 삽입/삭제 O(1) 평균 O(n)
중간 삽입 O(n) O(n) 탐색 + O(1) 삽입

Python list는 동적 배열이라 인덱스 접근과 끝 삽입에서 연결 리스트보다 빠르다. 연결 리스트는 앞에서의 삽입·삭제가 O(1)이라는 점에서 유리하다. 어떤 연산이 자주 일어나는지에 따라 자료구조를 선택해야 한다.

연결 리스트 활용 패턴

두 포인터 (Fast/Slow)

연결 리스트에서는 인덱스로 임의 위치에 접근할 수 없다. 대신 두 포인터를 서로 다른 속도로 움직여서 위치 관계를 파악하는 패턴이 자주 쓰인다.

중간 노드 찾기

slow 포인터는 한 번에 한 칸, fast 포인터는 한 번에 두 칸 이동한다. fast가 끝에 도달했을 때 slow는 중간에 있다. 리스트 길이를 미리 알지 못해도 한 번의 순회로 중간을 찾을 수 있다.

[1]→[2]→[3]→[4]→[5]에서 중간 노드를 찾는 과정을 따라가면 다음과 같다.

초기:   slow=[1]  fast=[1]
1단계:  slow=[2]  fast=[3]
2단계:  slow=[3]  fast=[5]
3단계:  fast.next=None → 종료  →  slow=[3]
def find_middle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

mid = find_middle(node1)
print(mid.value)

출력:

3

사이클 탐지 (Floyd's)

사이클이 있는 연결 리스트에서는 fast가 끝에 도달하지 못한다. slow와 fast가 같은 노드에서 만나는 순간 사이클이 있다고 판단한다.

사이클이 있으면 두 포인터가 반드시 만나는 이유는 fast가 slow를 뒤에서 따라오기 때문이다. slow가 한 칸씩, fast가 두 칸씩 이동하면 매 단계마다 fast가 slow에 한 칸씩 가까워진다. 결국 같은 위치에서 만나게 된다.

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c

print(has_cycle(a))

c.next = b
print(has_cycle(a))

출력:

False
True

연결 리스트 뒤집기

코딩 테스트에서 자주 출제되는 패턴이다. 구현 섹션의 reverse 메서드와 같은 원리를 독립 함수 형태로 만들면 LeetCode 206번 같은 문제에 바로 적용할 수 있다.

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        ahead = current.next
        current.next = prev
        prev = current
        current = ahead
    return prev
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3

result = []
current = reverse_linked_list(node1)
while current:
    result.append(str(current.value))
    current = current.next
print(' -> '.join(result))

출력:

3 -> 2 -> 1

정렬된 연결 리스트 병합

두 정렬된 연결 리스트를 하나의 정렬된 연결 리스트로 합치는 패턴이다. 병합 정렬의 merge 단계와 같은 원리다.

dummy 노드를 사용하는 이유는 결과 리스트의 첫 번째 노드를 처리하는 예외 코드를 없애기 위해서다. dummy.next를 결과의 head로 사용하면, 첫 번째 노드도 나머지와 동일한 방식으로 처리할 수 있다.

[1]→[3]→[5]와 [2]→[4]→[6]을 병합하는 과정을 따라가면 다음과 같다.

l1=[1], l2=[2]  →  1 <= 2,  current.next=[1]  →  l1=[3]
l1=[3], l2=[2]  →  3 > 2,   current.next=[2]  →  l2=[4]
l1=[3], l2=[4]  →  3 <= 4,  current.next=[3]  →  l1=[5]
l1=[5], l2=[4]  →  5 > 4,   current.next=[4]  →  l2=[6]
l1=[5], l2=[6]  →  5 <= 6,  current.next=[5]  →  l1=None
l1=None → 종료  →  current.next=[6]
결과: [1]→[2]→[3]→[4]→[5]→[6]
def merge_two_sorted(l1, l2):
    dummy = Node(0)
    current = dummy
    while l1 and l2:
        if l1.value <= l2.value:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 if l1 else l2
    return dummy.next
l1_head = Node(1)
l1_head.next = Node(3)
l1_head.next.next = Node(5)

l2_head = Node(2)
l2_head.next = Node(4)
l2_head.next.next = Node(6)

result = []
current = merge_two_sorted(l1_head, l2_head)
while current:
    result.append(str(current.value))
    current = current.next
print(' -> '.join(result))

출력:

1 -> 2 -> 3 -> 4 -> 5 -> 6

연습 문제

초급

번호 문제 난이도 링크 핵심 접근
1406 에디터 실버 2 https://www.acmicpc.net/problem/1406 커서 좌우를 두 스택으로 관리
1158 요세푸스 문제 실버 4 https://www.acmicpc.net/problem/1158 원형 구조 시뮬레이션
2 Add Two Numbers Medium https://leetcode.com/problems/add-two-numbers/ 자릿수별 덧셈 + carry

중급

번호 문제 난이도 링크 핵심 접근
21 Merge Two Sorted Lists Easy https://leetcode.com/problems/merge-two-sorted-lists/ dummy 노드로 병합
206 Reverse Linked List Easy https://leetcode.com/problems/reverse-linked-list/ prev/current/next 포인터
141 Linked List Cycle Easy https://leetcode.com/problems/linked-list-cycle/ Floyd's fast/slow

 

'CodingTest > 자료구조-알고리즘' 카테고리의 다른 글

[DFS & BFS]  (0) 2026.03.31
[재귀 & 완전 탐색] & [백트래킹]  (0) 2026.03.24
해시 (Hash)  (1) 2026.03.17
큐 (Queue)  (1) 2026.03.17
스택 (Stack)  (0) 2026.03.17
CodingTest/자료구조-알고리즘 관련 글
더 보기

티스토리툴바