함께 배우는 수업 · 컴퓨터/정보

배열과 연결 리스트

선형 자료구조의 양대 산맥인 배열(정적/동적 배열)과 연결 리스트(단일/이중/원형)의 메모리 배치 원리 및 연산별 시간 복잡도를 비교 분석합니다.

이 수업에서 해 볼 일

접근 방식과 연결 변경 비용으로 자료구조를 선택한다

먼저 알면 좋은 것: 메모리 주소(번지)와 포인터(참조) 개념 · 캐시 메모리의 공간 지역성(Spatial Locality) · 기본 시간 복잡도 표기 ($O(1)$ 상수 시간과 $O(N)$ 선형 시간)

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

자료구조는 자주 하는 연산을 기준으로 고른다. 배열은 인덱스로 위치를 계산할 수 있고, 연결 리스트는 이웃 노드의 링크로 다음 위치를 찾는다.배열 앞 삽입은 뒤 원소들을 옮겨야 하지만, 연결 리스트에서 위치를 이미 알고 있다면 몇 개의 링크 변경으로 삽입할 수 있다. 위치를 찾는 탐색 시간은 별도로 세어야 한다.동적 배열 끝 삽입의 분할 상환 O(1)은 각 삽입의 최악 시간이 모두 O(1)이라는 뜻이 아니다. 드문 확장 비용을 여러 연산에 나누어 평가한 값이다.

1. 배열 (Array)과 임의 접근(Random Access)의 원리

- 연속된 메모리 할당: 배열은 동일한 타입의 원소들을 메모리상에 빈틈없이 연속된 공간에 배치하는 자료구조입니다. - 임의 접근 (Random Access, $O(1)$ ): - 배열의 시작 메모리 주소(

\text{Base Address}

)와 원소 하나의 바이트 크기(

\text{Size}

)를 알면,

i

번째 원소의 메모리 주소를 탐색 없이 수식 하나로 즉시 계산할 수 있습니다:

\text{Address}(A[i]) = \text{Base Address} + (i \times \text{Size})

- 따라서 배열의 길이가 10개든 1억 개든 상관없이 인덱스

i

를 통한 조회·수정 시간 복잡도는 항상 $O(1)$ 입니다. - 삽입과 삭제의 한계 ( $O(N)$ ): - 메모리 연속성을 유지해야 하므로, 배열의 맨 앞이나 중간에 새 원소를 끼워 넣거나 삭제하면 그 뒤에 있는 최대

N

개의 원소들을 한 칸씩 뒤로 밀거나 앞으로 당겨야(Shift) 하므로 $O(N)$ 의 비용이 듭니다.배열이 인덱스만으로 O(1) 만에 원소를 찾아갈 수 있는 이유는 모든 원소의 자료형 크기(Byte)가 동일하고 메모리상에 연속으로 붙어 있어 '시작 주소 + 인덱스 × 크기'로 주소를 단번에 계산하기 때문입니다.

2. 연결 리스트 (Linked List)의 구조와 종류

- 노드(Node)와 포인터 연결: 연결 리스트는 메모리 여기저기 흩어져 할당된 노드(Node)들을 포인터(참조 주소)로 사슬처럼 이어 붙인 자료구조입니다. 각 노드는 [데이터(Data) | 다음 노드 주소(Next Pointer)]로 구성됩니다. - 연산별 시간 복잡도: - 탐색(Access / Search): 메모리 주소가 불연속적이므로

k

번째 원소를 찾으려면 무조건 첫 번째 노드(Head)부터 포인터를 따라

k

번 이동해야 하므로 $O(N)$ 이 걸립니다. - 삽입 / 삭제: 삽입·삭제할 위치의 노드를 이미 가리키고 있다면, 주변 노드들의 포인터 연결선만 바꿔 끼우면 되므로 원소 이동 없이 $O(1)$ 만에 수행됩니다 (단, 그 위치를 처음부터 찾아가는 과정이 포함되면

O(N)

). - 연결 리스트의 변형: - 단일 연결 리스트 (Singly Linked List): 다음 노드로만 이동 가능(단방향). - 이중 연결 리스트 (Doubly Linked List): 이전 노드(prev)와 다음 노드(next) 양쪽 포인터를 모두 가져 양방향 이동과 끝 노드 삭제가

O(1)

에 가능함(실무 표준).

예제로 살펴보기

시작 주소가 1000번지이고 각 원소가 4바이트(32비트 정수)인 배열 A에서 A[25]의 메모리 주소를 구하고, 길이 1,000인 배열의 인덱스 2 위치에 새 원소를 삽입할 때 이동해야 하는 원소의 개수를 구하시오.

1) A[25]의 메모리 주소 계산 (인덱스는 0부터 시작): Address(A[25]) = 시작 주소 + (인덱스 × 원소 크기) = 1000 + (25 × 4) = 1000 + 100 = 1100번지입니다. 2) 인덱스 2 위치에 삽입 시 원소 이동 횟수: 길이 1,000인 배열의 기존 인덱스는 0부터 999까지입니다. 인덱스 2 자리에 새 원소를 넣으려면 기존 인덱스 2부터 999까지의 원소들을 모두 오른쪽으로 한 칸씩 밀어야 합니다. 따라서 이동해야 하는 원소의 개수는 999 - 2 + 1 = 998개입니다.

확인: 배열은 연속된 메모리 공간에 할당되어 인덱스를 통한 임의 접근(Random Access)이 O(1)에 가능하다.

3. 동적 배열(Dynamic Array)의 분할 상환 분석과 실무 선택 기준

- 동적 배열 (Python list, C++ std::vector, Java ArrayList): - 정적 배열의 고정 크기 한계를 극복하기 위해, 내부 배열이 꽉 차면 기존 용량의 약 2배(Doubling) 크기의 새 배열을 할당하고 기존 데이터를 복사합니다. - 가끔 용량 확장 시

O(N)

복사가 발생하지만, 맨 뒤에 원소를 추가(append)하는 연산을 평균 내면 분할 상환 시간 복잡도(Amortized Time Complexity) $O(1)$ 이 보장됩니다! - 배열 vs 연결 리스트 종합 비교표:

비교 항목	배열 (Array / Dynamic Array)	연결 리스트 (Linked List)
메모리 구조	연속 할당 (캐시 적중률 극대화)	불연속 동적 할당 (포인터 저장 공간 추가 소모)
인덱스 조회 (Access)	$O(1)$ (임의 접근)	$O(N)$ (순차 접근)
맨 앞/중간 삽입·삭제	$O(N)$ (원소 밀기/당기기)	$O(1)$ (포인터만 변경, 단 위치 탐색 시 $O(N)$ )
맨 뒤 삽입 (Append)	$O(1)$ (동적 배열 평균)	$O(1)$ (Tail 포인터 유지 시)

실무 코딩 테스트 팁: 파이썬에서 리스트 맨 앞에 원소를 넣거나 빼는 list.insert(0, x)나 list.pop(0)은 O(N) 시간이 걸려 시간 초과(TLE)의 주범이 됩니다. 양끝 삽입/삭제가 필요할 때는 반드시 이중 연결 리스트 기반인 collections.deque를 사용해 O(1)로 처리하세요!

참고 근거와 확인 범위

Harvard CS50 · Lecture 5: Data structures ↗
배열과 연결 리스트의 저장·접근·삽입

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →