1-6 연결 리스트·트리·그래프

	배열	연결 리스트
랜덤 접근	O(1)	O(n)
중간 삽입/삭제	O(n)	O(1) (포인터 있을 때)
메모리	연속, 캐시 친화	흩어짐, 포인터 오버헤드
크기 변경	재할당 필요	자유로움

1-3. ⚠️ 함정: 이론적 O(1) vs 실제 성능

연결 리스트의 "중간 삽입 O(1)"은 이미 그 위치의 포인터를 들고 있을 때만 성립. 검색이 필요하면 O(n)이다.

또한 현대 CPU는 캐시 지역성 때문에 연속 메모리를 훨씬 빠르게 읽는다. 순회만 필요하면 배열이 대부분 더 빠르다 (3단계에서 심화).

"빅오가 같으면 상수가 작은 쪽이 이긴다".

1-4. 단일 연결 리스트 구현

class ListNode {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

class LinkedList {
  constructor() { this.head = null; this.size = 0; }

  prepend(val) {
    this.head = new ListNode(val, this.head);
    this.size++;
  }

  append(val) {
    const node = new ListNode(val);
    if (!this.head) this.head = node;
    else {
      let cur = this.head;
      while (cur.next) cur = cur.next;
      cur.next = node;
    }
    this.size++;
  }

  delete(val) {
    if (!this.head) return;
    if (this.head.val === val) { this.head = this.head.next; this.size--; return; }
    let cur = this.head;
    while (cur.next && cur.next.val !== val) cur = cur.next;
    if (cur.next) { cur.next = cur.next.next; this.size--; }
  }
}

1-5. 대표 문제: 뒤집기

3개 포인터(prev, cur, next)로 순회하며 방향을 뒤집는다.

function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

이 패턴은 수많은 연결 리스트 문제의 기본.

1-6. 이중 연결 리스트와 원형

이중: 이전 노드 포인터도 유지 → 양방향 순회, 중간 삭제 O(1)
원형: 꼬리가 머리를 가리킴 → 스케줄링, 원형 버퍼

2. 이진 트리와 BST

2-1. 용어

루트: 최상위 노드
리프: 자식 없는 노드
깊이(depth): 루트에서의 거리
높이(height): 가장 먼 리프까지의 거리
균형: 모든 리프의 깊이가 비슷함

2-2. 순회 4가지

전위 (Pre-order): 루트 → 왼 → 오 → A B D E C F
중위 (In-order): 왼 → 루트 → 오 → D B E A C F
후위 (Post-order): 왼 → 오 → 루트 → D E B F C A
레벨 (BFS): A B C D E F

2-3. BST (Binary Search Tree)

왼쪽 서브트리의 모든 값 < 루트 < 오른쪽 서브트리의 모든 값.

BST의 중위 순회 결과는 항상 오름차순.

class BSTNode {
  constructor(val) { this.val = val; this.left = null; this.right = null; }
}

class BST {
  constructor() { this.root = null; }

  insert(val) {
    this.root = this._insert(this.root, val);
  }
  _insert(node, val) {
    if (!node) return new BSTNode(val);
    if (val < node.val) node.left = this._insert(node.left, val);
    else if (val > node.val) node.right = this._insert(node.right, val);
    return node;
  }

  contains(val) {
    let cur = this.root;
    while (cur) {
      if (val === cur.val) return true;
      cur = val < cur.val ? cur.left : cur.right;
    }
    return false;
  }
}

2-4. 복잡도

균형 잡힌 BST: 탐색/삽입/삭제 O(log n)
최악 (정렬된 데이터를 순차 삽입): O(n) — 선형 리스트가 됨

균형 트리 (AVL, Red-Black): 삽입/삭제 시 자동으로 회전하여 균형 유지. 이름과 용도만 알면 된다.

3. 트라이 (Trie, Prefix Tree)

3-1. 용도

문자열 집합에 대한 접두사 검색을 O(m)에 (m = 검색 문자열 길이). 배열에서 매번 순회하면 O(n×m).

3-2. 구조

각 노드에 "이 노드에서 끝나는 단어인가" 플래그.

3-3. 구현

class TrieNode {
  constructor() { this.children = new Map(); this.isEnd = false; }
}

class Trie {
  constructor() { this.root = new TrieNode(); }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }

