연결 리스트 (Linked List)

데이터를 한 덩어리로 붙여 두는 배열과 달리, 값 하나하나를 노드라는 작은 상자에 담고 "다음 상자는 여기야"라는 포인터(주소)로 줄줄이 이어 붙인 자료구조. 상자들은 메모리 어디에 흩어져 있어도 상관없다.

1. 직접 만져 보기 — 싱글 링크드 리스트

각 노드는 [ 값 | next ] 두 칸짜리 상자다. next 칸의 화살표가 다음 노드를 가리키고, 마지막 노드는 null(⏚)을 가리킨다. 노드를 클릭해 선택한 뒤 삽입·삭제해 보자.

2. 배열은 왜 앞쪽 삽입이 느릴까

배열은 메모리에 빈틈 없이 딱 붙어 있다. 덕분에 arr[i]는 "시작 주소 + i × 원소크기"로 단번에 계산된다(O(1)). 하지만 맨 앞에 값을 넣으려면 뒤의 원소를 전부 한 칸씩 밀어야 한다.

3. 시간 복잡도 비교

4. 싱글 vs 더블 vs 원형

5. 코드 — 파이썬 싱글 연결 리스트

class Node:
    def __init__(self, value):
        self.value = value
        self.next  = None          # 다음 노드 참조 (없으면 None)

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

    def push_front(self, value):        # O(1)
        node = Node(value)
        node.next = self.head          # 새 노드가 옛 head를 가리킴
        self.head = node               # head를 새 노드로 갱신
        self.size += 1

    def insert_after(self, node, value):  # O(1) — node를 이미 알 때
        new = Node(value)
        new.next  = node.next
        node.next = new
        self.size += 1

    def remove(self, value):           # O(n) — 앞 노드를 찾아야
        prev, cur = None, self.head
        while cur:
            if cur.value == value:
                if prev: prev.next = cur.next
                else:    self.head = cur.next
                self.size -= 1
                return True
            prev, cur = cur, cur.next
        return False

    def find(self, value):             # O(n) — 랜덤 접근 불가
        cur = self.head
        while cur:
            if cur.value == value: return cur
            cur = cur.next
        return None

6. 어디에 쓰이나