자료구조 기초 - 연결 리스트(Linked List)

연결 리스트란?

배열은 연속된 공간에 데이터를 저장하지만, 연결 리스트는 데이터를 떨어진 공간에 저장하면서 서로 연결해두는 자료구조입니다.

말 그대로 데이터가 연결(link)되어 있는 리스트(list)입니다.

연결 리스트의 구조

연결 리스트는 노드(Node) 라는 단위로 구성됩니다. 각 노드는 두 가지 정보를 가집니다:

• 데이터(Data): 실제 저장할 값
• 다음 노드를 가리키는 포인터(Next)

[Data|Next] -> [Data|Next] -> [Data|Next] -> None

이런 구조 덕분에 연결 리스트는 데이터를 어디서든 쉽게 추가하거나 제거할 수 있습니다.

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List): 한 방향으로만 연결되어 있습니다.
2. 이중 연결 리스트(Doubly Linked List): 앞뒤로 모두 연결되어 있어 양방향 이동이 가능합니다.
3. 원형 연결 리스트(Circular Linked List): 마지막 노드가 처음 노드를 가리켜서 원처럼 연결되어 있습니다.

연결 리스트 예시 (Python)

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

연결 리스트의 시간복잡도

작업	시간복잡도	설명
접근 (Access)	O(n)	인덱스로 접근이 불가능하므로 처음부터 차례대로 찾아야 합니다.
검색 (Search)	O(n)	원하는 데이터를 찾을 때도 처음부터 하나씩 확인해야 합니다.
삽입 (Insert)	O(1)*	삽입 위치의 노드를 알고 있다면 바로 연결만 하면 됩니다.
삭제 (Delete)	O(1)*	삭제할 노드를 알고 있다면 포인터만 끊으면 됩니다.

삽입 또는 삭제하려는 위치를 알고 있다는 전제 하에서 빠르게 동작할 수 있습니다.

배열과 연결 리스트 비교

항목	배열	연결 리스트
메모리 구조	연속적	비연속적 (포인터로 연결)
접근 속도	빠름 (O(1))	느림 (O(n))
삽입/삭제	느림 (O(n))	빠름 (O(1), 위치 알고 있을 때)
크기 조절	어려움	자유로움

실생활 예시로 이해하기

연결 리스트는 사슬 체인과 비슷합니다. 각각의 고리가 하나의 노드이고, 고리 사이를 연결하는 고리가 포인터 역할을 합니다. 중간에 새로운 고리를 끼우거나 기존 고리를 제거할 때, 전체를 다시 만들 필요 없이 연결만 바꾸면 되기 때문에 구조 변경이 매우 유연합니다.

마무리 정리

항목	연결 리스트
데이터 접근	느림 (O(n)) - 인덱스로 직접 접근이 불가능하여 처음부터 순차 탐색이 필요합니다.
삽입/삭제	빠름 (O(1), 특정 위치 알고 있을 때) - 포인터 연결만 바꾸면 되므로 효율적입니다.
크기 조절	자유로움 - 노드를 추가하거나 제거하면서 구조를 쉽게 변경할 수 있습니다.
검색 효율	낮음 - 원하는 데이터를 찾을 때 선형 탐색이 필요하여 시간이 오래 걸릴 수 있습니다.
구현 복잡도	비교적 높음 - 포인터를 다루어야 하므로 구현이 배열보다 어렵습니다.