  _traverse(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }

  autocomplete(prefix, limit = 10) {
    const node = this._traverse(prefix);
    if (!node) return [];
    const result = [];
    const dfs = (cur, path) => {
      if (result.length >= limit) return;
      if (cur.isEnd) result.push(prefix + path);
      for (const [ch, next] of cur.children) dfs(next, path + ch);
    };
    dfs(node, '');
    return result;
  }
}

3-4. 복잡도

삽입/검색: O(m)
공간: 알파벳 수 × 총 문자 수 — 매우 크다

3-5. 실전: 주소 자동완성, 태그 필터

검색어 입력할 때마다 Trie에서 접두사 매칭. "서울"만 쳐도 시군구 후보 전체를 O(m)에 제공.

4. Union-Find (Disjoint Set)

4-1. 용도

"두 원소가 같은 집합에 있는가?"를 빠르게 판정.

find(x): x가 속한 집합의 대표 원소
union(x, y): 두 집합을 합침

4-2. 기본 구현

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);  // 경로 압축
    }
    return this.parent[x];
  }

  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    // union by rank: 낮은 트리를 높은 트리 밑에
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

4-3. 최적화 두 가지

경로 압축 (Path Compression): find 시 중간 노드들을 직접 루트에 붙임
Union by Rank: 낮은 트리를 높은 트리 밑에 붙여 깊이 증가 방지

두 최적화 다 적용하면 아커만 역함수 α(n) ≈ 상수. 실질적으로 O(1).

4-4. 실전

MST (Kruskal): 간선을 가중치 순으로 정렬 후, 사이클을 만들지 않는 것만 선택
그래프 연결성: 동적으로 간선이 추가될 때 "같은 컴포넌트인가?" 판정
이미지 영역 감지: 같은 색 픽셀을 합치기

5. 그래프 표현

5-1. 인접 행렬 (Adjacency Matrix)

공간: O(V²)
간선 존재 확인: O(1)
모든 이웃 탐색: O(V)
간선이 조밀한(dense) 그래프에 유리

5-2. 인접 리스트 (Adjacency List)

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C'],
};
// 또는 Map
const graph2 = new Map([['A', ['B','C']], ...]);

공간: O(V + E)
간선 존재 확인: O(deg(v))
모든 이웃 탐색: O(deg(v))
희소(sparse) 그래프에 유리 — 대부분의 실무 그래프

5-3. 가중 그래프

const graph = {
  A: [{ to: 'B', w: 3 }, { to: 'C', w: 1 }],
  ...
};

6. DFS와 BFS

6-1. DFS (Depth-First Search)

한 방향 끝까지 → 되돌아오며 다른 방향. 스택 또는 재귀.

function dfs(start, graph) {
  const visited = new Set();
  function visit(node) {
    if (visited.has(node)) return;
    visited.add(node);
    console.log(node);
    for (const next of graph[node] ?? []) visit(next);
  }
  visit(start);
}

용도:

백트래킹 (N-Queens, 스도쿠, 순열)
위상 정렬
연결 컴포넌트 세기
사이클 감지

6-2. BFS (Breadth-First Search)

같은 거리 전부 방문 → 다음 거리. 큐.

function bfs(start, graph) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();   // ⚠️ 큰 그래프면 head 포인터 큐를
    console.log(node);
    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }
}

용도:

가중치 없는 그래프의 최단 경로
레벨별 순회
웹 크롤러
소셜 네트워크의 "친구의 친구"

6-3. DFS vs BFS

	DFS	BFS
자료구조	스택(재귀)	큐
메모리	O(h) (높이)	O(w) (너비)
특성	깊이 먼저	거리 먼저
최단 경로	X	O (가중치 1일 때)

