자료구조 - 배열과 연결리스트

자료구조 (배열, 연결리스트, 시간복잡도)

컴퓨터 과학에서 가장 먼저 배우는 두 자료구조가 배열과 연결리스트다. 두 구조는 데이터를 메모리에 어떻게 늘어놓을 것인가에 대한 가장 본질적인 두 답이며, 이후 등장하는 모든 고급 자료구조(스택·큐·트리·해시·그래프)가 이 둘의 변형이거나 조합이라고 해도 과언이 아니다. 본 글은 정보처리기사 시험 출제 범위와 학교 자료구조 수업 입문 영역을 모두 닿도록 배열과 연결리스트의 메모리 구조, 시간복잡도, 실전 선택 기준을 정리한다(출처: Python 공식 자료구조 문서). 제가 학교 자료구조 수업에서 처음 두 구조의 시간복잡도 표를 봤을 때 솔직히 "그래서 무엇을 언제 쓰라는 거지?" 한 줄로 정리되지 않아 한참 헤맸는데, 직접 두 구조로 같은 알고리즘을 짜고 실행 시간을 재 본 후로는 "임의 접근이 많은가, 중간 삽입이 많은가" 한 줄로 선택 기준이 정리되었다.

 

배열 자료구조의 메모리 구조와 시간복잡도

배열(Array)은 같은 타입의 데이터를 연속된 메모리 공간에 일렬로 늘어놓는 가장 기본적인 자료구조이다. 가장 큰 특징은 메모리가 연속적이라는 점이며, 이 한 가지 특성에서 배열의 모든 강점과 약점이 파생된다. 메모리가 연속되어 있기 때문에 i번째 원소의 주소는 시작 주소 + i × 원소 크기라는 단순한 산술 연산으로 계산되며, 그 결과 배열은 인덱스만 알면 O(1) 시간에 어떤 원소든 곧바로 꺼낼 수 있다. 여기서 임의 접근(Random Access)이란 인덱스로 직접 위치를 계산해 한 번에 도달하는 접근 방식을 의미하며, 배열의 가장 결정적인 강점이다.

배열은 크게 정적 배열과 동적 배열로 나뉜다. 정적 배열(Static Array)은 컴파일 시점에 크기가 정해져 변경할 수 없는 형태로, C/C++의 int arr[10] 같은 선언이 대표적이다. 동적 배열(Dynamic Array)은 실행 중에 크기를 늘릴 수 있는 형태로, 파이썬 list, 자바 ArrayList, C++ std::vector가 모두 여기에 속한다. 동적 배열은 내부적으로 더 큰 새 배열을 할당하고 기존 원소를 복사하는 방식으로 확장되며, 이 확장 비용은 평균(amortized) O(1)로 분석된다. 분할 상환 분석(amortized analysis)이란 가끔 발생하는 큰 비용을 자주 발생하는 작은 비용에 평균적으로 나누어 평가하는 분석 기법을 가리킨다.

// C — 정적 배열, 크기 고정
int arr[5] = {10, 20, 30, 40, 50};
printf("%d\n", arr[2]);   // O(1) 임의 접근 → 30

// 중간 삽입은 O(n) — 뒷쪽을 한 칸씩 밀어야 함
for (int i = 4; i > 2; i--) arr[i] = arr[i-1];
arr[2] = 99;              // 이제 arr = {10, 20, 99, 30, 40}

배열의 시간복잡도를 표로 정리하면 다음과 같다.

연산	시간복잡도	비고
인덱스 접근	O(1)	가장 큰 강점
맨 뒤 삽입(append)	평균 O(1), 최악 O(n)	동적 배열 확장 시
맨 앞·중간 삽입	O(n)	뒤 원소들을 한 칸씩 밀어야 함
맨 앞·중간 삭제	O(n)	뒤 원소들을 한 칸씩 당겨야 함
탐색(값으로 찾기)	O(n)	정렬되어 있다면 이진 탐색으로 O(log n)

배열의 또 다른 강점은 캐시 친화성이다. 메모리가 연속되어 있어 CPU가 한 원소를 읽을 때 그 주변까지 캐시에 함께 들고 오기 때문에, 순회 작업의 실제 속도가 연결리스트보다 압도적으로 빠른 경우가 많다. 솔직히 이건 예상 밖이었는데, 이론상 같은 O(n)인 순회 작업도 배열이 연결리스트보다 3~10배 빨리 끝나는 모습을 직접 측정한 후로는 시간복잡도 표 한 장이 전부가 아니라는 점을 손끝으로 받아들였다.

연결리스트, 동적 메모리와 노드 연결

연결리스트(Linked List)는 데이터를 메모리의 흩어진 곳에 두고, 각 노드(Node)가 다음 노드를 가리키는 포인터로 연결해 순서를 표현하는 자료구조이다. 메모리 연속성을 포기하는 대신 크기 변경과 중간 삽입·삭제의 자유도를 얻는다. 한 노드는 데이터 값과 다음 노드를 가리키는 포인터(C에서는 next, 자바에서는 참조)를 함께 가지며, 이 단위가 사슬처럼 이어진다.

