배열 vs 연결 리스트: 자료구조 선택 가이드와 실무 활용법

배열과 연결 리스트란?

자료구조를 선택할 때 가장 기본이 되는 두 가지, 배열(Array)과 연결 리스트(Linked List)는 데이터를 순차적으로 저장한다는 공통점이 있지만, 내부 구조와 성능 특성이 완전히 다릅니다. 올바른 자료구조 선택은 프로그램의 성능을 크게 좌우하므로, 각각의 특징을 정확히 이해하는 것이 중요합니다.

배열은 연속된 메모리 공간에 같은 타입의 데이터를 저장하는 구조입니다. 인덱스를 통해 O(1) 시간에 원하는 요소에 접근할 수 있습니다.

연결 리스트는 각 노드가 데이터와 다음 노드의 주소를 함께 저장하는 구조입니다. 노드들이 메모리 여기저기 흩어져 있으며, 포인터로 연결됩니다.

메모리 구조의 차이

배열의 메모리 할당

배열은 선언 시 연속된 메모리 블록을 할당받습니다. 예를 들어 int 배열 5개를 만들면, 메모리의 연속된 20바이트(int 4바이트 × 5)가 예약됩니다. 이러한 연속성 덕분에 인덱스 계산만으로 즉시 접근이 가능합니다.

// 배열 예시
int arr[5] = {10, 20, 30, 40, 50};
// 메모리: [10][20][30][40][50] - 연속적으로 배치
int value = arr[3]; // O(1) 시간에 40에 접근

연결 리스트의 메모리 할당

연결 리스트는 노드가 필요할 때마다 동적으로 메모리를 할당받습니다. 각 노드는 메모리의 임의의 위치에 존재하며, 다음 노드의 주소를 저장하여 연결을 유지합니다.

// 연결 리스트 노드 구조
struct Node {
    int data;
    Node* next;
};
// 메모리: 노드들이 흩어져 있고 포인터로 연결
// Node1(0x100) -> Node2(0x500) -> Node3(0x200)

주요 연산 성능 비교

접근(Access) 성능

배열: O(1) – 인덱스를 알면 즉시 접근 가능합니다. 시작 주소 + (인덱스 × 자료형 크기) 계산으로 위치를 바로 찾습니다.

연결 리스트: O(n) – 처음부터 순차적으로 탐색해야 합니다. n번째 요소에 접근하려면 n번의 포인터 이동이 필요합니다.

삽입/삭제(Insert/Delete) 성능

배열: 중간 삽입/삭제 시 O(n) – 뒤의 모든 요소를 이동시켜야 합니다. 맨 끝 삽입은 O(1)이지만, 크기가 고정되어 있어 확장이 어렵습니다.

연결 리스트: 삽입/삭제 위치를 알고 있다면 O(1) – 포인터만 변경하면 되므로 매우 빠릅니다. 다만 위치를 찾는 데 O(n)이 걸립니다.

// 연결 리스트 중간 삽입 예시
void insertAfter(Node* prevNode, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = prevNode->next; // 새 노드가 다음을 가리킴
    prevNode->next = newNode; // 이전 노드가 새 노드를 가리킴
    // 다른 노드들은 전혀 이동하지 않음!
}

실무에서의 선택 기준

배열을 사용해야 할 때

• 랜덤 접근이 빈번한 경우: 게임에서 좌표 배열, 이미지 픽셀 데이터
• 데이터 크기가 고정적: 요일 배열, 월별 데이터
• 캐시 효율이 중요한 경우: 연속 메모리로 인한 캐시 히트율 상승
• 메모리 오버헤드 최소화: 포인터 저장 공간이 불필요

연결 리스트를 사용해야 할 때

• 빈번한 삽입/삭제: 실시간 로그 시스템, 작업 큐
• 크기 예측 불가: 사용자 입력 기반 데이터
• 메모리 단편화 허용: 큰 연속 메모리 확보가 어려운 환경
• 중간 삽입이 주 연산: 우선순위 큐, LRU 캐시 구현

실무 활용 예시

음악 플레이어 재생목록: 곡 추가/삭제가 빈번하고 순차 재생이 주된 패턴이므로 연결 리스트(또는 이중 연결 리스트)가 적합합니다.

엑셀 데이터 처리: 특정 셀 접근이 빈번하고 전체 크기가 정해져 있으므로 배열(또는 2차원 배열)이 적합합니다.

웹 브라우저 히스토리: 앞/뒤로 가기 기능을 위해 이중 연결 리스트가 효율적입니다.

핵심 요약

배열은 인덱스 기반 빠른 접근(O(1))이 필요하고 크기가 고정적일 때 최적입니다. 메모리 효율성과 캐시 성능이 우수하지만, 중간 삽입/삭제는 비효율적입니다.

연결 리스트는 동적 크기 조정과 빈번한 삽입/삭제(O(1))가 필요할 때 적합합니다. 메모리를 유연하게 사용할 수 있지만, 특정 위치 접근은 느립니다(O(n)).

실무에서는 두 자료구조의 장점을 결합한 하이브리드 구조(예: 동적 배열인 ArrayList, 해시테이블)를 자주 사용합니다. 문제의 특성을 정확히 파악하여 적절한 자료구조를 선택하는 것이 효율적인 프로그래밍의 핵심입니다.