들어가며

작업을 하다 보면 ‘노드(node)’라는 단어를 자주 접하게 됩니다.  
특히 프론트엔드 개발을 하다 보면 DOM 구조 속 요소를 노드라고 부르기도 하죠.
저 역시 그 정도로만 알고 있었는데, 자료구조를 공부하면서 처음으로 노드가 얼마나 중요한 개념인지 알게 되었습니다.  
단순히 태그를 감싸는 요소가 아니라, 데이터를 효율적으로 구성하고 연결하는 구조의 핵심이었던 거죠.

처음 자료구조를 접하는 분들이 가장 헷갈리는 부분 중 하나가 바로 노드(node) 개념입니다.  
이 책에서는 “왜 배열이 아닌 노드로 데이터를 연결해야 할까?”라는 의문부터 시작해서, 이 노드를 기반으로  
"연결 리스트 → 트리 구조(이진 탐색 트리) → 힙 → 트라이"로 점점 확장되는 구조를 제시했는데요. 각 구조에서 삽입·삭제·탐색 등의 어떻게 동작하는 지 살펴보려 합니다.

 

연결 리스트 (Linked List)

왜 배열만으로는 부족할까?

배열은 인덱스를 기준으로 원하는 값에 바로 접근할 수 있어서 아주 편리합니다.
하지만 문제는 중간에 데이터를 삽입하거나 삭제할 때 발생하는데요.
그럴 경우, 해당 위치 이후의 모든 요소를 한 칸씩 밀거나 당겨야 하기 때문에, 데이터가 많아질수록 시간이 점점 오래 걸립니다.

이런 상황을 시간 복잡도로 표현하면 O(n)이라고 하는데요, 이는 전체 데이터 수(n)에 비례해서 작업 시간이 증가한다는 뜻입니다. 즉, 데이터가 10개면 10번, 1,000개면 1,000번 움직여야 할 수도 있다는 의미죠.

이럴 땐 노드 기반 구조, 즉 연결 리스트가 해답이 될 수 있습니다.

// 단일 연결 리스트의 Node 구조
class Node {
  constructor(data) {
    this.data = data;    // 실제 데이터를 저장하는 필드
    this.next = null;    // 다음 노드를 가리키는 포인터
  }
}

// 리스트 구성 및 순회 예시
let head = new Node("once");
head.next = new Node("upon");
head.next.next = new Node("a");
head.next.next.next = new Node("time"); // ... 이어 붙이면 "once → upon → a → time"

이 예시는 "once → upon → a → time"처럼 노드들이 서로 연결되어 있는 구조입니다.
각 노드는 자신이 가진 데이터(data)와 다음 노드의 정보를 담고 있는 포인터(next)를 가지고 있습니다.

그래서 이 구조의 특징은 다음과 같은데요.

• 삽입과 삭제가 빠름 (O(1))
  원하는 위치에 있는 노드의 포인터만 조정하면 되므로, 전체를 이동할 필요 없이 바로 연결하거나 끊을 수 있습니다. 예를 들어 “upon”과 “a” 사이에 새로운 단어를 끼워 넣으려면, 단지 하나의 연결만 새로 지정하면 끝입니다.

• 단점: 인덱스로 빠르게 접근할 수 없음 (O(n))
  배열처럼 list[2] 이런 식으로 바로 찾아갈 수는 없습니다.
  맨 앞에서부터 차례차례(next를 따라) 이동해야 하기 때문에, 데이터가 많을수록 느려질 수 있습니다.

 

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

단일 연결 리스트의 아쉬운 점, 해결할 수 없을까?

단일 연결 리스트는 순차적으로 데이터를 이어붙이기에는 충분하지만, 한 방향(→)으로만 이동 가능하다는 제약이 있습니다.

예를 들어 중간 노드를 삭제하거나 이전 노드로 돌아가려면, 맨 앞(head)부터 차례대로 이동해야만 해당 노드를 찾을 수 있죠.

이런 문제를 해결하려면 양방향으로 이동 가능한 구조가 필요합니다.
그 해답이 바로 이중 연결 리스트입니다.

// 노드 클래스
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;    // 다음 노드를 가리킴
    this.prev = null;    // 이전 노드를 가리킴
  }
}

// 이중 연결 리스트 클래스
class DoublyLinkedList {
  constructor() {
    this.head = null;    // 리스트의 시작점
    this.tail = null;    // 리스트의 끝점
  }

