1. 배열(array)
배열의 각 데이터를 배열 요소라 하고 배열의 위치를 인덱스라고 한다.
(1) 장점
메모리 영역에 연속적으로 존재한다.
(2) 단점
배열의 개수를 결정하면 확대 또는 축소할 수 없다.
2. 동적 배열(vector)
배열과 유사하지만 크기(capacity)를 능동적으로 조절할 수 있다.
메모리 영역에 연속적으로 존재한다.
배열 요소(size)가 용량(capacity)보다 많아지면 데이터를 통째로 복사해서 새로운 메모리 영역으로 이동한다.
이 때, 새로운 메모리 영역에서 Capacity는 Size의 크기의 1.5배 ~ 2배이다.
(1) 장점
배열의 개수를 능동적으로 확대 또는 축소할 수 있다.
(2) 단점
배열 요소가 많아지면(size > capacity) 통째로 다른 영역으로 복사해야되므로 리소스 소모가 발생함.
중간 삽입 / 삭제가 비효율적으로 작동함.
(요소를 밀어내면서 불필요한 복사가 자주 일어남)
3. 이중 연결 리스트(list)
데이터가 메모리 영역에 불연속적으로 분포함.
각 노드에 이전 / 이후 노드의 위치를 포인터의 형태로 저장하고 있음.
헤더가 마지막 노드과 처음 노드에 연결되어 있음.
(1) 장점
중간 삽입/삭제가 효율적으로 작동함.
(2) 단점
임의 접근(Random Access)이 불가.
'자료구조와 알고리즘 > 선형 자료구조 & 그래프' 카테고리의 다른 글
| 2-1. 그래프 기초 (0) | 2023.07.06 |
|---|---|
| 1-8. 오른손 법칙 개선하기 (0) | 2023.07.04 |
| 1-7. 큐(Queue) (0) | 2023.07.04 |
| 1-5. 이중 배열 리스트(List) - 구현 복습 (0) | 2023.06.30 |
| 1-4. 동적 배열(vector) - 구현 복습 (0) | 2023.06.29 |