배열(Array) vs 연결 리스트, 상황에 맞는 선택 기준 완벽 비교

자료구조의 세계에 처음 발을 들여놓고 기본 문법과 기초 지식을 습득하다 보면, 가장 먼저 만나게 되는 두 가지 형태의 선형(Linear) 자료구조가 있습니다. 바로 '배열(Array)'과 '연결 리스트(Linked List)'입니다. 이 두 자료구조는 데이터를 일렬로 순서대로 나란히 나열하여 저장한다는 공통된 목적을 가지고 있지만, 실제로 컴퓨터 내부에서 메모리(RAM)를 할당받아 데이터를 보관하는 방식과 동작 원리에서는 정반대의 특징을 보입니다. "어떤 상황에서 배열을 써야 가장 효율적이고, 언제 연결 리스트로 전환해야 최적의 성능을 낼 수 있을까?" 이 간단한 질문에 명확한 기준을 대답할 수 있다면, 여러분은 이미 데이터 최적화 설계의 출발선을 넘은 것입니다. 실무와 면접에서 단골로 등장하는 이 두 라이벌의 구조를 해부하고 상황에 따른 완벽한 선택 가이드를 제시해 드립니다.

1. 배열 (Array): 연속된 메모리의 든든한 지정석

배열은 가장 직관적이면서도 역사가 깊은 기본 자료구조입니다. 배열의 핵심 동작 원리를 한 단어로 요약하면 '연속성'입니다. 데이터를 메모리(RAM) 공간에 할당할 때 중간에 빈틈이나 띄어쓰기 없이 순서대로 차곡차곡 연속적인 블록 형태로 저장합니다.

1-1. 구조적 특징과 장점 (임의 접근과 캐시 지역성)

배열의 가장 막강한 무기는 인덱스(Index)를 통한 압도적인 조회 속도입니다. 영화관의 예약된 10열의 연석 좌석표를 떠올려 보십시오. 첫 번째 자리의 위치와 크기만 알고 있다면, 다섯 번째 자리의 위치를 찾기 위해 좌석 사이를 걸어 다니며 확인할 필요 없이 단순히 간단한 산술 계산 한 번이면 5번째 데이터가 있는 정확한 메모리 주소로 바로 점프할 수 있습니다. 이를 임의 접근(Random Access)이라고 하며, 데이터가 아무리 길어도 조회 시간 복잡도는 O(1)로 매우 신속합니다. 또한 데이터가 메모리에 옹기종기 모여 있기 때문에 컴퓨터 CPU가 데이터를 가져올 때 주변 데이터까지 한 번에 캐시(Cache) 메모리에 올려 효율적으로 처리하는 캐시 지역성(Cache Locality)의 큰 이점을 얻습니다.

1-2. 치명적인 단점 (데이터 추가와 삭제의 늪)

하지만 이 '연속성'이라는 강력한 장점이 무거운 단점으로 돌변하는 상황이 있습니다. 만약 10명의 지정석이 가득 찼는데, 중간에 새로운 1명이 끼어들려고 한다면 어떨까요? 중간 자리를 하나 비우기 위해서는 그 뒤에 앉은 모든 사람이 한 칸씩 옆으로 밀려 이동해야만 합니다. 데이터를 삭제할 때도 마찬가지로 빈칸을 없애기 위해 뒤의 데이터들이 당겨져야 하므로 데이터 복사와 이동(Shift)에 엄청난 리소스가 소모되어 삽입/삭제 속도가 느립니다 (O(n)). 게다가 최초 생성 시점에 미리 메모리 크기를 '10칸'처럼 고정적으로 선언해야 하므로, 크기를 넘어서게 되면 새로운 거대 배열을 짓고 전체 데이터를 이사(Copy)시켜야 하는 오버헤드 비용이 발생합니다.

2. 연결 리스트 (Linked List): 포인터로 엮은 보물찾기 쪽지

