연결 리스트

🔥 매회 출제 (priority 3)

🌱 왜 배우나

꽉 찬 줄의 맨 앞에 한 명을 끼워 넣으려면 뒤에 서 있던 모든 사람이 한 칸씩 움직여야 한다. 배열(값을 한 줄로 나란히 저장하는 방식)이 딱 이 모습이다. 중간에 뭔가를 넣거나 빼려면 뒤 데이터를 전부 밀어야 하니 느리다.

연결 리스트는 다른 방법을 쓴다. 값 옆에 “다음 친구는 저기 있어”라는 쪽지를 붙여 두는 것이다. 값이 메모리(컴퓨터가 값을 저장해 두는 공간) 여기저기에 흩어져 있어도, 쪽지만 따라가면 순서대로 읽을 수 있다. 새 값을 끼우거나 뺄 때도 쪽지 두 장만 고쳐 쓰면 된다.

📖 핵심 개념

연결 리스트(Linked List)는 노드를 포인터로 이어 붙인 자료구조다. 자료구조란 데이터를 저장하고 꺼내는 방식을 말한다.

노드는 값 하나를 담는 칸이다. 포인터는 “다음 노드가 어디에 있는지”를 적어둔 주소표 같은 것이다. 메모리가 연속될 필요가 없다.

삽입과 삭제는 쪽지(포인터) 몇 개만 바꿔 쓰면 된다. 그래서 O(1)로 끝난다. O(1)은 데이터가 아무리 많아도 걸리는 시간이 일정하다는 뜻이다. 반대로 “n번째 값을 꺼내줘”는 처음부터 쪽지를 하나씩 따라가야 한다. 그래서 O(n)이 걸린다. n은 데이터 개수다.

시험에서는 C 구조체(여러 값을 묶어 하나의 타입처럼 다루는 문법)와 포인터로 된 코드를 주고, 순회 결과를 묻는다. 순회란 처음부터 끝까지 차례로 방문하는 동작이다.

🔍 시각화

단일 연결 리스트 구조:

head
  │
  ▼
┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
│ 데이터│    │ 데이터│    │ 데이터│    │ 데이터│
│  35  │    │  42  │    │  11  │    │  21  │
├──────┤    ├──────┤    ├──────┤    ├──────┤
│ next ─┼───▶│ next ─┼───▶│ next ─┼───▶│ next ─┼───▶ NULL
└──────┘    └──────┘    └──────┘    └──────┘
  노드1       노드2       노드3       노드4

맨 앞에 새 노드 삽입:

  ┌──────┐
  │  새  │
  │  5   │
  ├──────┤
  │ next ─┼──┐
  └──────┘  │    head 가 여기를 가리키도록 변경
            ▼
         기존 노드1 → 노드2 → ...

↔️ 이웃 개념 구분

• 배열 vs 연결 리스트: 배열은 번호로 바로 꺼내서 조회가 빠름. 연결 리스트는 쪽지를 따라가야 해서 조회는 느리지만 삽입·삭제가 빠름.
• 단일 vs 이중 연결 리스트: 단일은 앞→뒤 한 방향. 이중은 앞↔뒤 양방향으로 움직일 수 있음.

🔑 핵심 용어

• 노드(Node): 값 한 칸. 데이터와 “다음 노드의 주소(next 포인터)“를 함께 담는다
• head: 리스트의 시작점. 첫 노드를 가리키는 포인터
• →: 포인터로 구조체 안의 값을 꺼내는 연산자. p->data는 (*p).data와 같다
• 단일 연결 리스트(Singly Linked List): next 한 방향으로만 이동
• 이중 연결 리스트(Doubly Linked List): prev(이전)와 next(다음) 양쪽으로 이동
• 원형 연결 리스트(Circular Linked List): 마지막 노드의 next가 다시 head를 가리켜 고리 모양으로 연결

✅ 스스로 가르쳐보기

연결 리스트를 처음 들어보는 친구에게 설명한다면 어떻게 말하시겠어요? 일상 속 물건이나 장면에 빗댄 본인만의 비유로 한 문장 정의를 만들어 보세요.

체크포인트 — 아래를 말로 풀어 설명할 수 있는지 확인해 보세요.

• 배열과 연결 리스트의 삽입·삭제 속도가 왜 다른지
• p = p->next가 포인터를 따라간다는 말이 실제로 무슨 동작인지
• 맨 앞에 끼워 넣을 때 newNode->next = head를 먼저 해야 하는 이유
• 순회가 NULL 에서 멈추는 이유

🎯 기출 포인트

• 2025-1회: C 연결 리스트 순회 코드 추적. 출력 결과 35421 (노드 data 순서대로)
• 2025-2회: 연결 리스트 삽입 후 순회. 출력 3 1 2. 포인터 재연결 순서를 잘 따라가야 한다
• 2024-2회: 구조체 포인터 + 연결 리스트 혼합 신유형. -> 와 역참조 * 구분이 관건
• 주의: next 포인터가 재할당되는 순서를 반드시 한 줄씩 추적한다

🔗 연결 개념

• pg-data-structure-001
• C언어 포인터 기초
• pg-language-005