배열과 연결 리스트의 핵심 개념 요약은 무엇인가요?

선형 자료구조의 양대 산맥인 배열(정적/동적 배열)과 연결 리스트(단일/이중/원형)의 메모리 배치 원리 및 연산별 시간 복잡도를 비교 분석합니다. 핵심 정리: 배열은 연속된 메모리 공간에 할당되어 인덱스를 통한 임의 접근(Random Access)이 O(1)에 가능하다. 배열의 중간에 원소를 삽입하거나 삭제하면 뒤쪽 원소들을 이동시켜야 하므로 O(N)의 시간이 소요된다. 연결 리스트는 포인터로 노드를 연결하여 삽입/삭제 자체는 O(1)이지만, 특정 위치 탐색에 O(N)이 걸린다. 데이터 조회와 순회가 빈번하면 캐시 지역성이 뛰어난 동적 배열을, 양끝/중간 삽입·삭제가 빈번하면 연결 리스트(Deque)를 선택한다.

개념 정리

글자

배열과 연결 리스트

단원 개요

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

선수 개념

필수 키워드:연속된 메모리 할당빈틈없이 연속된 공간

O(1)

삽입과 삭제의 한계 (

O(N)

)

O(N)

노드(Node)와 포인터 연결노드(Node)연산별 시간 복잡도탐색(Access / Search)Head

이 단원의 내용

1배열 (Array)과 임의 접근(Random Access)의 원리 2연결 리스트 (Linked List)의 구조와 종류 3동적 배열(Dynamic Array)의 분할 상환 분석과 실무 선택 기준

배열 (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)가 동일하고 메모리상에 연속으로 붙어 있어 '시작 주소 + 인덱스 × 크기'로 주소를 단번에 계산하기 때문입니다.

연결 리스트 (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)

에 가능함(실무 표준).

풀이

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개입니다.

동적 배열(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)로 처리하세요!

핵심 요약

✓
배열은 연속된 메모리 공간에 할당되어 인덱스를 통한 임의 접근(Random Access)이 O(1)에 가능하다.
✓
배열의 중간에 원소를 삽입하거나 삭제하면 뒤쪽 원소들을 이동시켜야 하므로 O(N)의 시간이 소요된다.
✓
연결 리스트는 포인터로 노드를 연결하여 삽입/삭제 자체는 O(1)이지만, 특정 위치 탐색에 O(N)이 걸린다.
✓
데이터 조회와 순회가 빈번하면 캐시 지역성이 뛰어난 동적 배열을, 양끝/중간 삽입·삭제가 빈번하면 연결 리스트(Deque)를 선택한다.

배열과 연결 리스트

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

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

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

핵심 요약

설명 다음에는 직접 풀어 보세요

배열과 연결 리스트 단원 연습 문제

참고 근거와 확인 범위