  // 맨 뒤에 노드 삽입
  insertAtEnd(data) {
    const newNode = new Node(data);
    if (!this.head) {                // 리스트가 비어있다면
      this.head = this.tail = newNode;
      return;
    }
    this.tail.next = newNode;       // 기존 tail과 새 노드 연결
    newNode.prev = this.tail;       // 새 노드가 기존 tail을 가리킴
    this.tail = newNode;            // tail 갱신
  }
}

이 구조의 핵심은, 각 노드가 **next(다음 노드)**와 **prev(이전 노드)**를 모두 갖는다는 점입니다.
그래서 앞에서 뒤로, 뒤에서 앞으로 자유롭게 이동할 수 있습니다.

• 장점: 양방향 탐색이 가능함 (O(1))
  prev 포인터 덕분에 뒤에서 앞으로도 즉시 접근할 수 있습니다.
  단일 연결 리스트에서는 특정 노드 이전을 찾으려면 매번 처음부터 순회해야 했지만,
  여기서는 노드 간의 직접 연결만으로도 이전 노드를 바로 찾을 수 있습니다.

• 중간 삭제도 효율적 (O(1))
  삭제하려는 노드가 이미 주어져 있다면,
  prev.next와 next.prev를 조정하는 것만으로 삭제가 매우 간단하고 빠릅니다.

• 단점: 메모리 사용 증가 + 구현 복잡도
  포인터가 두 개(prev, next)여서 메모리를 더 사용하고,
  삽입/삭제 시 처리해야 할 포인터도 더 많아져 코드가 더 복잡해집니다.

부연 설명 (시간 복잡도 감 잡기)

• O(1) 삭제:
  해당 노드를 정확히 알고 있을 경우, 포인터만 바꾸면 되기 때문에 리스트 전체를 탐색할 필요 없이 바로 삭제 가능합니다.

• 중간 삽입/삭제가 왜 더 쉬워졌을까?
  → 앞 노드와 뒷 노드를 모두 알고 있기 때문입니다.
  단일 연결 리스트는 뒷노드(next)만 있어서 "앞 노드 찾기"가 어려웠지만, 이중 연결 리스트는 양방향 정보를 다 가지고 있어 연결 해제도 훨씬 간단해집니다.

이 구조는 특히 브라우저의 ‘이전/다음 이동 기능’, Undo/Redo 시스템, 이중 방향 캐시 등에 자주 활용된다고 합니다. 앞뒤로 오가는 구조가 필요한 상황에서는 꼭 등장하는 자료구조라고 하니 알아두면 좋겠죠?

 

이진 탐색 트리 (Binary Search Tree, BST)

연결 리스트에서 “계층 구조”로 확장해보겠습니다.

앞에서 살펴본 연결 리스트는 데이터를 순차적으로 이어주는 선형 구조였는데요.
하지만 탐색 효율이 중요해지는 순간, 선형 구조만으로는 부족해집니다.

그래서 등장한 것이 이진 탐색 트리, 줄여서 BST입니다. (그 유명한 분들이 아닙니다...)
트리는 노드 기반 구조이지만, 한 방향으로 이어지지 않고 ‘계층적으로’ 분기되고, 그 분기 규칙이 아주 간단합니다.

왼쪽 자식 < 부모 < 오른쪽 자식

이 규칙만 잘 지키면, 트리는 매우 빠른 탐색이 가능해집니다.
보통 평균적으로는 O(log n) 시간에 원하는 값을 찾을 수 있게 되죠.

class Node {
  constructor(val) {
    this.value = val;
    this.left = null;   // 왼쪽 자식 노드
    this.right = null;  // 오른쪽 자식 노드
  }
}

class BST {
  constructor() {
    this.root = null;   // 트리의 시작점 (루트 노드)
  }

  // 삽입 함수: 좌우 비교를 통해 적절한 위치에 삽입
  insert(value) {
    const node = new Node(value);
    if (!this.root) {
      this.root = node;
      return;
    }
    let curr = this.root;
    while (true) {
      if (value === curr.value) return; // 중복 값은 삽입하지 않음
      if (value < curr.value) {
        if (!curr.left) { curr.left = node; return; }
        curr = curr.left;
      } else {
        if (!curr.right) { curr.right = node; return; }
        curr = curr.right;
      }
    }
  }

  // 검색 함수: 트리의 규칙을 따라 좌우로 분기하며 탐색
  search(value) {
    let curr = this.root;
    while (curr) {
      if (value === curr.value) return true;
      curr = value < curr.value ? curr.left : curr.right;
    }
    return false;
  }

  // 삭제 함수: 하위 섹션에서 상세히 다룰 예정
  delete(value) {
    this.root = this._deleteNode(this.root, value);
  }

