자료구조의 선택 기준

자료구조는 데이터를 담는 방식이자 비용의 약속이다

자료구조는 데이터를 저장하는 모양이다. 하지만 실무에서는 단순한 '담는 그릇'이 아니다. 어떤 자료구조를 선택하느냐에 따라 조회 속도, 삽입·삭제 비용, 메모리 사용량, 코드 복잡도가 달라진다.

예를 들어 사용자 목록에서 특정 ID를 자주 찾는 서비스가 있다고 하자. 데이터를 배열에 넣고 매번 처음부터 끝까지 찾으면 사용자가 많아질수록 느려진다. 반대로 ID를 키로 하는 해시 테이블을 사용하면 대부분의 경우 훨씬 빠르게 찾을 수 있다. 같은 기능이라도 자료구조 선택 하나로 성능 문제가 생기거나 사라진다.

좋은 자료구조 선택은 "가장 빠른 구조"를 고르는 일이 아니다. 내 코드에서 어떤 작업이 가장 자주 일어나는지를 보고, 그 작업에 맞는 비용 구조를 고르는 일이다. 데이터를 자주 읽는가, 중간에 자주 삽입하는가, 정렬된 상태가 필요한가, 우선순위가 중요한가, 관계를 표현해야 하는가. 이 질문에 대한 답이 자료구조 선택의 출발점이다.

AI 생성 이미지

배열과 연결 리스트: 메모리 배치가 성능을 바꾼다

배열은 일반적으로 같은 종류의 데이터를 메모리의 연속된 공간에 저장한다. 이 특징 덕분에 인덱스를 알고 있으면 원하는 위치에 바로 접근할 수 있다. arr[1000]처럼 특정 위치의 값을 읽는 작업이 매우 빠른 이유다. 언어에 따라 배열이 실제 값을 직접 담기도 하고 객체의 참조를 담기도 하지만, 핵심은 인덱스 기반 접근에 강하다는 점이다.

또 하나의 장점은 캐시 친화성이다. 앞에서 본 것처럼 CPU는 메인 메모리보다 캐시에 있는 데이터를 훨씬 빠르게 읽는다. 배열은 데이터가 연속적으로 배치되므로 하나의 값을 읽을 때 주변 값도 함께 캐시에 올라올 가능성이 높다. 반복문으로 배열을 순회할 때 빠른 이유가 여기에 있다.

하지만 배열은 중간 삽입과 삭제에 약하다. 중간에 값을 하나 넣으려면 뒤쪽 요소들을 한 칸씩 밀어야 한다. 삭제할 때도 빈자리를 메우기 위해 뒤쪽 요소들을 앞으로 당겨야 한다. 데이터가 적을 때는 티가 나지 않지만, 수십만 개 이상의 데이터를 자주 이동시키면 병목이 된다.

연결 리스트는 다른 방식으로 데이터를 저장한다. 각 요소를 노드라고 부르며, 노드는 값과 다음 노드의 위치 정보를 가진다. 메모리상에서 노드들이 연속되어 있을 필요가 없다. 한 노드가 다음 노드를 가리키는 식으로 이어진다.

연결 리스트의 장점은 삽입과 삭제다. 삽입할 위치의 앞 노드를 알고 있거나, 삭제에 필요한 앞뒤 연결 정보를 이미 알고 있다면 포인터만 바꾸면 된다. 배열처럼 뒤쪽 요소 전체를 밀거나 당길 필요가 없다. 그래서 중간 삽입·삭제가 많은 구조에서 유리해 보인다.

그러나 중요한 조건이 있다. 삽입하거나 삭제할 위치를 이미 알고 있을 때만 빠르다. 특정 값을 찾기 위해 처음부터 따라가야 한다면 시간이 오래 걸린다. 연결 리스트는 인덱스로 바로 접근할 수 없기 때문이다. 또한 각 노드가 다음 노드의 주소를 저장해야 하므로 메모리를 더 사용하고, 노드들이 흩어져 있으면 캐시 효율도 떨어진다.

