배열(Array)과 리스트(List) 개념 정리

배열 (Array)

배열의 특징

- 동일한 자료형을 가지는 데이터들의 집합
- 고정된 크기 (정적 할당)
- 연속된 메모리 공간에 저장됨
- Index 기반으로 빠른 조회 가능 (O(1))
- 삽입, 삭제 시 연산이 느림 (O(n)) (중간 요소 변경 시 모든 요소 이동이 필요하기 때문)

배열의 장점

- 메모리 접근 속도가 빠르다. (연속된 메모리 할당)
- Index 기반으로 빠른 조회 가능 (O(1))
- CPU 캐시 최적화가 가능

배열의 단점

- 크기가 고정됨 (Python 예외)
- 중간 삽입/삭제 시 비효율적 (뒤 요소들을 이동해야 함)

시간 복잡도

- 접근 (Access) : O(1)
- 삽입 (Insert) & 삭제 (Delete) : O(n)
 
 

리스트 (List)

리스트의 특징

- 크기가 동적으로 변경 가능 (가변 길이)
- 다양한 자료형 포함 가능 (Python)
- 동적 배열 or 연결 리스트로 구현됨

리스트의 장점

- 가변 크기로 사용 가능 → 데이터 추가/삭제가 자유로움
- 중간 삽입/삭제가 용이함
- 다양한 자료형 포함 가능 (Python)

리스트의 단점

- 연결 리스트 기반의 경우, 연속된 메모리 할당이 아님
- 배열보다 접근 속도가 느릴 수 있음.
- 캐시 최적화가 어려움

시간 복잡도

연산	배열 기반 리스트 (python)	연결 리스트
접근 (Access)	O(1)	O(n)
삽입 (Insert)	O(n)	앞쪽 - O(1), 중간 - O(n)
삭제 (Delete)	O(n)	앞쪽 - O(1), 중간 - O(n)

 
 

---

 

배열과 리스트 비교

	배열 (Array)	리스트 (List)
크기	고정 크기	가변 크기
자료형	단일 타입	여러 타입 가능 (python)
메모리 할당	연속적	비연속적 (Linked List)
접근 속도	O(1) - 빠름	배열기반:O(1), 연결 리스트 기반:O(n)
삽입/삭제	O(n) - 비효율적	앞쪽 - O(1), 중간 - O(n)
메모리 효율성	높음 (낭비 적음)	낮음 (포인터 추가로 인한 오버헤드)
데이터 저장 방식	연속된 메모리 공간	동적 배열 또는 연결 리스트
활용	정형화된 데이터를 다룰 때 사용	다양한 데이터 구조에서 활용