[가벼운 고민] linked list에서 순서에 관계없이 노드를 추가할라면 어디에 추가하는게 가장 효율적인가?

일반적으로 linked list의 중간에 삽입하는건 번거롭다는 것은 우리가 쉽게 알고 있다.

 

그렇다면 "연결리스트에서 순서 관계 없이 노드를 추가하는 효율적인 위치는 양 끝이다." 라는 명제는 참일까?

 

그렇지 않다.

 

연결 리스트의 크기가 n개라고 했을 때, 리스트의 tail노드 위에 붙이기 위해서는 tail 노드를 가리키는 포인터가 있지 않은 이상 n번의 탐색을 통해 tail 노드를 찾아야 할 것이다. 이 과정에서 불필요한 오버헤드가 발생한다. FIFO 구조라면 불가피하게 이렇게 해야 하겠지만 '순서 관계 없이'라는 조건이라면 head 노드의 앞에 붙이는 것이 가장 효율적이다.

 

이처럼 항상 자료구조를 이해하여 그 연산의 비용을 고려하며 생각해야 한다.