자료구조 면접 질문 완벽 정리: 스택, 큐, 트리, 해시

자료구조는 알고리즘과 함께 개발자 면접의 기초 중 기초입니다. 각 자료구조가 왜 존재하고 언제 쓰이는지를 이해하면 면접뿐 아니라 실무에서도 올바른 선택을 할 수 있습니다.

배열 (Array)#

가장 기본적인 자료구조로, 연속된 메모리에 같은 타입의 데이터를 저장합니다.

const arr = [1, 2, 3, 4, 5]

arr[2]        // O(1) — 인덱스로 즉시 접근
arr.push(6)   // O(1) — 맨 뒤 삽입
arr.pop()     // O(1) — 맨 뒤 삭제
arr.shift()   // O(N) — 맨 앞 삭제 (나머지 요소 이동)
arr.unshift(0)// O(N) — 맨 앞 삽입 (나머지 요소 이동)

연산	시간복잡도
인덱스 접근	O(1)
검색	O(N)
맨 뒤 삽입/삭제	O(1)
중간 삽입/삭제	O(N)

연결 리스트 (Linked List)#

각 노드가 데이터와 다음 노드의 포인터를 가집니다.

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

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

  prepend(value) { // O(1) — 맨 앞에 삽입
    const node = new Node(value)
    node.next = this.head
    this.head = node
  }

  find(value) { // O(N) — 순차 탐색
    let current = this.head
    while (current) {
      if (current.value === value) return current
      current = current.next
    }
    return null
  }
}

배열 vs 연결 리스트:

중간 삽입/삭제가 많다면 → 연결 리스트 (O(1), 단 검색 후)
인덱스 접근이 많다면 → 배열 (O(1))

스택 (Stack)#

LIFO(Last In, First Out) — 마지막에 넣은 것이 먼저 나옵니다.

class Stack {
  #items = []

  push(item) { this.#items.push(item) }   // O(1)
  pop() { return this.#items.pop() }       // O(1)
  peek() { return this.#items.at(-1) }    // O(1) — 제거 없이 확인
  isEmpty() { return this.#items.length === 0 }
}

// 실전 활용: 괄호 유효성 검사
function isValidBrackets(s) {
  const stack = new Stack()
  const pairs = { ')': '(', ']': '[', '}': '{' }

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char)
    } else if (stack.isEmpty() || stack.peek() !== pairs[char]) {
      return false
    } else {
      stack.pop()
    }
  }

  return stack.isEmpty()
}

스택 활용 예시: 함수 콜 스택, 실행 취소(Undo), 브라우저 뒤로가기

큐 (Queue)#

FIFO(First In, First Out) — 먼저 넣은 것이 먼저 나옵니다.

// 배열로 구현 시 shift()가 O(N)이라 비효율적
// 실무에서는 연결 리스트나 두 스택으로 구현

class Queue {
  #items = {}
  #head = 0
  #tail = 0

  enqueue(item) { this.#items[this.#tail++] = item }  // O(1)
  dequeue() {                                           // O(1)
    const item = this.#items[this.#head]
    delete this.#items[this.#head++]
    return item
  }
  isEmpty() { return this.#head === this.#tail }
}

큐 활용 예시: 프린터 작업 대기열, BFS 탐색, 이벤트 처리

해시테이블 (Hash Table)#

키를 해시 함수로 변환해 배열 인덱스로 사용합니다. 평균 O(1) 검색/삽입/삭제가 강점입니다.

// JavaScript에서는 Map, Set, 객체 리터럴이 해시테이블 역할

const map = new Map()
map.set('name', '홍길동')  // O(1)
map.get('name')            // O(1)
map.has('name')            // O(1)

// 실전: 두 배열의 교집합
function intersection(arr1, arr2) {
  const set = new Set(arr1)          // O(N)
  return arr2.filter(n => set.has(n)) // O(M)
  // 총 O(N+M) — 이중 반복문 O(N×M)보다 훨씬 빠름
}

해시 충돌 (Hash Collision)#

다른 키가 같은 해시값을 가질 때 발생합니다.

체이닝(Chaining): 같은 인덱스에 연결 리스트로 연결
개방 주소법(Open Addressing): 다음 빈 슬롯을 탐색

트리 (Tree)#

계층적 구조를 표현하는 자료구조입니다.

        10
       /  \
      5    15
     / \     \
    3   7    20

class TreeNode {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

// 이진 탐색 트리 (BST): 왼쪽 < 루트 < 오른쪽
class BST {
  insert(value, node = this.root) {
    if (!this.root) { this.root = new TreeNode(value); return }
    if (value < node.value) {
      if (!node.left) node.left = new TreeNode(value)
      else this.insert(value, node.left)
    } else {
      if (!node.right) node.right = new TreeNode(value)
      else this.insert(value, node.right)
    }
  }
}

트리 순회#

// 전위 순회 (Root → Left → Right)
function preOrder(node) {
  if (!node) return
  console.log(node.value)
  preOrder(node.left)
  preOrder(node.right)
}

// 중위 순회 (Left → Root → Right) — BST에서 정렬된 순서
function inOrder(node) {
  if (!node) return
  inOrder(node.left)
  console.log(node.value)
  inOrder(node.right)
}

힙 (Heap)#

완전 이진 트리로, 최대값 또는 최솟값을 O(1)로 조회합니다.

최소 힙: 부모 ≤ 자식
         1
        / \
       3   2
      / \
     7   4

힙 활용: 우선순위 큐, 힙 정렬, Top K 문제

// JavaScript에서는 직접 구현하거나 라이브러리 사용
// 코딩테스트에서는 배열로 힙을 시뮬레이션

// Top K 큰 수 찾기
function topK(nums, k) {
  nums.sort((a, b) => b - a)  // O(N log N)
  return nums.slice(0, k)
}

자료구조 선택 가이드#

필요한 연산	최선의 자료구조
인덱스 접근	배열
키로 값 조회	해시테이블 (Map)
중복 없는 집합	해시셋 (Set)
LIFO 처리	스택
FIFO 처리	큐
최솟값/최댓값 반복 조회	힙
계층 구조 표현	트리
정렬된 데이터 검색	이진 탐색 트리

면접 빈출 질문 요약#

스택과 큐의 차이? LIFO vs FIFO. 스택: 함수 콜스택, 큐: BFS
해시테이블 시간복잡도? 평균 O(1), 최악 O(N) (해시 충돌 시)
배열 vs 연결 리스트? 배열은 O(1) 인덱스 접근, 연결 리스트는 O(1) 중간 삽입/삭제
힙이란? 최솟값/최댓값을 O(1)로 조회하는 완전 이진 트리
BST 시간복잡도? 균형 잡힌 경우 O(log N), 최악(일자 트리) O(N)