연결 리스트(Node)

 

Node(노드)

노드는 연결 리스트의 기본 단위입니다.

단순히 '값 하나'가 아니라 값 + 다음 노드(next) 정보를 함께 가진 작은 객체입니다.

class ListNode {
  val: number;
  next: ListNode | null;
}

 

즉, 노드 하나는 이렇게 생겼습니다

┌───────────────┬──────────────────────┐
│     val       │        next          │
├───────────────┴──────────────────────┤
│ ex) 3         │ 주소: Node(4) 위치   │
└───────────────────────────────────────┘

• 그래서 노드가 하나만 있어도, 그 노드의 next가 다른 노드를 가리키고 있다면 리스트는 자동으로 연결됩니다.

 

예

노드(2) = { val:2, next:노드(4) }

• 2 노드를 어디에 연결하는 순간 뒤에 있는 4 노드도 자동으로 따라옵니다.

 

---

 

연결 리스트는 어떻게 생겼을까?

배열과 다르게 인덱스 구조가 아니라, 노드끼리 화살표(next)로 연결된 형태입니다.

[1] → [2] → [3] → [4] → null

• 첫 노드를 head라고 부르며, head에서 next를 따라가며 이동합니다.

 

---

 

배열 vs 연결 리스트

비교	항목 배열(Array)	연결 리스트(Linked List)
메모리 구조	연속된 공간	흩어져 있어도 됨 (next로 연결)
접근 속도	O(1) 랜덤 접근	O(n) next 따라감
삽입/삭제	O(n) (밀기/당기기 필요)	O(1) (link만 수정)

 

연결 리스트가 문제에서 자주 쓰이는 이유는 중간 노드 수정이 매우 빠르기 때문입니다.

 

---

노드를 삭제하는 원리

배열처럼 "지우기"가 있는 게 아니라, 연결 관계(next)를 바꿔서 노드를 리스트에서 끊어버립니다.

 

삭제 전

prev → cur → next

• 삭제 후 (prev.next = cur.next)

prev ─────────→ next

• 그러면 cur는 아무도 가리키지 않기 때문에 리스트에서 사라지게 됩니다.

 

---

예시 1: 가운데 노드 삭제 (deleteMiddle)

연결 리스트의 가운데 노드를 삭제하라.

1 → 2 → 3 → 4 → 5

결과:

1 → 2 → 4 → 5

 fast-slow pointer

• slow는 한 칸씩 이동
• fast는 두 칸씩 이동
• fast가 끝에 도달할 때 slow는 절반만 이동 → 가운데 노드!

function deleteMiddle(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return null;

  let slow = head;
  let fast = head;
  let prev: ListNode | null = null;

  while (fast && fast.next) {
    prev = slow;
    slow = slow.next!;
    fast = fast.next.next;
  }

  prev!.next = slow.next;
  return head;
}

 

예시 2: 홀수·짝수 노드 재정렬 (oddEvenList)

노드를 홀수 인덱스와 짝수 인덱스 그룹으로 나누고, 홀수 그룹 뒤에 짝수 그룹을 붙여라.

1 → 2 → 3 → 4 → 5

 

결과

1 → 3 → 5 → 2 → 4

• odd는 홀수 인덱스 체인
• even은 짝수 인덱스 체인
• 마지막에 odd 체인의 끝을 evenStart에 연결

코드

function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head?.next) return head;

  let odd = head;
  let even = head.next;
  const evenStart = even;

  while (even?.next) {
    odd.next = even.next; // odd 체인 확장
    odd = odd.next;

    even.next = odd.next; // even 체인 확장
    even = even.next;
  }

  odd.next = evenStart; // 결합
  return head;
}

 

• evenStart는 2 → 4 → ... 로 연결된 "짝수 체인의 시작점".
• 노드 하나에는 값(val)과 next가 있어서, 2만 연결해도 뒤에 있던 4가 자동으로 따라옴.

 

---

정리

• Node(노드) = 값 + 다음 노드(next)를 가진 객체
• 연결 리스트는 노드들이 next 연결로 이어진 사슬 구조
• 삭제는 next 조작으로 이루어짐 (prev.next = cur.next)
• fast-slow pointer는 중간 노드를 찾는 핵심 전략
• odd-even 재배열 같은 문제는 연결 리스트의 구조적 이해를 요구