자료구조 기초

pxd UX Engineer(XE) 그룹의 독서노트 시리즈는 제이 웬그로우의 『누구나 자료구조와 알고리즘』을 읽고 노드(node) 개념을 중심으로 자료구조가 확장되는 과정을 정리한다. 프론트엔드 개발자에게 노드는 흔히 DOM 요소를 가리키는 말로만 익숙하지만, 실제로는 데이터를 효율적으로 연결·구성하는 구조의 핵심 개념이다. 이 시리즈(4편)는 연결 리스트 → 트리(이진 탐색 트리) → 힙 → 트라이로 점점 복잡해지는 구조를 자바스크립트 코드와 함께 설명한다.

연결 리스트(Linked List)는 배열의 한계—중간 삽입·삭제 시 이후 요소를 전부 이동시켜야 하는 O(n) 비용—를 해결하기 위해 등장한다. 각 노드가 데이터와 다음 노드를 가리키는 포인터(`next`)만 가지므로 삽입·삭제는 포인터 조정만으로 O(1)에 처리되지만, 인덱스로 즉시 접근할 수 없어 특정 위치를 찾으려면 처음부터 순회해야 하는(O(n)) 단점이 있다. 이중 연결 리스트(Doubly Linked List)는 각 노드가 `next`뿐 아니라 `prev`도 가져 양방향 이동과 O(1) 중간 삭제를 가능하게 하며, 브라우저의 앞/뒤 이동, Undo/Redo, 양방향 캐시 등에 쓰인다.

이진 탐색 트리(BST)는 노드를 선형이 아닌 계층적으로 배치해, "왼쪽 자식 < 부모 < 오른쪽 자식" 규칙만으로 평균 O(log n)의 탐색·삽입·삭제를 구현한다. 다만 데이터가 정렬된 순서로 삽입되면 한쪽으로만 자라는 편향 트리가 되어 최악의 경우 O(n)까지 성능이 떨어진다. 삭제 연산은 자식이 없는 노드(그냥 제거), 자식이 하나인 노드(자식을 부모에 직접 연결), 자식이 둘인 노드(오른쪽 서브트리의 최솟값으로 교체 후 그 최솟값 노드를 재삭제)의 세 가지 경우로 나뉘어 상대적으로 까다롭다.

힙(Heap)은 완전 이진 트리 형태를 가지면서 부모-자식 간 크기 관계(최소 힙: 부모 ≤ 자식, 최대 힙: 부모 ≥ 자식)를 유지해, 루트에서 항상 최솟값 또는 최댓값을 O(1)에 꺼낼 수 있는 우선순위 큐 구조다. 삽입·삭제는 O(log n)이며 배열 기반으로 구현할 수 있다. 트라이(Trie)는 문자열의 각 글자를 노드로 연결해 접두어 검색에 최적화한 트리로, 검색 속도가 저장된 단어 수가 아니라 찾는 문자열의 길이(O(m))에만 비례해 자동완성·사전 검색·오타 수정 등에 활용된다. 다만 문자마다 노드를 만들고 자식을 해시로 관리하기 때문에 메모리 사용량이 크다는 단점이 있다.

시리즈는 배열·연결 리스트·이중 연결 리스트·BST·힙·트라이의 삽입·삭제·탐색 시간 복잡도를 표로 비교하며 마무리된다. 결론적으로 이 모든 구조는 "노드가 연결된다"는 하나의 원리에서 출발해, 목적(순차 접근, 빠른 탐색, 우선순위 처리, 접두어 검색)에 따라 노드를 배치하는 방식만 달라진다는 점을 강조한다.

핵심 내용

  • 노드(node): DOM 요소를 넘어, 데이터와 연결 정보를 함께 담는 자료구조의 기본 단위
  • 연결 리스트: 삽입·삭제 O(1), 인덱스 접근 O(n) — 배열의 중간 삽입·삭제 비용(O(n))을 해결
  • 이중 연결 리스트: `prev`/`next` 양방향 포인터로 역방향 탐색과 O(1) 중간 삭제 지원, Undo/Redo·브라우저 이동에 활용
  • 이진 탐색 트리(BST): "왼쪽 < 부모 < 오른쪽" 규칙으로 평균 O(log n) 탐색, 편향 트리가 되면 최악 O(n)
  • BST 삭제의 세 가지 케이스: 자식 없음(제거) / 자식 하나(직접 연결) / 자식 둘(오른쪽 서브트리 최솟값으로 교체 후 재삭제)
  • 힙(Heap): 완전 이진 트리 + 부모-자식 크기 관계로 최솟값/최댓값을 O(1)에 꺼내는 우선순위 큐, 삽입·삭제 O(log n)
  • 트라이(Trie): 문자열을 글자 단위 노드로 연결, 접두어 검색에 최적화(O(m)), 자동완성·사전 검색에 활용되나 메모리 사용량 큼

관련 개념

출처

최종 업데이트: 2026-09-07 | 출처 1개