연결리스트는 연결 방향에 따라 세 종류로 나뉜다. 첫째, 단일 연결리스트(Singly Linked List)는 각 노드가 다음 노드만 가리키는 가장 단순한 형태이다. 둘째, 이중 연결리스트(Doubly Linked List)는 각 노드가 다음과 이전 두 방향을 모두 가리켜, 양방향 순회와 임의 노드 삭제가 모두 O(1)에 가능하다. 셋째, 원형 연결리스트(Circular Linked List)는 마지막 노드가 다시 첫 노드를 가리키는 형태로, 순환 구조가 필요한 라운드 로빈 스케줄링 같은 영역에서 활용된다. 여기서 라운드 로빈이란 정해진 순서대로 자원을 순환하며 분배하는 운영체제의 CPU 스케줄링 기법을 의미한다.

# Python — 단일 연결리스트
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, value):       # O(1) — 맨 앞 삽입
        node = Node(value)
        node.next = self.head
        self.head = node

    def insert_after(self, target, value):  # O(1) — 노드 뒤에 삽입
        node = Node(value)
        node.next = target.next
        target.next = node

    def get(self, idx):                # O(n) — 인덱스 접근
        cur = self.head
        for _ in range(idx):
            if cur is None: return None
            cur = cur.next
        return cur.value

연결리스트의 시간복잡도를 표로 정리하면 다음과 같다.

연산	시간복잡도	비고
인덱스 접근	O(n)	처음부터 따라가야 함
맨 앞 삽입·삭제	O(1)	가장 큰 강점
알려진 노드 뒤 삽입·삭제	O(1)	포인터만 갈아 끼움
맨 뒤 삽입	O(n) 또는 O(1)*	* tail 포인터 유지 시 O(1)
탐색(값으로 찾기)	O(n)	정렬해도 이진 탐색 불가

연결리스트의 결정적 강점은 포인터 갈아 끼우기만으로 끝나는 중간 삽입·삭제이다. 배열은 한 원소를 중간에 넣으려면 뒤의 모든 원소를 한 칸씩 밀어야 하지만, 연결리스트는 인접 노드 두 개의 포인터만 갱신하면 끝난다. 다만 인덱스 i번째 노드를 찾으려면 처음부터 i번 따라가야 하므로, 임의 접근은 O(n)이다. 또 노드마다 포인터 공간이 추가로 필요해 메모리 오버헤드가 배열보다 크고, 메모리가 흩어져 있어 캐시 효율도 낮다.

제가 학교 프로젝트에서 처음 단일 연결리스트를 직접 짜 본 게 학생 수강신청 대기열을 구현하는 과제였는데, 등록 취소가 빈번한 상황에서 배열로 짜다가 매번 뒤 원소를 다 미는 비용이 누적되어 결국 연결리스트로 갈아 끼운 경험이 있다. 그 한 번의 비교가 두 구조의 차이를 가장 직관적으로 가르쳐 준 사례였다.

배열과 연결리스트, 언제 무엇을 쓸 것인가

두 구조의 선택은 결국 "어떤 연산이 가장 자주 일어나는가"라는 한 질문으로 좁힌다. 임의 접근(인덱스 조회)이 많은 환경이라면 배열, 중간 삽입·삭제가 많은 환경이라면 연결리스트가 자연스러운 선택이다. 다음 표는 시험과 실무 모두에서 자주 참조되는 비교표이다(출처: 위키백과 — Introduction to Algorithms).

기준	배열	연결리스트
메모리 배치	연속	불연속
인덱스 접근	O(1)	O(n)
맨 앞 삽입·삭제	O(n)	O(1)
중간 삽입·삭제(노드 알면)	O(n)	O(1)
크기 변경	가능(동적 배열)	항상 가능
캐시 효율	매우 좋음	나쁨
메모리 오버헤드	작음	노드당 포인터 추가

실전에서 자주 헷갈리는 지점이 "파이썬 list가 배열인가 연결리스트인가"이다. 결론부터 말하면 파이썬 list는 동적 배열이며, 자바의 ArrayList와 같은 부류이다. 자바의 LinkedList만이 진짜 연결리스트이고, 따라서 파이썬에서 큐를 만들고 싶을 때 list.pop(0)을 쓰면 O(n)이 되는 사고가 자주 발생한다. 이 경우에는 collections.deque가 양방향 연결리스트에 가까운 구현체를 제공하므로 그쪽을 선택해야 한다(출처: Python collections — deque). 솔직히 제 경험상 학교 알고리즘 과제에서 가장 자주 시간 초과가 났던 사고가 정확히 list.pop(0) 한 줄이었고, 그 한 줄을 deque.popleft()로 갈아 끼우는 것만으로도 시간이 5배 이상 줄어드는 경험을 직접 했다.

마지막으로 정보처리기사 실기 답안에서 자주 쓰이는 정형 표현 하나를 정리해 두면, "배열은 임의 접근에 강하고 삽입·삭제에 약하며, 연결리스트는 그 반대이다. 따라서 인덱스 기반 조회가 많으면 배열을, 중간 삽입·삭제가 많으면 연결리스트를 선택한다"라는 두 문장이다. 시험에서 한 줄짜리 비교 답안을 요구할 때 이 두 문장이 그대로 쓰일 만큼 표준화된 표현이며, 그 뒤에 시간복잡도 표를 곁들이면 가장 단단한 답안이 된다. 다음 글에서는 이 두 구조 위에 책임을 부여해 만든 첫 추상 자료형(ADT)인 스택과 큐를 이어 다룬다.

---

메타 디스크립션: 배열과 연결리스트의 메모리 구조, 시간복잡도, 실전 선택 기준을 비교표·코드 예시·실무 사례와 함께 자료구조 입문자 관점에서 세심하게 정리합니다.