인프런 커뮤니티 질문&답변

사실 코드를 어떻게 작성하냐에 따라서 시간복잡도가 달라질 수 있습니다. 하지만 대부분 linked list 의 장점으로 추/삭 시에 O(1)의 시간복잡도가 걸린다! 라고 면접관과 피면접자간의 합의(?)같은 점들이 있습니다. 하지만 실제 우리가 구현해보면 시간복잡도 O(1)으로 추/삭을 하기에는 현실과 괴리감이 조금 있습니다. 해당 인덱스까지 current node 포인터를 이동시켜야 하기 때문에 실질적인 시간복잡도는 O(n)이라고 볼 수 있는거죠.

물론. current node가 가리키고 있는 동일한 지점에서 지속적인 추/삭이 발생한다면 O(1)이 될 수 있을겁니다. 즉 상황에 따라서, 그리고 코드를 어떻게 구현했냐에 따라서 조금 이론과 다른 지점들이 있습니다.

즉. linked list는 추/삭시에 O(1)의 시간복잡도가 걸리지만, current node 포인터가 해당 index까지 도달해야만 추가/삭제를 할 수 있기 때문에 전체적인 추/삭의 시간복잡도를O(n)으로 볼 수도 있다. 라고 이해하시면 될 것 같아요!

질문에 답이 됐을까요?!