인프런 강의 "기출로 대비하는 개발자 전공면접 [CS 완전정복]" 정리
Array
- 연관된 data를 메모리상 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조
- Linked List와는 메모리에 저장하는 방식과 연산 속도(시간복잡도)에서 차이
- 특징 : 고정된 저장 공간, 순차적인 데이터 저장
- 시간복잡도
- insertion, deletion, search가 O(n)인 이유 : n개의 이동이 필요하기 때문
| access |
O(1) |
| append |
O(1) |
| 마지막원소 delete |
O(1) |
| insetion |
O(n) |
| deletion |
O(n) |
| search |
O(n) |
Q. 예상했던거 보다 더 많은 수의 data를 Array에 저장하려면?
A. 기존 size보다 더 큰 Array를 선언하고 데이터를 모두 옮긴 후 기존의 것은 메모리에서 삭제하기 → Dynamic Array
- 사이즈의 크기를 예측하기 어렵다면 Linked List 사용하기
Dynamic Array
- resize
- 사이즈를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮김
- 대표적인 방법은 Doubling : 기존 배열의 size보다 두 배 큰 배열 선언
- append의 시간복잡도 : 가끔 발생하는 O(n)의 시간을 O(1)의 작업이 나눠가지는 amortized O(1)
| Doubling |
O(n) |
| Dynamic Array에 데이터 추가 |
O(1) |
| appned |
amortized O(1) |
- Linked List와 비교한 Dyamic Array의 장단점
- 장점 : 접근과 할당이 빠름, 맨 뒤에 data를 추가하거나 삭제하는 것이 상대적으로 빠름 O(1)
- 단점 : 중간에 data를 insert 하거나 remove할 때 느린 편 O(n) , resize 시 현저히 낮은 performance와 필요 이상의 메모리 할당
Linked List
- Node라는 구조체로 이루어짐
- Node = 데이터값 + next address
- 물리적인 메모리 상에서는 비연속적이지만 next address가 논리적 연속성 보장
- next address를 추가적으로 저장해야하기 때문에 데이터 하나당 차지하는 메모리가 커짐
- 데이터가 추가되는 시점에 메모리를 할당 → 효율적인 사용 가능
- 시간복잡도
- insert, deletion : next address가 가르키는 주소값만 변경하면 되기 때문에 O(1)
- access, search : next address를 통한 순차적인 접근만 가능하기 때문에 O(n)
| access |
O(n) |
| search |
O(n) |
| insertion |
O(1) |
| deletion |
O(1) |
Array vs Linked List
- 주된 차이점은 메모리 구조에 기인
- 조회
- Array : 메모리 상에서 연속적인 저장, 즉시 접근이 가능 O(1)
- Linked List : 메모리 상에서 불연속적 저장, 순차 접근만 가능 O(n)
- 삽입/삭제
- Array : 마지막에 원소를 추가/삭제하면 O(1), 중간에 원소를 삽입, 삭제하면 원소를 shift해야 해서 O(n)
- Linked List : shift할 필요가 없어서 O(1), 그러나 실질적으로는 index 도달까지 O(n)이 걸리기 때문에 O(n)이 걸린다고 볼 수 있음
- 메모리
- Array : 데이터 접근, append가 빠름 / 메모리 낭비 발생
- Linked List : 유연한 size 조절, 필요한 만큼 메모리 할당
- Linked List를 써야 하는 상황
- 삽입/삭제를 자주해야할 때
- 들어올 데이터의 크기를 예측할 수 없을 때
- 조회 작업을 많이 하지 않을 때
- Array를 써야 하는 상황
- 조회 작업을 자주해야 할 때
- 데이터의 갯수를 미리 알고 있을 때
- 데이터를 반복문을 통해 빠르게 순회할 때
- 메모리를 적게 쓰는 게 중요한 상황일 때
- Array와 Linked List의 메모리 할당 시점
- Array : compile단계
- Linked List : runtime 단계