[C++] Linked List, Vector, Deque

1. Linked List (#include <list>)

정의: 노드들이 메모리 상에 퍼져서 분포하며,

각 노드에는 Data와 다음 노드를 가리키는 Link로 이루어진 자료구조이다.

Index 접근이 불가능하다.

 

(C++ STL List: Double Linked List)

 

Search: O(n)

Insert: O(1)

Delete: Search + O(1)

 

장점: 삽입이 빠르다.

단점: 선형 탐색을 사용하여 탐색이 느리다. link pointer에 대한 추가 메모리가 발생한다.

 

 

 

 

 

2. Vector (#include <vector>)

정의: 크기가 변하는 동적 배열 자료구조이다. 배열의 크기가 기존보다 커지면 원래 크기의 2배씩 늘린다.

이때, 배열을 복사하여 다른 메모리에 저장하여 배열의 크기를 증가시킨다. (Dynamic Array)

연속적인 메모리 구조이며 Index 접근이 가능하다.

 

Search: O(n)

Insert: O(1) 

Delete: O(1)

 

만약 Sorted Vector를 구현한다면 이진 탐색을 사용하여 빠른 탐색을 수행할 수 있다.

대신 끝 삽입과 삭제의 시간 복잡도가 증가한다. [O(log n)]

 

장점: 끝 부분 삽입/제거가 O(1)으로 매우 빠르다. Index 접근 및 모든 순회 가능

단점: 끝이 아닌 삽입/제거는 느리다. 확장시 큰 오버헤드가 발생한다.

 

 

 

 

 

3. Deque (#include <deque>)

정의: Deque는 Vector의 단점을 보완하기 위해서 만들어진 자료구조로, 앞뒤로 Push/Pop이 가능한 자료구조이다.

 

Vector와 마찬가지로 Dynamic Array이며 Index 접근이 가능하다.

Vector와 다른 점은 불연속적인 메모리로, Chunk를 통해 관리된다.

(오버헤드 감소)

 

Search: O(n)

Insert: O(1)

Delete: O(1)

 

만약 Sorted Deque를 구현한다면 이진 탐색을 사용하여 빠른 탐색을 수행할 수 있다.

대신 시작과 끝 삽입과 삭제의 시간 복잡도가 증가한다. [O(log n)]

 

장점: 시작과 끝 부분 삽입/제거가 O(1)으로 매우 빠르다. Index 접근 및 모든 순회 가능

단점: 끝이 아닌 삽입/제거는 느리다. 불연속적 메모리 공간이라 포인터 연산은 불가능