기록을

C++ STL list의 삽입과 삭제에 대해서 간단히 정리하고자 한다.

STL list .insert(iterator, 넣을 값)

L = { A, B, C }

연결리스트는 A->B->C 와 같이 구성되어 있는 것이지만 표기의 편의성을 위해 위와 같이 표기하였다.

위와 같은 연결리스트가 있고, 현재 iterator의 위치가 B라면, L.insert(iterator, 'K') 라는 코드를 실행하게 되면 결과는 다음과 같다.

{A, K, B, C}

iterator의 왼편에 새로운 값이 삽입이 되고, iterator는 원래 가르키던 값을 가르킨다고 생각하면 된다. 

( 이해의 편의를 위해서 이렇게 적었다)

그리고, insert 함수의 경우 아무 것도 반환하지 않는다.

다음으로는 삭제에 대해서 알아보자.

Iterator = list.erase(Iterator)

erase 함수는 삭제를 수행한 이후에 iterator를 반환한다. 따라서 반드시 반환되는 iterator을 받아서 갱신(저장)하는 방식으로 구현해줘야 한다.

L = { A, B, C }

위와 동일한 상황이고, 현재 iterator가 B를 가르키고 있는 상태에서, 

itr = list.erase(itr)

다음과 같은 구문을 실행하게 되면, L = {A, C } 이와 같은 상황이 되고, iterator는 없어진 B의 우측에 있던 값인 C를 가르킨다고 생각할 수 있다.

Array

• 논리적 저장 순서와 물리적 저장 순서가 일치한다.

• 따라서 인덱스로 해당 원소에 접근할 수 있으므로, 찾고자 하는 원소의 인덱스를 알고 있으면 O(1)의 시간 복잡도로 해당 원소에 접근할 수 있다. (Random access 가능)

• 삽입/삭제의 경우, O(1)에 접근은 할 수 있지만, 삽입/삭제 이후에 대부분의 상황에서 원소들을 shift 해주어야 하기 때문에, 이 shift 비용이 최악의 경우 O(n)이 된다.

LinkedList

• 논리적 저장 순서와 물리적 저장 순서가 관계가 없다.

• Random access가 불가능하다. 즉 특정 원소에 접근하고자 할 때, 처음부터 하나씩 찾아가야 한다. 따라서 검색 시 최악의 시간 복잡도는 O(n)이다.

• 삽입 혹은 삭제를 하는 경우에는, 일단 검색을 통해서 원하는 위치에 접근을 한 이후에는, 연결만 해주거나 끊어주면 되기 때문에 검색을 제외한 삽입/삭제의 시간 복잡도는 O(1)이다.

• 결국 처음부터 삽입/ 삭제를 해야하는 경우 시간 복잡도는 O(n)이다.

• Tree의 근간이 되는 자료구조이다.

배열의 경우에 데이터 삽입을 하려고 하는데 처음에 잡은 배열 크기의 범위를 벗어난다면, 새로이 할당을 하여 크기를 키워줘야 한다. 연결리스트는 이러한 과정이 필요 없다.

결론적으로 데이터의 삽입과 삭제가 빈번하게 일어난다면 연결리스트를 사용하면 된다.

그렇지 않고 미리 정해둔 데이터에서 검색만 빈번히 일어난다면 배열을 사용하는 것이 좋다.

하지만 대부분의 알고리즘 문제를 풀이할 경우에는, 메모리와 변수의 입력크기 범위가 주어지기 때문에, 그 한계치로 배열 크기를 잡아두고 사용하면 빠르게 사용할 수 있다.

또한 연결리스트의 경우, 원소 추가 과정마다 메모리의 할당이 발생하고, 삭제 시에는 메모리 해제가 발생하는데, 이러한 system call이 사용되는 부분에서 시간이 걸린다.