Array vs List

이 게시물을 통하여 배열 (array)와 동적리스트 (linked list)의 차이점과 어느 상황에서 우세한지 비교하고자 한다.

무작위 접근 연산이 일어나면 배열을 쓴다.

링크드리스트는 무작위 접근연산이 일어나서 인덱스가 나오면 거기까지 움직여야 한다. O(N).
배열은 그냥 접근하면 된다. O(1)

커서에서 연산이 일어나면 링크드리스트를 쓴다.

연산이라 함은 insertion, deletion을 말한다.

insertion의 경우 링크드리스트는 커서 다음에 새로운 노드를 삽입하고 포인터만 잘 설정해 주면 된다. 이때 O(1)이다.
배열의 경우 커서 다음에 현재 값을 삽입한다고 할 때 커서 다음의 비어있지 않은 공간을 다 뒤로 밀어줘야 된다. 이때 O(N)이다.

deletion의 경우 링크드리스트는 포인터 조작을 통해 커서의 노드가 더 이상 리스트에 포함되지 않도록 하고 후에 free해주면 된다. 이때 O(1)이다.

배열의 경우 배열에서 값을 삭제하는 경우, 현재 배열을 사용하지 않는 플래그를 사용하는 경우가 있을 수 있다.
배열에서 값을 삭제하는 경우 현재 커서 뒤의 값을 앞으로 끌고와야 하기에 O(N).
플래그를 사용하는 경우 당장 delete는 O(1)이지만, delete된 원소가 연속적으로 쌓인다고 생각하면 공간의 낭비가 생긴다. 또한 만약 현재 사용중인 원소의 다음 사용 중인 원소로 이동한다고 할 때, 중간의 쌓인 사용되지 않는 원소들을 건너가야하는 의미없는 연산이 M번 일어날 수가 있다. 즉 커서 움직임에 O(N)이 후에 발생할 수 있는 것이다.

두 방향 커서에서 연산이 일어나면 더블 링크드 리스트를 쓴다.

용량이 동적으로 바뀐다면 링크드 리스트가 더 효율적이다.