연결리스트의 삽입과 삭제에서 시간복잡도.

Question

연결리스트에서 값을 삽입하거나 삭제할 때 시간복잡도가 O(1)이라고 하는데 특정 주소의 값을 삭제하거나 특정 값 앞뒤로 새로운 값을 삽입할 때 그 특정 주소를 찾기위해서는 결국 순차탐색을 해서 최악의 경우 O(n)이 되지않나요? 예를들어 길이가 n인 연결리스트에서 n//2째에 값을 삭제하거나 삽입하고 싶다고 한다면 n//2 번째의 주소를 가르키고 있는 노드를 찾아야 하니 시간복잡도가 O(n)이 아닌가 라는 의문이 들어서 질문 남깁니다.

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. kyo lee님, 연결리스트에 대한 질문 감사드립니다. 말씀하신 내용이 정확합니다. 연결리스트에서 노드를 삽입하거나 삭제하는 작업 자체는 이전 노드와 다음 노드의 참조만 변경하면 되므로 O(1) 의 시간복잡도를 가집니다. 하지만 특정 위치에 대해 이러한 작업을 하기 위해서는 해당 위치를 먼저 찾아가야 하는데, 이 과정에서 최악의 경우 모든 노드를 확인해야 하므로 최악의 시간복잡도는 O(n) 이 됩니다. 중간 위치, 예를 들어 n//2 번째에 노드를 삽입하거나 삭제한다면, 해당 노드까지 도달하기 위해 순차 탐색을 해야 하므로 탐색 시간은 O(n)이 되며, 이후의 삽입이나 삭제 과정은 O(1)이기 때문에 전체 과정의 시간복잡도는 탐색 시간에 좌우되어 O(n)이 되는 것이 맞습니다. 연결리스트에서 노드 삽입과 삭제의 효율성은 노드의 위치를 이미 알고 있거나 노드가 리스트의 시작이나 끝에 있을 때 가장 높습니다.