  /* 삭제 알고리즘은 다음 섹션에서 자세히 정리할 예정이니, 잠시 뒤에 함께 살펴보겠습니다. */
}

BST의 핵심 특성과 시간 복잡도

• 탐색 속도가 빠름 (O(log n))
  트리는 매 단계마다 범위를 절반으로 줄여나갑니다.
  예를 들어, 값이 50인 노드를 찾고 싶을 때, 루트가 30이라면 오른쪽으로 → 70이라면 왼쪽으로 → 이런 식으로 계속 좁혀갑니다. 이런 방식은 이진 탐색(binary search)과 원리가 같아 데이터가 많아도 빠르게 원하는 값을 찾을 수 있습니다.

• 삽입·삭제도 구조에 따라 빠름 (O(log n))
  삽입도 마찬가지로 규칙에 따라 위치를 찾아 넣으면 되고, 삭제는 좀 더 복잡하지만, 위치를 알아내는 과정 자체는 효율적입니다. 다만 이건 ‘트리가 잘 균형 잡혔을 때’의 이야기입니다.

• 최악의 경우 O(n)까지도 늘어남
  예: 삽입된 값들이 모두 정렬되어 있다면, 트리는 한쪽 방향으로만 자라는 '편향 트리'가 되기 때문에 리스트와 다를 바 없는 성능이 됩니다.

트리는 어디에 쓰일까?

• 자동 완성 추천 시스템,

• 파일 디렉터리,

• 게임 AI의 의사 결정 트리,

• 이진 탐색 알고리즘 구현,
  이처럼 검색 속도가 중요한 분야에서 자주 쓰입니다.

추가적으로 설명을 드리면 왜 O(log n)이 빠를까요?

O(log n)은 매 단계마다 선택지를 절반씩 줄인다는 뜻입니다.
1000개의 데이터가 있어도 최대 10번 비교면 원하는 값을 찾을 수 있습니다.
이건 마치 사전을 반으로 계속 접어서 원하는 단어를 찾는 것과 같은데요.
단, 이 효율은 트리가 균형을 이루고 있을 때만 보장된다고 합니다.

 

BST의 삭제(Delete) 연산

앞서 살펴본 삽입과 검색은 규칙만 잘 지키면 단순한 로직으로 구현할 수 있었죠.
하지만 삭제는 그렇지 않습니다. 노드의 ‘자식 유무’에 따라 처리 방식이 완전히 달라지기 때문입니다.

BST 삭제의 세 가지 상황

1. 자식이 없는 노드 (리프 노드)
   → 그냥 null로 바꿔서 없애면 끝입니다.

2. 자식이 하나인 노드
   → 자식 노드를 부모와 직접 연결해주면 됩니다.
   예: 부모 → 삭제 대상 → 자식 → 부모 → 자식

3. 자식이 두 개인 노드
   → 이때가 가장 까다롭습니다.
   삭제할 노드를 대신할 값이 필요하기 때문인데요, 보통 **오른쪽 서브트리에서 가장 작은 값(findMin)**을 찾아서 삭제할 노드의 자리에 복사하고, 그 작은 노드를 다시 삭제하는 방식으로 해결합니다.

// 내부 재귀 함수: 세 가지 삭제 케이스 처리
_deleteNode(node, value) {
  if (!node) return null;  // 찾는 값이 없을 경우
  if (value < node.value) {
    node.left = this._deleteNode(node.left, value);
  } else if (value > node.value) {
    node.right = this._deleteNode(node.right, value);
  } else {
    // 1. 자식이 없는 경우
    if (!node.left && !node.right) return null;

    // 2. 자식이 하나인 경우
    if (!node.left) return node.right;
    if (!node.right) return node.left;

    // 3. 자식이 둘인 경우
    const min = this._findMin(node.right);  // 오른쪽 서브트리 최소값
    node.value = min.value;                 // 삭제 대상 값 대체
    node.right = this._deleteNode(node.right, min.value); // 최소값 삭제 재귀
  }
  return node;
}

// 오른쪽 서브트리 중 가장 작은 값 반환
_findMin(node) {
  while (node.left) node = node.left;
  return node;
}

이 코드는 재귀적으로 삭제할 값을 찾아 내려가며, 상황별로 분기 처리를 수행합니다.
특히 자식이 둘인 경우엔 교체 → 재삭제의 흐름이 반복되기 때문에 이해가 중요한 부분입니다.

조금 더 이해를 돕기 위해 BST 삭제 케이스에 따른 처리 방식을 표로 정리해보았습니다.

