연결 리스트 (Linked List)

개념

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조

메모리 상에서 불연속적으로 저장되며, 포인터로 연결

---

시간복잡도

연산	시간복잡도	설명
접근	O(n)	처음부터 순차적으로 탐색
탐색	O(n)	처음부터 끝까지 순회 필요
삽입	O(1)	포인터만 변경 (위치를 알 때)
삭제	O(1)	포인터만 변경 (위치를 알 때)

---

특징

장점

• 동적 크기: 필요할 때마다 메모리 할당 가능
• 효율적인 삽입/삭제: 중간에 삽입/삭제 시 O(1) (위치를 알 때)
• 메모리 효율: 필요한 만큼만 사용

단점

• 느린 접근: 인덱스로 직접 접근 불가, O(n) 소요
• 추가 메모리: 포인터 저장을 위한 메모리 필요
• 캐시 비효율: 메모리가 불연속적이라 캐시 미스 발생

---

종류

1. 단일 연결 리스트 (Singly Linked List)

각 노드가 다음 노드만 가리킴

[data|next] -> [data|next] -> [data|next] -> None

2. 이중 연결 리스트 (Doubly Linked List)

각 노드가 이전 노드와 다음 노드를 모두 가리킴

None <- [prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> None

3. 원형 연결 리스트 (Circular Linked List)

마지막 노드가 첫 노드를 가리킴

[data|next] -> [data|next] -> [data|next] ┐
   ↑                                       │
   └───────────────────────────────────────┘

---

Python 구현

1. 노드 클래스 정의

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

---

2. 단일 연결 리스트 구현

class LinkedList:
    def __init__(self):
        self.head = None
 
    # 리스트 끝에 노드 추가 - O(n)
    def append(self, data):
        new_node = Node(data)
 
        if not self.head:
            self.head = new_node
            return
 
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
 
    # 리스트 맨 앞에 노드 추가 - O(1)
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
 
    # 특정 위치에 노드 삽입 - O(n)
    def insert_after(self, prev_node, data):
        if not prev_node:
            print("이전 노드가 존재하지 않습니다")
            return
 
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node
 
    # 특정 값을 가진 노드 삭제 - O(n)
    def delete(self, key):
        current = self.head
 
        # 삭제할 노드가 head인 경우
        if current and current.data == key:
            self.head = current.next
            return
 
        # 삭제할 노드 찾기
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
 
        # 노드를 찾지 못한 경우
        if not current:
            return
 
        # 노드 삭제
        prev.next = current.next
 
    # 리스트 출력 - O(n)
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")
 
    # 리스트 탐색 - O(n)
    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

---

3. 사용 예시

# 연결 리스트 생성
ll = LinkedList()
 
# 노드 추가
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
ll.print_list()  # 0 -> 1 -> 2 -> 3 -> None
 
# 노드 삽입
node = ll.head.next  # 1번 노드
ll.insert_after(node, 1.5)
ll.print_list()  # 0 -> 1 -> 1.5 -> 2 -> 3 -> None
 
# 노드 삭제
ll.delete(1.5)
ll.print_list()  # 0 -> 1 -> 2 -> 3 -> None
 
# 노드 탐색
print(ll.search(2))  # True
print(ll.search(5))  # False

---

자주 나오는 문제 유형

1. 연결 리스트 뒤집기 (Reverse)

문제: 연결 리스트를 역순으로 뒤집기

def reverse_list(head):
    prev = None
    current = head
 
    while current:
        # 다음 노드 임시 저장
        next_node = current.next
        # 현재 노드의 포인터 역전
        current.next = prev
        # prev와 current를 한 칸씩 이동
        prev = current
        current = next_node
 
    return prev  # 새로운 head
 
# 시간복잡도: O(n)
# 공간복잡도: O(1)

핵심: 포인터 방향을 하나씩 역전시키면서 순회

---

2. 중간 노드 찾기 (Fast & Slow Pointer)

문제: 연결 리스트의 중간 노드 찾기

def find_middle(head):
    slow = fast = head
 
    # fast는 2칸, slow는 1칸씩 이동
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    return slow  # slow가 중간 노드
 
# 시간복잡도: O(n)
# 공간복잡도: O(1)

핵심: 빠른 포인터와 느린 포인터를 사용한 투 포인터 기법

---

3. 사이클 탐지 (Floyd’s Cycle Detection)

문제: 연결 리스트에 사이클이 있는지 확인

def has_cycle(head):
    if not head:
        return False
 
    slow = fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
        # 두 포인터가 만나면 사이클 존재
        if slow == fast:
            return True
 
    return False
 
# 시간복잡도: O(n)
# 공간복잡도: O(1)

핵심: 거북이와 토끼 알고리즘 - 사이클이 있으면 반드시 만남

---

4. 두 연결 리스트 합치기 (Merge Two Sorted Lists)

문제: 정렬된 두 연결 리스트를 하나로 합치기

def merge_two_lists(l1, l2):
    # 더미 노드 생성
    dummy = Node(0)
    current = dummy
 
    # 두 리스트를 비교하며 합치기
    while l1 and l2:
        if l1.data <= l2.data:
            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
 
# 시간복잡도: O(n + m)
# 공간복잡도: O(1)

핵심: 더미 노드를 사용해 코드 간결화

---

5. N번째 노드 삭제 (Remove Nth Node from End)

문제: 뒤에서 N번째 노드를 삭제

def remove_nth_from_end(head, n):
    dummy = Node(0)
    dummy.next = head
 
    # fast를 n칸 먼저 이동
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
 
    # fast와 slow를 함께 이동
    while fast.next:
        fast = fast.next
        slow = slow.next
 
    # slow.next가 삭제할 노드
    slow.next = slow.next.next
 
    return dummy.next
 
# 시간복잡도: O(n)
# 공간복잡도: O(1)

핵심: 두 포인터를 N칸 간격으로 유지하며 이동

---

추천 연습 문제

기초

• 백준 1406번 - 에디터
• 백준 5397번 - 키로거

중급

• LeetCode 206 - Reverse Linked List
• LeetCode 141 - Linked List Cycle
• LeetCode 21 - Merge Two Sorted Lists
• LeetCode 19 - Remove Nth Node From End

고급

• LeetCode 23 - Merge k Sorted Lists
• LeetCode 143 - Reorder List

---

핵심 요약

개념	설명
구조	노드(데이터 + 포인터)가 연결된 형태
삽입/삭제	위치를 알 때 O(1), 찾아야 하면 O(n)
주요 기법	투 포인터, 더미 노드, 재귀
vs 배열	동적 크기 vs 빠른 접근

---

배열 vs 연결 리스트

특성	배열	연결 리스트
메모리	연속적	불연속적
접근	O(1)	O(n)
삽입/삭제	O(n)	O(1) (위치 알 때)
크기	고정 (Python은 동적)	동적
캐시	효율적	비효율적

---

주의사항

1. Null 체크 필수

# NoneType 에러 방지
if node and node.next:
    # 안전한 접근
    value = node.next.data

2. 더미 노드 활용

# head 변경 처리를 단순화
dummy = Node(0)
dummy.next = head
# ... 작업
return dummy.next

3. 포인터 순서 주의

# 잘못된 순서
current.next = new_node
new_node.next = current.next  # 이미 변경됨!
 
# 올바른 순서
new_node.next = current.next
current.next = new_node