Linked Lists & Pointer Logic

1. Overview

연결 리스트와 포인터 논리(Linked Lists & Pointer Logic)는 메모리 곳곳에 흩어진 파편들을 포인터(화살표)라는 보이지 않는 실로 꿰어, 동적으로 늘었다 줄었다 하는 자유로운 데이터 사슬을 만드는, 배열의 경직성을 부수는 첫 번째 혁명적 자료구조입니다.

학습자는 노드(Node) 하나가 실제 데이터(Value)와 다음 노드의 메모리 주소(Next Pointer)를 쌍으로 들고 다니는 단순 연결 리스트(Singly Linked List)의 물리적 구조를 뜯어봅니다. 나아가 앞뒤 자유로이 탐색하는 이중 연결 리스트(Doubly Linked List), 마지막 노드가 첫 번째 노드를 가리키는 순환 연결 리스트(Circular)를 거쳐, 포인터 논리의 가장 어두운 면인 **메모리 누수(Memory Leak)**와 댕글링 포인터(Dangling Pointer)의 공포까지 해부하여 C/C++ 로우레벨 시스템 프로그래밍의 근육을 단련합니다.

2. Scope & Boundaries

In-Scope

• 단순/이중/순환 연결 리스트 (List Variants): 노드 구조체(struct Node), 헤드/테일 포인터, 삽입/삭제/탐색 연산의 포인터 조작.
• 포인터 패러다임 (Pointer Logic): next = next->next 포인터 추적, 더미 헤드(Sentinel Node) 패턴, 포인터 반전(Pointer Reversal).
• 메모리 안전성 (Memory Safety): 메모리 누수(Memory Leak), 댕글링 포인터(Dangling Pointer), free() 순서의 참사, 스마트 포인터(C++ unique_ptr).
• 고전 문제 패턴 (Classic Problems): Floyd's 사이클 탐지(Tortoise and Hare), 역전(Reverse), 두 리스트 병합(Merge), Nth from End 투 포인터.

Out-of-Scope

• 스킵 리스트(Skip List): 다단계 포인터 레이어를 이용한 O(log n) 탐색 구조 $\rightarrow$ 04-02. Core Data Structures 영역.
• 가비지 컬렉션(GC)을 통한 자동 메모리 관리: JVM이나 CPython 인터프리터 레벨의 참조 카운팅 메커니즘 $\rightarrow$ 05-03. Runtime Memory Management 영역.

Boundaries

• Array vs Linked List (04-01-01): 배열은 "미리 방을 100개 예약해두는 연속 호텔"로 arr[k]가 O(1)이지만 중간 방을 빼면 뒤를 다 이사(Shift)해야 합니다. 연결 리스트는 "빈 자리 어디든 방을 잡고 현관 화살표(포인터)만 바꾸는 포인터 이사"라 중간 삽입/삭제가 O(1)이지만, k번째 방을 찾으려면 1번 방부터 k번 화살표를 따라가야 하는(O(k)) 근본적 트레이드오프입니다.

3. Counterexample

• 포인터 순서 역전 실수와 리스트 고아화 (The Lost Pointer): 단순 연결 리스트에서 중간 노드를 삭제할 때 prev->next = node->next; free(node); 순서가 아니라 free(node); prev->next = node->next; 순서로 실수하는 초보 버그. free(node) 직후 node->next는 이미 해제된 메모리를 가리키는 댕글링 포인터가 되어 읽는 순간 미정의 동작(Undefined Behavior)이 터집니다. prev->next가 업데이트되지 못해 삭제 이후의 모든 노드들이 메모리 공간에 떠도는 고아(Orphan)가 되어 절대 도달 불가능(Unreachable)한 누수(Leak) 상태가 됩니다.
• 사이클 미탐지와 무한 루프 (Cycle Detection Failure): 연결 리스트의 끝을 탐색하는 while(node != null) 루프. 만약 실수로 마지막 노드의 next가 중간 노드를 가리키도록 포인터가 잘못 연결된 순환(Cycle)이 생기면, 루프가 영원히 종료되지 않아 CPU가 무한 스핀(Infinite Spin)을 태우며 서버 프로세스가 100% CPU를 먹고 응답 불능 상태가 됩니다.

4. Prerequisites

• 포인터 개념 (Basic): 변수의 값이 아닌 '메모리 주소'를 저장하는 포인터 변수의 개념과 역참조(*ptr)를 알아야 합니다. (03-03-01 Virtual Memory)
• 동적 메모리 할당 (Basic): malloc()/free()(C) 또는 new/delete(C++)로 힙 메모리를 요청하고 반납하는 수동 메모리 관리의 책임을 이해해야 합니다.

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 화살표 꿰매기와 포인터 3단계 조작, 단순 연결 리스트 (Singly Linked List)

• Why to Learn: 데이터베이스의 언두 로그(Undo Log), 브라우저 방문 기록(History Stack), OS의 빈 메모리 블록 관리 등 "동적으로 크기가 변하는 모든 시스템"의 밑바닥에 깔린 포인터 꿰매기의 근육을 만들기 위함입니다.
• What to Learn:
  • Concepts: 노드(Node) 구조체, 헤드(Head) 포인터, next 포인터 체인, 더미 헤드(Sentinel) 패턴.
  • Skills: 삽입(Head/Tail/Middle Insert), 삭제(Node Delete), 역방향 탐색 불가 한계.
  • Tools: gdb 포인터 체인 추적, Valgrind 메모리 누수 감지.
  • Trade-offs: 연결 리스트는 중간 삽입/삭제가 포인터 2개만 바꾸는 O(1) 쾌속이며 크기가 동적이어서 선언 시 크기를 정할 필요가 없는 극강의 유연성이 있지만, 데이터 하나를 저장할 때마다 next 포인터 값(8Byte, 64bit 시스템)을 추가로 낭비하는 메모리 오버헤드와, k번째 요소 접근이 O(k)라 배열처럼 무작위 접근이 없는 태생적 한계.
• How to Learn:
  • 1단계: 노드 C 구조체 struct Node { int data; struct Node *next; };를 선언하고, malloc(sizeof(Node))로 힙에 방 3개를 잡아 A->B->C->NULL 사슬을 손수 포인터로 꿰맵니다. 출력 루프 while(node) { print(node->data); node=node->next; } 를 해부합니다.
  • 2단계: 노드 B와 C 사이에 새 노드 X를 삽입하는 연산을 뜯어봅니다. 핵심은 무조건 new_node->next = B->next (=C)를 먼저 연결한 뒤 B->next = new_node로 B의 화살표를 옮기는 2단계 순서로, 순서가 반대가 되면 C를 영구히 잃어버리는 궤적입니다.
• Implement: 파이썬 Node 클래스와 SinglyLinkedList 클래스 구현. append(v), insert_after(target_v, new_v), delete(v), to_list() 메서드 구현 후 단위 테스트: 빈 리스트에서 [1,2,3] 삽입 후 중간(2) 삭제 시 [1,3] 검증, Head 앞에 새 노드 삽입 후 헤드 갱신 검증.

Recommended

Core Topic 02: 양방향 화살표와 자기 참조의 뱀, 이중 및 순환 리스트 (Doubly & Circular)

• Why to Learn: LRU(가장 최근 미사용) 캐시의 구현체, 텍스트 에디터의 커서 이동(앞뒤 문자 탐색), OS의 프로세스 실행 큐가 왜 이중 연결 리스트(DoublyLL)로 구현되는지 역방향 포인터의 필요성을 꿰기 위함입니다.
• What to Learn:
  • Concepts: 이중 연결 리스트(Doubly LL, prev/next 쌍), 순환 연결 리스트(Circular LL, tail->next = head), 더미 헤드/테일(Sentinel) 패턴.
  • Skills: O(1) 삭제를 위한 노드 포인터 직접 조작(역방향 포인터 덕분), Python collections.deque 내부 구조.
  • Tools: LRU Cache 구현 연습.
  • Trade-offs: 이중 연결 리스트는 prev 포인터를 추가로 유지하여 역방향 탐색과 O(1) 삭제(노드를 쥐고 있으면)를 달성하지만, 노드 하나마다 prev/next 두 개의 포인터(16Byte)를 쥐어야 하므로 단순 리스트 대비 메모리 오버헤드가 2배인 트레이드오프.
