벡터(vector)와 리스트(list), 시퀀스(sequence) ADT의 차이를 알아봅시다.
벡터(Vector, array list)
-
정의
벡터는 array list라고도 불리는 자료구조입니다. 벡터는 인덱스를 통해 자료에 접근하며, 접근 시 잘못된 인덱스가 주어지면 예외를 throw합니다. -
vector adt
// stl interface와 다름
at(int idx)
//인덱스 idx의 위치에 있는 요소를 지우지 않은 채 반환합니다
set(int idx, object o)
//인덱스 idx에 있는 요소를 o로 대체합니다
insert(int idx, object o)
//인덱스 idx에 새로운 객체 o를 삽입합니다
erase(int inx)
//인덱스 idx에 있는 요소를 지웁니다
//여기까지 필수로 구현되어야 하는 기능들
size()
//벡터의 사이즈 반환
empty()
//비어있으면 true, 비어있지 않으면 false 반환
//보조 기능들- 구현 방법 및 복잡도
벡터는 array를 통해 구현할 수 있습니다. 이 경우 at과 set 연산은 O(1)의 시간복잡도를 갖습니다. 한편 insert와 erase 연산은 삽입/삭제 후 칸을 뒤로 옮기거나 당겨오는 과정이 필요하기 때문에 최악의 경우 O(n)의 시간복잡도를 갖게 됩니다.
한편 메모리의 효율적인 사용을 위해 circular array로 구현할 수 있는데, 이 경우 insert(0, x)와 erase(0)의 경우 O(1)의 복잡도를 갖습니다.
또한 요소 삽입 시 array의 capacity를 넘는 연산이 발생하면 현재 array의 크기를 특정 상수 c만큼 증가시키거나, c배만큼 늘림으로써 이를 해결할 수 있습니다. 이 경우를 growable array based vector라고 합니다. 따라서 공간복잡도는 전체 array 크기인 N에 따라 O(N)을 만족합니다.
insert, erase = O(n)
other operations = O(1)
리스트(List, node list)
-
정의
리스트는 벡터와 달리 position 정보를 가지고 요소에 접근하는 자료구조입니다. 이때 position이란 해당 객체의 위치를 가르키는 개념으로, c++에서는 pointer로 이를 구현할 수 있습니다. 리스트에서는 인덱스가 아닌 특정 position과 그 전후관계로 요소에 접근하기 때문에, node list라고도 불립니다. -
List adt
// stl interface와 다름
insertFront(element)
//리스트 맨 앞에 새로운 요소 삽입
insertBack(element)
//리스트 맨 뒤에 새로운 요소 삽입
removeFront()
//맨 앞에 있던 요소 삭제
removeBack()
//맨 뒤에 있던 요소 삭제
size()
//요소들의 개수 반환
empty()
//비어있으면 true, 비어있지 않으면 false
insert(p, e)
//position p 이후에 새로운 요소 e 삽입
remove(p)
//position p에 있던 요소 삭제
begin()
//iterator
end()
//iterator
- 구현 방법 및 복잡도
리스트는 doubly linked list를 이용해 효율적으로 구현할 수 있습니다(일반적인 doubly linked list의 node 중 data를 저장하는 부분이 position을 저장하고, 이 position이 data를 가르키고 있다고 생각하면 됩니다). 이 경우 모든 연산은 O(1)의 시간복잡도를 갖습니다. 특정 position이 주어지면 해당 노드를 O(1)만에 찾을 수 있기 때문입니다. 한편 공간복잡도는 O(n)을 만족하게 됩니다.All operations = O(1)
시퀀스(Sequence)
-
정의
시퀀스는 벡터와 리스트의 확장이라고 할 수 있습니다. 시퀀스에서는 index와 position을 통한 탐색이 모두 가능합니다. -
Sequence adt
// stl interface와 다름
elemAtIdx(i)
//인덱스 i에 있는 요소를 반환
replaceAtIdx(i, o)
//인덱스 i에 있는 값을 o로 바꿈
insertAtIdx(i, o)
//인덱스 i에 새로운 요소 o를 삽입
removeAtIdx(i)
//인덱스 i에 있던 값을 지움
first()
//iterator
last()
//iterator
replaceElem(p, o)
//position p에 있던 값을 o로 바꿈
swapElem(p, q)
//position p와 q에 있던 값을 서로 바꿈
insertBefore(p, o)
//position p 앞에 새로운 요소 o를 삽입
insertAfter(p, o)
insertFirst(o)
insertLast(o)
remove(p)
//position p에 있던 값을 지움
atIdx(i)
//인덱스 i의 position을 반환
idxOf(p)
//position p의 인덱스를 반환- 구현 방법 및 복잡도
시퀀스는 array와 doubly linked list 등을 이용하여 구현할 수 있습니다. 다만 doubly linked list로 구현할 경우 인덱스를 통한 탐색은 O(n)의 시간복잡도를 갖습니다. 각 구현방법에 따른 기능들의 복잡도는 다음과 같습니다.
Data Structures and Algorithms in C++ (2nd, Paperback)을 참고하여 작성된 포스트입니다.
