자료구조 (Data Structures)

자료구조란

자료구조(Data Structures) 는 데이터를 어떤 형태로 저장하고 접근할지 정하는 방식입니다.

백엔드 면접에서 자료구조는 알고리즘 문제 풀이용 지식으로만 나오지 않습니다.
대기열, 캐시, 인덱스, 작업 스케줄링, 우선순위 처리처럼 실제 시스템 구현에서도 계속 등장합니다.

핵심은 이름을 외우는 것이 아니라 다음을 설명할 수 있는가입니다.

어떤 연산이 자주 일어나는가
그 연산이 얼마나 빠른가
메모리를 얼마나 쓰는가
순서, 중복, 탐색, 갱신 중 무엇이 중요한가

즉, 자료구조는 “데이터를 어떻게 놓을 것인가”에 대한 선택입니다.

면접에서 자료구조를 보는 이유

면접관이 자료구조를 묻는 이유는 보통 다음과 같습니다.

문제 분해 능력: 요구사항을 어떤 연산으로 바꿔 보는가
기본기: 삽입, 삭제, 탐색의 비용을 감으로 아는가
선택 기준: 배열, 해시, 트리 중 왜 이것을 골랐는지 설명하는가
트레이드오프 인식: 빠른 탐색을 얻는 대신 메모리나 구현 복잡도가 늘어나는 점을 아는가

예를 들어 “최근 조회 항목 10개를 유지하라”는 문제는 단순 리스트가 아니라 큐나 덱을 떠올릴 수 있어야 합니다.
“중복 없이 빠르게 존재 여부를 확인하라”는 문제는 해시 기반 구조가 자연스럽습니다.

자료구조 답변이 강하려면 “이 구조는 빠릅니다”보다
어떤 연산이 O(1)에 가깝고, 어떤 연산이 느려지는지까지 연결해서 설명하는 편이 좋습니다.

시간 복잡도와 공간 복잡도

자료구조를 설명할 때는 보통 시간 복잡도(Time Complexity) 와 공간 복잡도(Space Complexity) 를 같이 봅니다.

시간 복잡도: 입력 크기가 커질수록 연산 시간이 어떻게 증가하는가
공간 복잡도: 문제를 풀기 위해 추가 메모리가 얼마나 필요한가

면접에서는 보통 다음 질문으로 연결됩니다.

조회가 빠른 대신 삽입이 느려지는가
메모리를 더 쓰는 대신 탐색을 빠르게 할 수 있는가
최악의 경우에도 성능이 안정적인가

중요한 점은 Big-O를 외우는 것보다, 핵심 연산 기준으로 복잡도를 말하는 것입니다.

예를 들어:

배열은 인덱스로 접근할 때 빠릅니다.
연결 리스트는 중간 삽입이 쉬울 수 있지만, 원하는 위치를 먼저 찾아야 합니다.
해시 테이블은 평균적으로 빠른 조회가 가능하지만, 해시 충돌과 메모리 사용량을 고려해야 합니다.

즉, 자료구조 평가는 항상 “무슨 연산이 중요한가”와 함께 가야 합니다.

배열과 연결 리스트

배열(Array)과 연결 리스트(Linked List)는 가장 기본적인 선형 자료구조입니다.

항목	배열	연결 리스트
접근	인덱스로 빠르게 접근 가능	순차 탐색이 필요
삽입/삭제	중간 삽입/삭제 시 이동 비용 큼	노드 위치를 알고 있으면 유연
메모리	연속된 메모리 사용	포인터 저장 비용 필요
적합한 경우	랜덤 접근이 많은 경우	중간 삽입/삭제가 잦은 경우

배열이 잘 맞는 경우:

인덱스로 자주 접근해야 함
순차 스캔이 많음
캐시 친화적인 메모리 접근이 중요함

연결 리스트가 잘 맞는 경우:

앞뒤 삽입/삭제가 많음
크기가 자주 변함
순차 처리 위주임

하지만 실무와 면접 모두에서 연결 리스트가 자주 쓰인다는 뜻은 아닙니다.
실제 서비스 코드에서는 배열 기반 동적 리스트가 더 흔하고, 연결 리스트는 특정 삽입/삭제 패턴을 설명하는 교재형 구조로 나오는 경우가 많습니다.

스택과 큐

스택(Stack)과 큐(Queue)는 제어 흐름과 작업 처리 모델을 설명할 때 자주 나옵니다.

자료구조	원칙	대표 사용 사례
스택	LIFO (Last In, First Out)	함수 호출 스택, 괄호 검사, 되돌리기
큐	FIFO (First In, First Out)	작업 큐, 메시지 처리, BFS

스택이 잘 맞는 경우:

가장 최근 상태를 먼저 꺼내야 함
재귀나 중첩 구조를 추적해야 함
undo/redo 같은 되돌리기 흐름이 필요함

큐가 잘 맞는 경우:

먼저 들어온 작업을 먼저 처리해야 함
producer-consumer 모델이 필요함
요청이나 이벤트를 순서대로 소비해야 함

면접에서는 스택과 큐를 단순 정의보다, 문제의 처리 순서와 연결해서 설명하는 편이 좋습니다.

해시 테이블

해시 테이블(Hash Table) 은 키를 해시 함수로 변환해 저장 위치를 찾는 구조입니다.

평균적으로 빠른 조회, 삽입, 삭제가 가능해서 실제 서비스 코드에서 매우 자주 쓰입니다.

장점: 평균적으로 빠른 존재 여부 확인과 조회
장점: key-value 모델에 자연스럽게 맞음
단점: 해시 충돌 처리 필요
단점: 순서가 중요한 문제에는 바로 맞지 않을 수 있음
단점: 메모리를 더 많이 쓰는 편임

적합한 경우는 다음과 같습니다.

중복 확인
빈도 수 집계
캐시 키 저장
사용자 ID 기준 조회

해시 테이블의 핵심은 “O(1)” 자체보다 평균적으로 빠르지만 충돌과 메모리 비용이 있다는 점입니다.
즉, 빠른 탐색을 원할 때 가장 먼저 검토하지만, 정렬 순서나 범위 탐색이 중요하면 트리 계열 구조가 더 맞을 수 있습니다.

트리와 힙

트리(Tree)는 계층 구조와 정렬된 탐색을 표현할 때 자주 등장합니다.

트리: 부모-자식 관계를 가진 계층 구조
이진 탐색 트리(BST): 정렬된 탐색을 위한 트리 구조
힙(Heap): 최댓값 또는 최솟값을 빠르게 꺼내기 위한 구조

구조	강점	적합한 경우
트리	계층 구조 표현에 적합	파일 시스템, 조직도, 파싱 트리
BST	정렬된 탐색에 유리	ordered set, 범위 탐색
힙	우선순위 원소 추출에 유리	우선순위 큐, 스케줄링, Top-K

힙을 설명할 때 중요한 점은 전체 정렬 구조가 아니라 루트 우선순위를 빠르게 유지하는 구조라는 점입니다.

예를 들어:

가장 우선순위가 높은 작업을 계속 꺼내야 할 때
상위 N개만 빠르게 유지해야 할 때
Dijkstra, 스케줄러 같은 문제에서 최소/최대 원소를 반복 추출할 때

즉, 트리와 힙은 둘 다 계층 구조처럼 보이지만 용도가 다릅니다.

언제 어떤 자료구조를 선택할까

자료구조 선택은 보통 다음 질문 순서로 정리하면 좋습니다.

가장 중요한 연산이 무엇인가
- 조회, 삽입, 삭제, 정렬, 우선순위 추출 중 무엇이 핵심인가
순서가 중요한가
- 입력 순서, 정렬 순서, 우선순위 순서가 필요한가
중복과 존재 여부 확인이 중요한가
- 그렇다면 해시 기반 구조가 유리할 수 있음
범위 탐색이 중요한가
- 단순 해시보다 정렬 구조나 트리 계열을 검토
메모리 비용을 얼마나 감수할 수 있는가
- 빠른 탐색을 얻는 대신 메모리를 더 쓰는 구조도 많음

좋은 답변은 “배열을 썼습니다”가 아니라,
이 문제에서 가장 중요한 연산이 조회였고, 인덱스 접근이 많아서 배열이 맞았다처럼 연산 기준으로 설명하는 답변입니다.

코드 예시

아래 예시는 해시 테이블을 이용해 중복 여부를 빠르게 확인하는 기본 패턴입니다.

function hasDuplicate(values) {
  const seen = new Set();

  for (const value of values) {
    if (seen.has(value)) {
      return true;
    }
    seen.add(value);
  }

  return false;
}

이 예시에서 중요한 포인트는 다음과 같습니다.

Set은 해시 기반 구조라 평균적으로 빠른 존재 여부 확인이 가능합니다.
배열을 매번 순회하면 중복 확인 비용이 커질 수 있습니다.
메모리를 더 쓰는 대신 탐색 시간을 줄이는 전형적인 트레이드오프입니다.

면접 포인트

자료구조는 이름을 외우는 문제가 아니라, 어떤 연산이 중요한지에 따라 선택하는 문제입니다.
배열은 빠른 인덱스 접근, 연결 리스트는 삽입/삭제 패턴, 해시는 빠른 존재 여부 확인에 강합니다.
힙은 정렬 구조라기보다 우선순위 원소를 빠르게 꺼내는 구조로 설명하는 편이 좋습니다.
자료구조 답변은 시간 복잡도와 공간 복잡도를 같이 말해야 강해집니다.
좋은 답변은 자료구조 선택 이유를 연산 패턴과 연결해서 설명합니다.

참고 자료

Introduction to Algorithms (CLRS)
MIT OpenCourseWare, Introduction to Algorithms