실무에서는 연결 리스트가 항상 배열보다 삽입·삭제에 좋다고 단순히 외우면 위험하다. 실제 애플리케이션에서는 위치를 찾는 비용과 캐시 미스 비용이 함께 발생한다. 그래서 많은 언어의 기본 리스트 구현은 내부적으로 동적 배열을 사용한다. 동적 배열은 공간이 부족하면 더 큰 배열을 새로 만들고 기존 데이터를 복사한다. 이 과정은 비싸지만 매번 발생하지는 않는다. 특히 맨 뒤에 값을 추가하는 작업은 대부분 빠르게 처리된다.

따라서 선택 기준은 명확하다. 인덱스로 접근하거나 순차 순회가 많으면 배열 계열이 좋다. 중간의 특정 위치를 이미 알고 있고 삽입·삭제가 매우 잦다면 연결 리스트를 고려한다. 하지만 캐시 효율과 메모리 사용량까지 함께 봐야 한다.

스택과 큐: 처리 순서를 구조로 표현한다

스택과 큐는 데이터를 어떻게 저장하느냐보다 어떤 순서로 꺼내느냐가 중요한 자료구조다.

스택은 마지막에 넣은 데이터를 먼저 꺼낸다. 이를 LIFO, 즉 Last In First Out이라고 한다. 접시를 쌓아 놓으면 맨 위에 놓은 접시부터 꺼내는 것과 같다.

스택은 함수 호출에서 자연스럽게 등장한다. 함수가 호출되면 지역 변수와 복귀 위치 같은 정보가 호출 스택에 쌓인다. 함수가 끝나면 가장 최근에 호출된 함수부터 제거된다. 재귀 함수도 같은 원리로 동작한다. 재귀가 너무 깊어지면 스택 공간이 부족해져 스택 오버플로가 발생할 수 있다.

스택은 실행 취소 기능, 괄호 검사, 깊이 우선 탐색(DFS), 파서 구현에도 자주 사용된다. 핵심은 "가장 최근 작업을 먼저 처리해야 하는가"다. 그렇다면 스택이 자연스럽다.

큐는 먼저 넣은 데이터를 먼저 꺼낸다. 이를 FIFO, 즉 First In First Out이라고 한다. 줄을 선 사람이 먼저 서비스를 받는 구조다.

큐는 작업 처리 시스템에서 흔하다. 웹 서버가 요청을 받고, 백그라운드 워커가 작업을 가져가 처리하는 구조를 생각해 보자. 먼저 들어온 작업부터 처리해야 한다면 큐가 적합하다. 너비 우선 탐색(BFS)도 큐를 사용한다. 현재 위치에서 가까운 노드부터 차례대로 탐색해야 하기 때문이다.

실무에서는 큐가 단순한 자료구조를 넘어 시스템 설계 요소가 된다. 메시지 큐, 작업 큐, 이벤트 큐는 생산자와 소비자의 속도 차이를 흡수한다. 요청을 바로 처리하지 않고 큐에 넣으면 시스템은 순간적인 트래픽 증가를 더 안정적으로 견딜 수 있다. 다만 큐가 계속 쌓인다면 처리량이 부족하다는 신호다. 큐는 병목을 없애는 마법이 아니라 병목을 관찰하고 완충하는 장치다.

해시 테이블: 빠른 조회의 대가와 조건

해시 테이블은 키를 이용해 값을 빠르게 찾기 위한 자료구조다. 많은 언어의 Map, Dictionary, HashMap 같은 구조가 이 계열에 속한다. JavaScript의 Object처럼 객체 속성 저장 구조가 비슷한 역할을 하는 경우도 있지만, 언어마다 세부 구현과 제약은 다를 수 있다.

원리는 간단하다. 키를 해시 함수에 넣어 숫자로 바꾸고, 그 숫자를 내부 배열의 위치를 정하는 데 사용한다. 예를 들어 사용자 ID를 해시 함수에 넣어 특정 버킷을 고르면, 해당 위치에서 값을 찾는다. 잘 동작하면 삽입, 삭제, 조회가 평균적으로 매우 빠르다.

하지만 "항상 빠르다"는 뜻은 아니다. 해시 테이블의 성능은 세 가지에 크게 좌우된다.

