자료구조 정리 - 배열(Array)과 리스트(List)

배열 (Array)

핵심 개념:

• 연속된 메모리 공간에 같은 타입의 데이터를 저장
• 인덱스로 직접 접근 가능 (Random Access)
• 크기가 고정됨 (정적 배열 기준)

시간복잡도:

• 접근(Access): O(1) - 인덱스로 바로 접근
• 탐색(Search): O(n) - 순차 탐색 필요
• 삽입(Insert): O(n) - 중간 삽입 시 뒤 요소들을 밀어야 함
• 삭제(Delete): O(n) - 중간 삭제 시 뒤 요소들을 당겨야 함

장점:

• 인덱스 접근이 매우 빠름
• 메모리 효율적 (연속 배치로 캐시 친화적)
• 구조가 단순함

단점:

• 크기 변경 불가 (정적 배열)
• 중간 삽입/삭제가 비효율적
• 메모리 낭비 가능 (미리 크기를 크게 잡으면)

 

리스트 (List) - 동적 배열

핵심 개념:

• 크기가 동적으로 변하는 배열
• 내부적으로 배열을 사용하되, 꽉 차면 더 큰 배열을 새로 만들어 복사
• Python의 list, Java의 ArrayList, C++의 vector가 이것

시간복잡도:

• 접근(Access): O(1)
• 탐색(Search): O(n)
• 끝에 삽입(Append): O(1) - 평균적으로 (가끔 O(n)인 resize 발생)
• 중간 삽입(Insert): O(n)
• 끝에서 삭제: O(1)
• 중간 삭제(Delete): O(n)

리사이징 메커니즘:

• 용량이 꽉 차면 보통 2배 크기의 새 배열 생성
• 기존 데이터를 복사 (이때만 O(n))
• 분할상환 분석(Amortized Analysis)으로 평균 O(1)

 

연결 리스트 (Linked List)

핵심 개념:

• 노드들이 포인터로 연결된 구조
• 각 노드는 데이터 + 다음 노드 주소를 저장
• 메모리상에서 불연속적으로 배치

종류:

1. 단일 연결 리스트: 다음 노드만 가리킴
2. 이중 연결 리스트: 이전/다음 노드 모두 가리킴
3. 원형 연결 리스트: 마지막이 첫 노드를 가리킴

시간복잡도:

• 접근(Access): O(n) - 처음부터 순회 필요
• 탐색(Search): O(n)
• 앞/특정위치 삽입: O(1) - 해당 위치만 알면
• 앞/특정위치 삭제: O(1) - 해당 위치만 알면
• 주의: 특정 위치를 '찾는' 건 O(n)

장점:

• 크기 제한 없음
• 삽입/삭제가 O(1) (위치만 알면)
• 메모리를 필요할 때마다 할당

단점:

• Random Access 불가
• 포인터 저장으로 메모리 오버헤드
• 캐시 효율이 낮음

제공 하는 언어:

• Java: LinkedList 클래스 제공
• C++: std::list (이중 연결 리스트)
• C#: LinkedList<T>
• Python: collections.deque (양방향 큐지만 링크드리스트 기반)

제공 안 하는 언어:

• Python: 기본 list는 동적 배열 (링크드리스트 아님)
• JavaScript: 기본 Array는 동적 배열

 

 

배열 vs 연결리스트 선택 기준:

• 접근이 많다 → 배열
• 삽입/삭제가 많다 → 연결리스트
• 크기를 모른다 → 연결리스트 or 동적 배열
• 메모리가 중요하다 → 배열

단! 실제로는?

• 대부분 탐색작업이 압도적으로 많음
• 현대 CPU 구조상 캐싱미스가 많이 발생함
• 포인터를 추가로 저장해서 메모리 오버헤드가 많이 발생

- 대부분 링크드리스트가 비효율적임(다만, 특성상 후술할 트리, 그래프등은 링크드리스트로 표현할수밖에 없음)

 

정리: 언제 뭘 쓰나?

 

자료구조	구현 방식	이유
일반 배열/리스트	연속 메모리	크기 예측 가능, 접근 많음
동적 배열	배열 + 리사이징	크기 가변, 접근 많음
링크드리스트	포인터 연결	앞/중간 삽입삭제 많음
트리	포인터 연결	구조 가변적, 동적 확장
힙	배열	완전이진트리라서 가능
그래프	인접리스트/행렬	연결 관계 표현