케이스	처리 방식
리프 노드	null 반환
자식 하나	자식을 그대로 상위에 연결
자식 둘	오른쪽 서브트리 최소값으로 교체 후 해당 노드 삭제

삭제가 복잡한 이유는

• 단순히 "지워버리는 것"이 아니라, 트리의 규칙(왼쪽 < 부모 < 오른쪽)을 유지한 채로 연결을 다시 구성해야 하기 때문입니다.

• 특히 자식이 두 개 있는 경우엔 값의 대체와 포인터 재조정이 동시에 일어나므로 초보자들이 가장 많이 헷갈리는 포인트인 것 같아요. (제가 그렇거든요...)

 

힙 (Heap) - 완전한 이진트리 + 우선순위 큐

지금까지 봤던 이진 탐색 트리(BST)는 노드의 값 크기를 기준으로 왼쪽/오른쪽을 정하는 탐색 중심 구조였는데요. 하지만 탐색보다 "우선순위에 따라 빠르게 꺼내기"가 중요한 문제도 많습니다.

이럴 때 쓰이는 구조가 바로 힙(Heap)입니다. (저는 마마무의 힙말고 자료 구조 힙은 이 책으로 처음 접했습니다.)
힙은 단순한 트리가 아닙니다.
“완전 이진 트리”의 형태를 가지면서, 부모와 자식 간의 값 관계를 규정하는 자료구조라고 합니다.

그렇다면 완전한 이진 트리는 무엇일까요? 힙의 핵심 규칙을 정리하면서 함께 설명드리겠습니다.

힙의 핵심 규칙

• 완전 이진 트리 : 트리의 모든 레벨이 완전히 채워져 있으며, 마지막 레벨만 왼쪽부터 채워짐

• 힙 조건 (Heap Property)

  • 최소 힙(Min Heap): 부모 ≤ 자식

  • 최대 힙(Max Heap): 부모 ≥ 자식
    덕분에 힙은 항상 루트(root)에 가장 작은 값 또는 가장 큰 값이 위치하게 됨

아래 예시 코드는 책에 있던 코드를 자바스크립트 코드로 변환한 것입니다.

// 최소 힙 구현 예시
class MinHeap {
  constructor() {
    this.heap = [];  // 배열로 힙을 표현
  }

  // 값을 삽입하고 위로 정렬 (heapify-up)
  insert(val) {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0) {
      let p = Math.floor((i - 1) / 2); // 부모 인덱스
      if (this.heap[i] >= this.heap[p]) break; // 조건 만족 시 종료
      [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]]; // 부모와 자리 바꿈
      i = p;
    }
  }

  // 최소값 제거 후 아래로 정렬 (heapify-down)
  extractMin() {
    if (this.heap.length < 2) return this.heap.pop(); // 요소 하나면 그냥 제거
    const min = this.heap[0];
    this.heap[0] = this.heap.pop(); // 마지막 값을 루트에 올리고
    this._heapifyDown();           // 힙 성질 회복
    return min;
  }

  // 자식과 비교하며 아래로 내려감
  _heapifyDown() {
    let i = 0;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let smallest = i;
      if (l < this.heap.length && this.heap[l] < this.heap[smallest]) smallest = l;
      if (r < this.heap.length && this.heap[r] < this.heap[smallest]) smallest = r;
      if (smallest === i) break;
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

• 삽입/삭제: O(log n)

• 최소값 조회: O(1)

• 전체 힙 정렬: O(n log n)

 

트라이 (Trie) – 문자열 검색에 최적화된 트리

배열이나 리스트, 트리 구조만으로는 문자열 검색이나 자동완성 기능을 효율적으로 구현하기 어렵습니다.
특히 수많은 단어들 중에서 특정 접두어로 시작하는 단어만 빠르게 찾고 싶을 때,
매번 순회하며 찾는 것은 비효율적이죠.

이런 문제를 해결하기 위해 만들어진 자료구조가 트라이(Trie)입니다. 트라이는 단어의 각 문자를 노드로 연결하여, 접두어 단위 검색에 최적화된 트리입니다.

검색 속도는 단어의 길이에만 비례하기 때문에
실시간 자동완성, 추천, 사전 검색 등에 매우 유용합니다.

트라이 기본 구조

트라이는 다음과 같은 방식으로 동작합니다:

• 한 문자씩 노드로 이어 붙이며 트리를 구성

• 단어가 끝나는 지점에 isEndOfWord = true 플래그를 설정

• 검색 시에는 루트부터 한 글자씩 따라가며 탐색

// 트라이 노드
class TrieNode {
  constructor() {
    this.children = {};       // 알파벳 문자 키를 자식으로 가짐
    this.isEndOfWord = false; // 단어 끝 여부 표시
  }
}

// 트라이 클래스
class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // 단어 삽입
  insert(word) {
    let curr = this.root;
    for (const ch of word) {
      if (!curr.children[ch]) curr.children[ch] = new TrieNode();
      curr = curr.children[ch];
    }
    curr.isEndOfWord = true;
  }

  // 정확히 일치하는 단어 검색
  search(word) {
    let curr = this.root;
    for (const ch of word) {
      if (!curr.children[ch]) return false;
      curr = curr.children[ch];
    }
    return curr.isEndOfWord;
  }

  // 특정 접두어로 시작하는 단어가 있는지 확인
  startsWith(prefix) {
    let curr = this.root;
    for (const ch of prefix) {
      if (!curr.children[ch]) return false;
      curr = curr.children[ch];
    }
    return true;
  }

  // 모든 단어 수집 (재귀)
  collectAllWords(node = this.root, prefix = "", words = []) {
    if (node.isEndOfWord) words.push(prefix);
    for (const ch in node.children) {
      this.collectAllWords(node.children[ch], prefix + ch, words);
    }
    return words;
  }

  // 자동완성 결과 반환
  autocomplete(prefix) {
    let curr = this.root;
    for (const ch of prefix) {
      if (!curr.children[ch]) return [];
      curr = curr.children[ch];
    }
    return this.collectAllWords(curr, prefix);
  }
}

