링크드 리스트와 배열의 차이 - 작성완료

Stl Vector List 설명
   장단점
   간혹 둘중에 하나 그자리에서 짜보라고함

--------------------------------------------------------------------------------------------------------------

1. vector일반적인 배열처럼 vector는 개체들을 연속적인 메모리 공간에 저장한다.
즉, iterator 뿐 아니라 position index(operator [])로도 접근이 가능하다는 것이다.

vector는 동적으로 확장/축소가 가능한 dynamic array로 구현되어 있다.

강점

• 개별 원소들을 position index로 접근이 가능하다 (상수 복잡도)
• 원소를 컨테이너의 끝에 삽입/제거 하는 것이 빠르다 (상수-아모타이즈드 복잡도)
• 어떠한 순서로도 원소들을 순회할 수 있다. 즉, Random access iterating이 가능함. (로그 복잡도)

일반적으로 vector는 다른 두 개의 시퀀스 컨테이너인 deque, list에 비해 개별 원소에 대한 접근 속도와 컨테이너의 끝에서 삽입/제거하는 속도가 가장 빠르다.
굳이 "일반적으로" 빠르다는 표현을 쓴 것은 특정 상황별로 달라지기 때문이다.
이는 아래 내용들을 모두 읽어보고 종합적으로 분석해 보면 알 수 있다.

약점

• 컨테이너의 끝 위치가 아닌 곳에서 삽입/제거 수행시 그 성능은 deque/list에 비해 현저히 떨어진다.

주의

• 동적으로 컨테이너의 크기가 확장/축소되는 것이 편하기는 하나, 확장시의 reallocation은 비용이 꽤 크다.
• capacity를 확장 시켜줄 수 있는 적절한 크기의 reserve로 인한 메모리 확보가 중요.

2. deque (double ended queue)

deque는 어느 정도 vector와 유사성이 있는 듯하면서도 상당히 많이 다르다고도 할 수 있는 시퀀스 컨테이너다.

우선, Random access iterator를 통한 개별 원소에 대한 접근이 가능하다. operator []도 지원된다.
그리고, 컨테이너의 크기 역시 동적으로 조절되지만, 그 방법은 vector의 그것과 많이 다르다.

강점

• 개별 원소들을 position index로 접근이 가능하다.
• 원소를 컨테이너의 끝 뿐 아니라, 앞에서도 삽입/제거 하는 것이 빠르다.
• 어떠한 순서로도 원소들을 순회할 수 있다.

약점

• 컨테이너의 시작 / 끝 위치가 아닌 곳에서 삽입/제거 수행시 그 성능은 list에 비해 현저히 떨어진다.

vector와 비슷해 보이지만, 두번째 강점이 vector와의 첫번째 차이점이다.
vector는 컨테이너 끝에 삽입/제거하는 것만이 빨랐지만, deque는 컨테이너 끝 뿐 아니라 처음부분에서의 삽입/제거도 효율이 높다. double ended 라는 naming...

이러한 특징으로 STL의 스택과 큐 클래스는 deque와 list로 구현이 가능하지만, 기본 클래스는 deque이다.

그리고 vector와의 두번째 차이점이 컨테이너의 동적 확장/축소 방식이다.
이는 어떻게 보면 deque의 불편한 점이 되기도 하고, vector보다 더 나은 점이 되기도 한다.

vector의 경우 컨테이너 내부 capacity가 고갈되면 이를 확장하기 위해 전체 메모리 크기만큼 reallocating이 발생한다.
하지만, deque의 경우 일정 크기를 가지는 chunk 단위로 확장되는 방식을 가지고 있다.
이렇기에 vector에 비해 다음과 같은 장단이 존재한다.

장점

• 저장 원소가 많고 메모리 할당량이 큰 경우 vector에 비해 확장 비용이 절감된다.
  : 전체가 재할당되기 보다, 늘어나야 될 크기만큼만의 chunk가 하나 더 할당되면 그만이므로...

단점

• 컨테이너 처음부터 끝까지 연속 메모리 공간이 아니므로, vector에서 가능했던 원소들간 포인터 연산이 불가능하다.

3. list

list는 doubly linked list로 구현되어 있다.

강점

• 컨테이너의 어느 위치에서도 삽입/제거가 빠르다 (상수 복잡도)
• 원소들의 컨테이너 내 순서 이동이 빠르다. (상수 복잡도)

vector와 deque와 다르게 list의 가장 큰 강점은 컨테이너 내 어느 위치에서도 원소의 삽입/제거가 빠르다는 것이다.

약점

• 원소의 position index로 직접 접근이 불가능하다.
  : 특정 원소에 접근하려면 처음이나 끝에서부터 선형 탐색을 하여야만 한다.
• 컨테이너 내 원소 순회는 forward / reverse 순회만 가능하며, 느리다. (선형 복잡도)
• 원소들간 상호 연결 정보를 위해 추가적인 메모리가 사용된다.
  : 원소 수가 적을수록 그 상대 비율은 올라가겠지 쩝;

얼핏 보면 약점이 되게 많아 보이지만, 컨테이너 내 어느 위치에서도 원소의 삽입/제거가 빠르다는 장점이 list의 활용성을 대변해 주는 키워드이다.