[Algorithm] 벡터(Vector)와 리스트(List)의 차이점

벡터(vector)

벡터는 동적배열을 만드는 연산을 수행한다. 따라서 연속적인 메모리를 확보한다.

자신의 요소를 내부의 동적 배열 ( dynamic array )로 복사한다.

임의 접근 연산자를 제공([])하기 때문에 어떠한 값에 접근하든 상수시간이 소요된다

동적배열이기 때문에 배열의 중간에 새로 추가하거나 삭제하면 많은 값이 이동해야하기 때문에 오랜 시간이 걸린다

따라서 중간에 추가 하기보단 뒷부분에 추가한다 ( push_back )

동적배열이기 때문에 크기의 확장과 축소가 자유롭지만 재할당 비용은 크다.

 

장점

임의접근을 상수시간에 가능하다. 따라서 읽기에 매우 강하다.

 

단점 

중간에 값을 추가/제거하는 비용이 크다

재할당 비용이 크다

 

리스트(list)

리스트는 요소들을 양방향 연결리스트의 형태로 관리한다.

리스트 객체는 앵커라 불리는 포인터 2개를 제공하는데 이는 head와 tail을 가리킨다.

새로운 요소를 삽입하기 위해서는 이 포인터를 조작한다

리스트는 임의 접근을 제공하지 않는다. ( n번째 요소에 접근하기 위해서 노드들을 거쳐야한다 )

특정 위치에 추가/삭제가 자유롭다 ( 특정 위치를 찾는 시간은 제외 )

재할당 연산이 없다. 연속적인 메모리가 아니기 때문에 무한히 ( 메모리카드가 제공하는 한 ) 추가할 수 있다

 

장점

임의의 위치에 요소를 추가하는 것이 자유롭다 ( 찾아가는 시간 제외 ) 따라서 쓰기에 매우 강하다

 

단점

임의접근이 불가능하기 때문에 선형 탐색하여 위치를 찾는다

원소간의 연결을 위해 추가적인 메모리를 소모한다 ( 다음 노드의 포인터 메모리 )

 

 

두 컨테이너의 가장 큰 차이는 각 컨테이너의 장점과 단점으로 볼 수 있다.

리스트의 장점은 벡터의 단점이고 리스트의 단점은 벡터의 장점이다