golang에서 slice VS linkedlist

이번 포스팅에서는 golang에서 기본적으로 제공하는 기능인 slice와 자료구조의 기본인 linkedlist를 비교해보겠다.

아 참고로 linkedlist는 자기 앞 노드를 기억할 수 있는 double linkedlist를 기준으로 한다.

 

첫번째로 slice와 linkedlist에서의 맨 앞과 맨 끝 삭제를 비교해보자.

예전 포스팅에서 golang에서 slicing을 하면 새로운 복사본을 얻는게 아니라 단지 slicing한 범위를 포인팅하는 것이라고 했다. (이것 때문에 slicing한 slice의 값을 바꾸면 원본 slice도 값이 바뀌게 된다.)

즉, slice에서의 첫번째 항목 삭제는 아래그림과 같다.

원본 slice는 검은 화살표처럼 맨 처음과 맨 끝을 가리키지만 slicing을 이용하면 그 초록색 화살표처럼 두번째 항목으로 포인팅만 옮겨가기 때문에 시간 복잡도는 O(1)이다.

맨 끝을 삭제하는 경우도 이와 비슷하게 진행되므로 O(1)의 시간복잡도를 가진다.

 

linkedlist의 경우는 어떠할까?

위에서 말했듯 double linkedlist를 기준으로 한다고했으므로 head만 가지고 있는게 아니고 tail도 가지고 있다.

즉 head와 tail을 알고 있으므로 탐색에 시간이 필요없기 때문에 O(1)의 시간복잡도를 가진다.

 

두번째로 slice와 linkedlist의 중간에 있는 항목 삭제에 대해 알아보자

slice의 length가 10개이고 두번째항목을 삭제한다고 치자. 그럼 세번째 항목부터 끝까지 다 한칸식 땡겨?와야한다. 즉 O(N)이다.

그러나 linkedlist의 경우에는 삭제하려는 노드의 prev와 next를 이어주기만 하면 되기 때문에 O(1)이다.

 

여기까지만 보면 linkedlist의 성능이 더 좋기 때문에 slice를 쓸 이유가 없어보인다. 그러나 slice의 장점이 아직 남아있다. 

 

세번째로 slice와 linkedlist의 탐색을 알아보자.

linkedlist의 경우 head나 tail아닌 이상 쭉 돌면서 찾아봐야 하기 때문에 O(N)이다. slice도 내가 찾으려는게 어딨는지 모르면 O(N)이다.

그러나 만약 내가 찾는게 어디있는지 아는경우면 달라진다. 

이 slice에서 내가 john의 인덱스가 3인걸 이미 알고 있다고 가정해보자.

linkedlist는 내가 어딨는지 알고있더라도 O(N)의 시간이 걸린다. 그러나 slice는 내가 어딨는지 알고있으면 a[3] 이렇게 하면 O(1)의 시간이 걸린다.

 

그 밖에도 slice는 메모리가 서로 다 붙어있기 때문에 캐시성공률이 linkedlist에 비해 높다.