[자료구조] 동적 배열과 연결리스트의 차이

	삽입 및 삭제	조회
동적 배열	O(n)	O(1)
연결 리스트	O(1) or O(n)	O(n)

 

동적 배열에서의 데이터의 삽입과 삭제

데이터를 배열의 마지막에 추가하거나 삭제하는 경우, O(1).

하지만 배열이 가득 차 있을 때 (= 할당받은 메모리 공간을 다 채웠을 때), 충분한 공간을 다시 확보하고 기존 배열 요소를 모두 복사한 후 새로운 데이터를 추가한다. 데이터의 개수만큼 복사해야 하므로 이 때는 O(n)이다.

동적 배열에서 배열이 가득 찼을 때는 배열 크기의 2배만큼 메모리를 다시 잡는다. 

반면, 배열의 중간에 원소를 삽입하거나 삭제하는 경우, 이미 있는 원소들은 모두 한 칸씩 밀리거나 당겨진다. 이에 최악의 경우 O(n)이 소요된다.

결론 : 배열의 마지막에 원소를 추가하거나 삭제하는 경우 O(1)이지만, 할당 받은 메모리는 다 채운 상태에서 마지막에 추가나 삭제를 하는경우, O(n)이 필요하다. 배열의 중간에 삽입하거나 삭제하는 경우는 최악의 경우 O(n)의 시간복잡도를 가진다.

 

연결 리스트에서의 데이터의 삽입과 삭제

 

연결리스트에서의 삽입과 삭제는 해당 요소의 위치를 이미 알고 있을 경우 O(1)의 시간 복잡도를 가진다. 그런데 해당 요소의 위치를 모르고, 탐색한 다음 삽입이나 삭제를 해야 하는 경우라면 O(n)이 필요할 것이다.

연결리스트는 인덱싱과 같은 연산을 구현할 수 없기 때문에 어떤 요소를 찾으려면 리스트의 처음부터 끝까지 하나씩 방문하면서 해당 요소를 찾아야 한다. 따라서 O(n)의 시간복잡도를 가진다. 

 

번외)

연결 리스트는 어디에 쓰이는가?

연결 리스트는 동적 배열에 비해 쓰임이 적은 편이다. 삽입과 삭제가 빈번한 경우에 사용하기 좋다. 연결리스트를 사용한 예로는 OS에서 힙 메모리를 할당 및 해제할 때 이중 연결 리스트로 구현한 경우가 있다.