7. FE 실전 연결

7-1. DOM 트리

document 자체가 트리. querySelector, children, parentNode 순회는 그래프 순회다.

// BFS로 모든 자손 순회
function bfsDOM(root) {
  const queue = [root];
  while (queue.length) {
    const el = queue.shift();
    console.log(el.tagName);
    for (const child of el.children) queue.push(child);
  }
}

7-2. Virtual DOM diff

React가 두 가상 트리를 비교할 때 DFS로 순회. 같은 위치의 노드를 비교하며 key 기반으로 매칭.

7-3. 컴포넌트 트리

React 컴포넌트는 트리 구조. context 전파는 상위→하위 DFS 전파와 유사.

7-4. 번들러 의존성 그래프

import A from './a' 문들이 DAG(Directed Acyclic Graph)를 형성. 번들러는 이 그래프를 위상 정렬해 출력 순서를 결정 (1-7 챕터).

연습 문제

단일 연결 리스트를 뒤집는 reverse(head)를 재귀와 반복 양쪽으로 구현하라.
두 정렬된 연결 리스트를 병합하는 merge(a, b)를 구현하라.
이진 트리의 모든 순회(전위/중위/후위/레벨)를 구현하라.
트라이로 자동완성 기능을 구현하고 ["apple", "app", "apply", "application"]을 넣은 뒤 "app" 검색 결과를 구하라.
Union-Find로 n 노드 그래프에서 간선 [[0,1],[1,2],[3,4]]를 추가한 뒤 연결 컴포넌트 수를 구하라.
인접 리스트로 표현된 그래프에서 BFS로 최단 거리 배열을 반환하는 함수를 작성하라.
DOM 트리에서 특정 class를 가진 가장 가까운 조상 노드를 찾는 closest(el, cls)를 순회로 직접 구현하라.

연습 문제 정답

1. 뒤집기

// 반복
function reverseIter(head) {
  let prev = null, cur = head;
  while (cur) { const next = cur.next; cur.next = prev; prev = cur; cur = next; }
  return prev;
}

// 재귀
function reverseRec(head) {
  if (!head || !head.next) return head;
  const newHead = reverseRec(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

2. 병합

function merge(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

3. 순회 4종

const preOrder = (n, r=[]) => { if (!n) return r; r.push(n.val); preOrder(n.left,r); preOrder(n.right,r); return r; };
const inOrder  = (n, r=[]) => { if (!n) return r; inOrder(n.left,r); r.push(n.val); inOrder(n.right,r); return r; };
const postOrder= (n, r=[]) => { if (!n) return r; postOrder(n.left,r); postOrder(n.right,r); r.push(n.val); return r; };
function levelOrder(root) {
  if (!root) return [];
  const r = [], q = [root];
  while (q.length) {
    const n = q.shift();
    r.push(n.val);
    if (n.left) q.push(n.left);
    if (n.right) q.push(n.right);
  }
  return r;
}

4. Trie 자동완성

const t = new Trie();
["apple", "app", "apply", "application"].forEach(w => t.insert(w));
t.autocomplete("app");  // ["app", "apple", "apply", "application"]

5. 연결 컴포넌트

const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
const roots = new Set();
for (let i = 0; i < 5; i++) roots.add(uf.find(i));
roots.size;  // 2 (그룹 {0,1,2}와 {3,4})

6. BFS 최단 거리

function bfsDistance(start, graph) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const next of graph[node] ?? []) {
      if (!dist.has(next)) {
        dist.set(next, dist.get(node) + 1);
        queue.push(next);
      }
    }
  }
  return dist;
}

7. closest

function closest(el, cls) {
  let cur = el;
  while (cur && cur !== document) {
    if (cur.classList?.contains(cls)) return cur;
    cur = cur.parentNode;
  }
  return null;
}

조상 체인을 타고 올라가며 클래스 확인. 이것이 Element.closest()의 실체다.

체크리스트

이전: 1-5. 스택·큐·힙 | 다음: 1-7. 핵심 알고리즘