첫째, 해시 함수의 품질이다. 좋은 해시 함수는 서로 다른 키를 가능한 한 고르게 분산시킨다. 특정 버킷에 키가 몰리면 한 위치에 데이터가 쌓이고, 조회할 때 추가 탐색이 필요하다.

둘째, 충돌 처리 방식이다. 충돌은 서로 다른 키가 같은 위치에 배정되는 현상이다. 충돌은 피할 수 없다. 그래서 해시 테이블은 같은 버킷 안에 여러 값을 연결하거나, 다른 빈 공간을 찾아 저장하는 방식으로 충돌을 처리한다. 충돌이 많아질수록 평균 성능은 나빠진다.

셋째, 적절한 크기 조정이다. 데이터가 늘어나면 해시 테이블은 내부 배열을 더 크게 만들고 기존 데이터를 다시 배치한다. 이를 리해싱이라고 한다. 리해싱 순간에는 비용이 크다. 그래서 대량 데이터를 넣을 때는 초기 용량을 적절히 잡는 것이 도움이 된다.

해시 테이블은 ID로 객체를 찾거나, 중복 여부를 검사하거나, 카운트를 집계할 때 강력하다. 예를 들어 로그에서 사용자별 요청 수를 세거나, 이미 처리한 이벤트 ID를 기록하는 경우에 적합하다.

반대로 정렬된 순서가 중요하거나 범위 검색이 필요하다면 해시 테이블은 맞지 않을 수 있다. "ID가 1000 이상 2000 이하인 사용자"를 찾는 작업은 해시 테이블보다 정렬된 트리나 인덱스 구조가 더 자연스럽다.

트리: 계층과 정렬된 검색을 표현한다

트리는 부모와 자식 관계로 데이터를 표현하는 자료구조다. 파일 시스템, HTML DOM, 조직도, 카테고리 구조처럼 계층이 있는 데이터를 나타내기에 좋다.

트리 중에서도 이진 탐색 트리는 검색을 설명할 때 자주 등장한다. 각 노드는 왼쪽에는 자신보다 작은 값, 오른쪽에는 자신보다 큰 값을 둔다. 이 규칙이 유지되고 트리가 적절히 균형을 이루면 값을 찾을 때 전체를 다 보지 않고 범위를 줄여 갈 수 있다.

하지만 트리는 균형이 중요하다. 데이터가 한쪽으로만 치우치면 트리라기보다 연결 리스트처럼 변한다. 그러면 검색 성능도 나빠진다. 그래서 실제 시스템에서는 균형을 유지하는 트리 구조가 사용된다. 데이터베이스 인덱스에서 자주 등장하는 B-Tree 계열도 이런 문제의식에서 출발한다. 많은 데이터를 디스크나 SSD에 저장할 때 접근 횟수를 줄이도록 설계된 트리 구조다.

트리는 다음 상황에서 특히 유용하다.

• 정렬된 상태로 데이터를 유지해야 할 때

• 최솟값, 최댓값, 이전 값, 다음 값을 자주 찾아야 할 때

• 범위 검색이 필요할 때

• 계층 구조를 표현해야 할 때

해시 테이블이 단일 키 조회에 강하다면, 트리는 순서와 범위를 다루는 데 강하다. 이 차이를 이해하면 데이터베이스 인덱스나 캐시 자료구조를 볼 때 판단이 쉬워진다.

힙: 가장 중요한 값을 빨리 꺼내는 구조

힙은 우선순위 큐를 구현할 때 많이 쓰이는 자료구조다. 우선순위 큐는 먼저 들어온 순서가 아니라 우선순위가 높은 데이터부터 꺼낸다.

대표적인 예는 작업 스케줄러다. 모든 작업을 들어온 순서대로 처리하는 것이 아니라, 마감 시간이 가까운 작업이나 중요도가 높은 작업을 먼저 처리해야 할 수 있다. 이때 힙을 사용하면 최댓값이나 최솟값을 빠르게 확인하고 꺼낼 수 있다.

힙은 완전히 정렬된 구조가 아니다. 전체 데이터가 순서대로 나열되어 있지는 않다. 대신 부모가 자식보다 작거나 큰 규칙만 유지한다. 최소 힙에서는 루트에 항상 가장 작은 값이 온다. 그래서 최솟값을 빠르게 확인하고 제거할 수 있다.

힙은 다음 문제에 잘 맞는다.

• 상위 N개 항목 찾기

• 가장 짧은 작업부터 처리하기

• 실시간 랭킹의 일부 유지하기

• 다익스트라 알고리즘처럼 현재 가장 비용이 작은 후보를 반복해서 선택하기

정렬이 필요하다고 해서 항상 전체 정렬을 할 필요는 없다. 필요한 것이 "전체 순서"인지 "가장 큰 값 또는 작은 값의 반복 추출"인지 구분해야 한다. 후자라면 힙이 더 단순하고 효율적일 수 있다.

그래프: 관계가 중심인 데이터를 다룬다

그래프는 노드와 간선으로 관계를 표현하는 자료구조다. 트리도 그래프의 한 종류지만, 일반적인 그래프는 더 자유롭다. 순환이 있을 수 있고, 한 노드가 여러 노드와 복잡하게 연결될 수 있다.

소셜 네트워크에서 사용자는 노드, 친구 관계는 간선이 된다. 지도 앱에서는 장소가 노드, 도로가 간선이 된다. 서비스 의존성 그래프에서는 서비스가 노드, 호출 관계가 간선이 된다.

그래프를 구현하는 대표 방식은 인접 리스트와 인접 행렬이다. 인접 리스트는 각 노드가 연결된 노드 목록을 가진다. 연결이 많지 않은 희소 그래프에 적합하고 메모리를 아낄 수 있다. 인접 행렬은 노드 간 연결 여부를 2차원 배열로 표현한다. 두 노드가 연결되어 있는지 빠르게 확인할 수 있지만, 노드 수가 많으면 메모리를 많이 사용한다.

그래프에서는 탐색 방식도 중요하다. BFS는 가까운 노드부터 넓게 탐색하므로 간선 가중치가 없거나 모두 같을 때 최단 단계 수를 구하는 데 유용하다. DFS는 한 방향으로 깊게 들어가며 탐색하므로 경로 탐색, 순환 감지, 위상 정렬 같은 문제에 자주 사용된다.

실무에서 그래프 사고는 장애 분석에도 도움이 된다. 하나의 서비스 장애가 어떤 서비스로 전파되는지, 배포 순서가 어떤 의존성을 가지는지, 권한 관계가 어떻게 이어지는지 이해할 때 그래프 모델이 유용하다.

선택 기준은 연산 패턴에서 나온다

자료구조를 고를 때는 이름보다 질문이 중요하다.

• 특정 위치를 자주 읽는가? 배열을 먼저 고려한다.

• 순서대로 많이 순회하는가? 배열이 캐시 효율 면에서 유리하다.

• 중간 삽입·삭제가 많고 위치를 이미 알고 있는가? 연결 리스트를 고려한다.

• 가장 최근 작업을 먼저 처리해야 하는가? 스택이 맞다.

• 먼저 들어온 작업을 먼저 처리해야 하는가? 큐가 맞다.

• 키로 값을 빠르게 찾아야 하는가? 해시 테이블이 강하다.

• 정렬된 순서와 범위 검색이 필요한가? 트리 구조가 적합하다.

• 최댓값이나 최솟값을 반복해서 꺼내야 하는가? 힙을 사용한다.

• 복잡한 관계와 경로를 표현해야 하는가? 그래프로 모델링한다.

자료구조 선택은 나중에 성능을 최적화하는 문제가 아니다. 처음부터 코드의 형태와 시스템 비용을 결정하는 설계 문제다. 데이터가 적을 때는 어떤 구조를 써도 비슷해 보인다. 하지만 데이터가 커지고 요청이 늘어나면 접근 패턴에 맞지 않는 자료구조가 병목이 된다.

좋은 개발자는 자료구조 이름을 많이 외우는 사람이 아니라, 데이터가 어떻게 사용되는지 보고 비용을 예측하는 사람이다. 어떤 작업이 자주 일어나는지, 데이터 크기가 얼마나 커질지, 순서와 관계가 중요한지, 메모리와 캐시에 어떤 영향을 주는지 묻는 습관이 필요하다. 그 질문이 좋은 자료구조 선택의 기준이 된다.