// 사용 예시
const trie = new Trie();
['ace', 'bad', 'batter', 'cat', 'catnip'].forEach(w => trie.insert(w));

console.log(trie.autocomplete('ba'));  // 👉 ["bad", "batter"]
console.log(trie.autocomplete('cat')); // 👉 ["cat", "catnip"]

트라이의 장점

• 접두어 기반 검색에 매우 빠름
  startsWith('ca'), autocomplete('bat') 같은 기능 구현에 최적화

• 정확한 단어 검색 및 자동완성 기능 내장
  검색 엔진, 사전, 모바일 키보드 입력 추천 등에 사용됨

• 검색 속도는 '단어 수'가 아닌 '글자 수'에만 비례
  수천 개의 단어가 있어도 O(m)의 빠른 탐색 가능

트라이의 단점

• 메모리 사용량이 큼
  각 문자를 노드로 저장하고, 자식들을 해시 형태로 관리하기 때문에
  많은 단어를 저장하면 공간 복잡도가 커질 수 있어요.

• 문자 세트가 넓을수록 자식 노드 관리가 복잡해짐
  한글, 유니코드, 이모지 등 다양한 문자 입력까지 고려하면 구조가 더 커집니다.

트라이는 리스트나 배열보다 복잡하지만,
문자열 기반 기능이 자주 쓰이는 앱/서비스에서는 거의 필수적인 자료구조예요.
앞으로 검색 엔진 최적화, 오타 수정, 자동 추천 등으로도 응용해볼 수 있습니다.

 

자료구조	삽입	삭제	탐색
배열	O(1) (끝) / O(n) (중간)	O(n)	O(1) (인덱스 접근)
연결 리스트	O(1) (앞), O(n) (중간)	O(1) (앞), O(n) (중간)	O(n)
이중 연결 리스트	O(1) (앞/뒤), O(n) (중간)	O(1) (노드 참조 시)	O(n)
이진 탐색 트리 (BST)	O(log n) 평균	O(log n) 평균	O(log n) 평균
힙 (Heap)	O(log n)	O(log n)	O(1) (최댓값/최솟값)
트라이 (Trie)	O(m)	O(m)	O(m)

 

참고 문서

누구나 자료 구조와 알고리즘 - 제이 웬그로우 저/심지현 역

 

마치며

처음엔 단순히 'DOM 요소'로만 여겼던 노드가,
자료구조의 핵심 개념으로 이렇게 다양한 구조로 확장된다는 게 인상 깊었습니다.

연결 리스트부터 시작해, 트리, 힙, 트라이에 이르기까지
모두 “노드가 연결된다”는 하나의 원리에서 출발했죠.

이 글이 여러분의 머릿속에 흩어져 있던 ‘노드’라는 단어를
하나의 흐름으로 엮는 데 도움이 되었기를 바랍니다.

글은 여기까지이며, 혹시 수정할 내용이 있다면 언제든 알려주세요.
읽어주셔서 감사합니다. 🙇🏻‍♀️  
그럼 안녕히…👋 -The End-