• How to Learn:
  • 1단계: 이중 연결 리스트: 이중 리스트의 중간 노드 B를 삭제할 때, B->prev->next = B->next (B의 앞 노드가 B를 건너뜀)와 B->next->prev = B->prev (B의 뒤 노드가 B를 건너뜀) 두 줄로 O(1) 삭제가 완성되는 포인터 쌍 조작을 해부합니다.
  • 2단계: 순환 리스트: 원형 버퍼(Ring Buffer)나 OS 라운드 로빈 스케줄러는 마지막 노드의 next가 처음 노드를 무는 형태. 탐색 루프 종료 조건이 node != head임을 주의해야 하는 NULL 아닌 순환 종료 조건을 뜯어봅니다.
• Implement: 파이썬 DoublyLinkedList 클래스 구현 + LRU Cache(용량 3) 적용. get(key) 시 캐시 히트면 해당 노드를 리스트 맨 앞으로 이동(Head에 재삽입), put(key,val) 시 캐시 초과면 Tail 노드(가장 오래된) 즉각 삭제. LRU 메커니즘을 이중 리스트 포인터 조작으로 O(1) 구현 후 접근 시퀀스 [1,2,3,1,4] (cap=3)로 캐시 히트/미스 로그 증명.

Practical

Core Topic 03: 공중 분해와 댕글링 지뢰, 메모리 안전성 (Memory Safety & Smart Pointers)

• Why to Learn: C/C++에서 malloc/free를 손수 짜는 모든 시스템 프로그래밍에서, 포인터 해제(Free) 순서 실수 하나로 수천만 달러짜리 서버가 몇 달 동안 재현 불가능한 버그에 시달리는 메모리 안전성의 공포를 제어하기 위해서입니다.
• What to Learn:
  • Concepts: 메모리 누수(Memory Leak), 댕글링 포인터(Dangling Pointer), 더블 프리(Double Free), Use-After-Free(UAF).
  • Skills: C++ unique_ptr, shared_ptr/weak_ptr 참조 카운팅, Rust 소유권(Ownership) 모델.
  • Tools: Valgrind --leak-check=full, AddressSanitizer(ASan).
• How to Learn:
  • 1단계: 리스트를 순회하며 모든 노드를 삭제하는 루프 while(head) { Node* tmp=head; head=head->next; free(tmp); } 의 안전한 순서를 해부합니다. tmp에 현재 노드를 백업 후 head를 다음으로 전진시킨 뒤에야 free(tmp)를 때리는 순서가 왜 필수인지, 역순(free 후 head 접근)이 어떻게 UAF를 만드는지 증명합니다.
  • 2단계: C++ unique_ptr<Node> 스마트 포인터는 스코프를 벗어나면 자동으로 소멸자(~Node())를 호출하여 free()를 대신하므로, 프로그래머가 free()를 절대 잊을 수 없는 RAII(Resource Acquisition Is Initialization) 원칙을 뜯어봅니다.
• Implement: 파이썬 weakref 모듈 활용 시뮬레이션. 순환 참조(A→B→A) 노드 구조에서 A.next = B; B.prev = A (이중 강참조)를 구성하면 del 후에도 GC에서 미회수(누수)됨을 gc.collect() 후 gc.garbage 리스트로 증명. 이를 B.prev = weakref.ref(A)(약한 참조)로 바꿔 사이클이 끊기며 GC가 정상 회수하는 방어 코드 비교.

Advanced

