자료구조 - 배열, 링크드 리스트

배열 (Array)

배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조이다.

각 요소는 인덱스(index)로 고유하게 접근할 수 있고, 이 인덱스를 통해 빠르게 값을 조회할 수 있다.

arr = [10, 20, 30]
print(arr[1])  # 20

주요 특징

고정된 크기 : 선언 시점에 크기 결정 (동적 배열은 재할당으로 유동적 크기 가능)

연속된 메모리 공간 : 캐시 성능에 유리

인덱스를 통한 빠른 접근: O(1)

삽입/삭제 시 요소 이동 필요: O(n)

시간 복잡도 정리

삽입, 삭제시 모든 요소들이 재정렬 이루어진다고 가정했을 때 시간복잡도는 O(n)이 된다. 중간에 추가 or 삭제된 요소로 인해 이후의 요소들이 이동되어야 함. 즉 밀린다.

연산	설명	시간 복잡도
접근	인덱스로 바로 접근 가능	O(1)
삽입 (중간)	삽입 후 요소들을 한 칸씩 밀어야 함	O(n)
삭제 (중간)	삭제 후 요소들을 한 칸씩 당겨야 함	O(n)
추가 (맨 뒤)	일반적으로 O(1), 공간 부족 시 O(n) (재할당)

파이썬 list는 내부적으로 C의 동적 배열을 사용함 → 자동으로 크기 확장되지만, 재할당이 일어나면 복사 비용 발생

배열의 장점

• 빠른 조회 성능 → 랜덤 엑세스 가능 (O(1))
• 캐시 효율성 높음 → 연속된 메모리 접근
• 구현 간단 → 포인터/참조 등 없이도 사용 가능

배열의 단점

• 크기 고정 or 재할당 비용 큼
• 중간 삽입/삭제 시 요소 이동 필요 → 비효율
• 연속된 메모리 확보가 어려울 수 있음 → 큰 배열 선언 시 메모리 에러 가능
• 공간 낭비 발생 가능 (미리 크게 선언해야 하기때문에)

배열은 언제 유리한가

• 조회가 많고, 삽입/삭제가 적을 때
• 인덱스 기반 처리가 필요한 경우 (ex. DP 배열, 테이블 기반 알고리즘)
• 고정 크기 데이터를 다룰 때 (ex. RGB 이미지 데이터, 고정 사이즈 버퍼)

정적 배열 vs 동적 배열

정적 배열이란 프로그램을 실행하기 전에 크기가 고정되어 있는 배열을 말한다. 크기는 원칙적으로 프로그램 실행 도중에 바꾸지 못함.

동적 배열이란 실행 과정에서 크기를 변할 수 있는 배열을 말한다. 동적 배열을 벡터라는 이름으로 구현한 프로그래밍 언어도 있음!

링크드 리스트

링크드 리스트는 데이터를 저장하는 노드(Node)들이 포인터 또는 참조로 연결된 구조.

메모리는 비연속적으로 할당되며, 각 노드는 다음 노드를 가리키는 참조값(next)을 포함함.

head → [data | next] → [data | next] → null

구성 요소

data : 실제 값

next : 다음 노드를 가리키는 참조 (이중 연결 리스트는 prev도 있음)

주요 특징

• 연속된 메모리 불필요
• 크기 유동적
• 삽입/삭제가 빠름 (포인터만 바꾸면 됨)
• 순차 접근만 가능 → 탐색은 느림

시간 복잡도 정리

연산	단일 연결 리스트	이중 연결 리스트
접근	O(n)	O(n)
맨 앞 삽입/삭제	O(1)	O(1)
맨 뒤 삽입	O(n)*	O(1)**
중간 삽입/삭제	O(n)	O(n)

• tail 포인터 없으면 O(n)

  prev/next 모두 있어서 노드만 알면 포인터 수정으로 O(1)

링크드 리스트 종류

종류	설명
단일 연결 리스트	next만 존재, 단방향
이중 연결 리스트	prev, next 모두 존재, 양방향
환형 연결 리스트	마지막 노드가 처음 노드를 가리킴, 순환 가능

중간 삽입 할 때

새 노드 생성

새 노드의 next를 기존의 다음 노드로 연결

기존 노드의 next를 새 노드로 연결

Before
A → B

Insert C between A and B

After
A → C → B

new_node.next = current.next
current.next = new_node

중간 삭제할 때

삭제할 노드의 이전 노드를 찾음

이전 노드의 next를 삭제할 노드의 next로 연결

삭제할 노드는 더 이상 참조되지 않으므로 GC 대상 (Python)

Before
A → B → C

Delete B

After
A → C

current.next = current.next.next

링크드 리스트의 장점

• 삽입/삭제 효율적 (포인터만 수정)
• 크기 제한 없음 (필요할 때마다 노드 추가)
• 중간 노드 삽입/삭제 유리 → 큐, 스택, LRU 등에 적합

링크드 리스트의 단점

• 랜덤 엑세스 불가 → O(n) 순차 탐색 필요함
• 메모리 사용량 더 큼 (포인터 공간 포함)
• GC 없는 언어(C/C++)에선 메모리 해제 필요
• 포인터 잘못 다루면 체인 끊어짐 → 데이터 유실

파이썬에서는?

• list는 동적 배열 기반
• collections.deque는 이중 연결 리스트 기반
• 직접 구현하려면 Node 클래스 만들어야 함

실무 활용 예시

용도	설명
큐, 스택	삽입/삭제가 빠름
LRU 캐시	사용 순서대로 정렬, 삭제/이동 효율적
Undo/Redo	이중 연결 리스트로 이전/다음 상태 추적
그래프	인접 리스트 표현 시 노드 연결 방식 사용

배열 vs 링크드 리스트 종합적으로 비교

항목	배열(Array)	링크드 리스트(Linked List)
메모리 배치	연속적	비연속적
접근 속도	O(1)	O(n)
삽입/삭제	느림 O(n)	빠름 O(1) (위치 알면)
크기 관리	고정 or 재할당	유동적
구현 난이도	쉬움	중간 (포인터 조작 필요)
캐시 효율	높음	낮음
실무 예시	리스트, 배열 기반 처리	큐, 캐시, 연결된 상태 표현 등

마무리 핵심 요약

배열 : 조회 빠름, 삽입/삭제 느림, 캐시 친화적

링크드 리스트 : 조회 느림, 삽입/삭제 빠름, 메모리 유동적

파이썬 list는 배열, 진짜 링크드 리스트는 직접 구현 or deque