연결 리스트는 배열이 가진 '크기 고정'이라는 한계와 '데이터 추가/삭제의 비효율성'이라는 고질적인 단점을 타파하기 위해 고안되었습니다. 데이터들이 배열처럼 연속된 공간에 옹기종기 붙어있지 않고, 메모리상 여기저기에 무작위로 흩어져서 자유롭게 보관되는 형태입니다.

2-1. 구조적 특징과 장점 (유연한 크기 변화)

흩어진 데이터를 하나의 리스트로 인식하게 하는 비결은 바로 '포인터(Pointer)'입니다. 마치 보물찾기 게임과 같습니다. 첫 번째 쪽지(노드)를 찾으면, 그 쪽지 안에는 여러분의 실제 데이터와 함께 "다음 보물은 놀이터 미끄럼틀 아래에 묻혀 있어"라는 다음 데이터의 물리적 주소값(연결 고리)이 적혀있습니다. 따라서 데이터를 새롭게 추가하거나 삭제하고 싶다면 무거운 전체 데이터의 이동 없이, 단순히 앞뒤 데이터가 가리키고 있던 포인터의 화살표 방향만 새로운 데이터를 향하도록 살짝 묶어주거나 끊어주면 그만입니다. 메모리 용량이 허용하는 한 무제한으로 뻗어나갈 수 있는 유연한 동적 할당이 가장 큰 무기입니다.

2-2. 치명적인 단점 (느린 조회 속도와 메모리 낭비)

하지만 연결 리스트의 자유로움에는 대가가 따릅니다. 배열처럼 한 번에 원하는 5번째, 10만 번째 위치로 점프할 수 있는 인덱스 기능이 전혀 없습니다. 내가 5번째 보물을 찾고 싶다면, 반드시 1번째 쪽지를 읽고 2번째로, 다시 3번째로 쪽지의 지시를 순차적으로 따라가면서 이동(Sequential Access)해야만 찾을 수 있으므로 특정 데이터 조회가 매우 느립니다 (O(n)). 더군다나 순수 데이터뿐만 아니라 다음 주소를 가리키는 '포인터'까지도 함께 저장해야 하므로 추가적인 메모리 공간을 낭비한다는 구조적인 약점을 지닙니다.

3. 언제 무엇을 써야 할까? (실무 선택 가이드)

현업 시스템 구조 설계 시 절대적으로 우월한 자료구조는 존재하지 않으며 철저하게 데이터 변경 빈도와 조회 패턴에 맞추어 도구를 쥐어야만 최상의 애플리케이션 성능을 끌어낼 수 있습니다.

3-1. 배열(Array)을 선택해야 하는 상황

• 저장할 데이터의 전체 개수가 미리 고정되어 있고 명확할 때 (예: 1년 12개월의 월별 매출 통계)
• 데이터의 삽입/삭제가 거의 일어나지 않고, 특정 인덱스의 값을 수시로 빠르게 조회(Read)하고 반복 처리해야 하는 기능이 대다수일 때 (예: 주식 차트, 대시보드 데이터)

3-2. 연결 리스트(Linked List)를 선택해야 하는 상황

• 회원가입, 게시글 작성 등 데이터가 몇 개나 들어올지 미래를 예측하기 어렵고 수시로 변화할 때
• 리스트의 중간이나 맨 앞, 끝부분에 데이터의 추가(Insert)와 삭제(Delete)가 빈번하게 발생하는 시스템 (예: 음악 스트리밍 앱의 플레이리스트 생성/제거, 이미지 뷰어의 히스토리 관리)

[핵심 요약]
1. 배열은 메모리 상에 연속적으로 배치되어 인덱스로 빠른 접근(O(1))이 가능하지만, 중간 데이터 변경 시 성능 저하(O(n))가 발생합니다.
2. 연결 리스트는 포인터 화살표를 통해 흩어진 데이터를 유연하게 제어해 삽입과 삭제가 자유롭지만, 원하는 데이터를 찾는 속도는 느립니다.
3. 데이터의 변경이 많으면 리스트 구조를, 검색 및 빠른 조회가 잦다면 배열 구조를 선택하여 성능 최적화를 설계해야 합니다.