Core Topic 04: 거북이와 토끼의 우주 충돌, 플로이드 사이클 알고리즘 (Floyd's Tortoise & Hare)

• Why to Learn: 코딩 인터뷰의 최애 문제이자 OS 메모리 누수 탐지, DB 락 사이클(Deadlock) 감지에도 쓰이는, 공간 O(1)이라는 불가능에 도전하는 두 포인터 알고리즘의 수학적 아름다움을 꿰기 위함입니다.
• What to Learn:
  • Concepts: 플로이드(Floyd) 사이클 탐지, Tortoise(느린, 1칸씩), Hare(빠른, 2칸씩), 만남 지점의 수학적 증명.
  • Skills: 사이클 시작점(Entry Node) 역산, 사이클 길이(Length) 계산.
  • Tools: LeetCode #142 Linked List Cycle II 풀이 패턴.
  • Trade-offs: 방문한 노드를 해시 셋(HashSet)에 저장하는 O(n) 공간 방법은 직관적이지만 n개의 포인터를 메모리에 쟁여야 하는 반면, 플로이드는 단 2개의 포인터만으로 O(1) 공간에 O(n) 시간에 사이클을 탐지합니다.
• How to Learn:
  • 1단계: slow = slow.next, fast = fast.next.next 를 동시에 전진. 리스트에 사이클이 있으면, Fast(토끼)가 사이클 안에서 Slow(거북이)를 결국 따라잡는다는(같은 노드에서 만난다) 수학적 불변량을 해부합니다.
  • 2단계: 만남 지점에서 slow를 다시 head로 보내고, fast는 그 자리에 두고 1칸씩 같이 전진하면, 두 포인터가 다시 만나는 점이 정확히 사이클의 시작(진입) 노드임을 수학적으로 증명(비트 연산 거리 방정식 풀이)합니다.
• Implement: 파이썬 리스트 노드로 사이클 포함 연결 리스트 수동 생성 ([1,2,3,4,5]에서 5의 next를 3번 노드에 연결). floyd_detect(head) 함수가 Tortoise/Hare 투 포인터로 만남점을 찾고, 만남 후 Head reset으로 사이클 시작(3번 노드)을 정확히 출력하는 알고리즘 증명.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Engineering Foundations / Computing Foundations (Pointers) — Structural context.
• [P1] CS2023 - SDF/Fundamental Data Structures (Linked Lists) — Core requirements.

Secondary

• [Understanding and Using C Pointers] Richard Reese — Practical pointer guide.
• [Algorithms in C, Parts 1-4] Robert Sedgewick — Linked data implementation.

Industry

• [Kernel.org: Introduction to the Linux Kernel's Linked List] — Real-world gold standard.
• [Microsoft: Debugging Memory Leaks (Windows Developers)] — Applied pointer safety.

9. Final Checklist

Primary

• 특정 노드의 '주소'를 안다는 것과 그 주소에 담긴 '데이터'를 읽는 것의 물리적 차이를 설명 가능한가? (P1)
• 연결 리스트의 '중간 삽입'이 배열과 달리 주변 데이터를 물리적으로 밀어낼 필요가 없는 이유를 입증할 수 있는 가? (P1)

Secondary

• **참조 지역성(Reference Locality)**이 결여된 연결 리스트가 왜 CPU 캐시 효율을 떨어뜨려 시스템을 느리게 만드는지 소통 가능한가?
• 노드를 삭제한 후에도 포인터 변수를 초기화하지 않았을 때 발생하는 'Dangling Pointer' 시나리오를 도출할 수 있는 가?

Industry

• 임베디드 시스템 설계 시, 메모리 파편화를 막기 위해 '정적 노드 풀(Node Pool)'을 사전에 할당하여 연결 리스트를 운영하는 방안을 제안할 수 있는 가? (SFIA)
• C++의 std::unique_ptr와 같은 도구가 물리적 메모리 소유권(Ownership)을 어떻게 강제하여 안전성을 확보하는지 기술할 수 있는 가?