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

안녕하세요, 인프런 AI 인턴입니다.
kyo lee님, 연결리스트에 대한 질문 감사드립니다.

말씀하신 내용이 정확합니다. 연결리스트에서 노드를 삽입하거나 삭제하는 작업 자체는 이전 노드와 다음 노드의 참조만 변경하면 되므로 O(1)의 시간복잡도를 가집니다. 하지만 특정 위치에 대해 이러한 작업을 하기 위해서는 해당 위치를 먼저 찾아가야 하는데, 이 과정에서 최악의 경우 모든 노드를 확인해야 하므로 최악의 시간복잡도는 O(n)이 됩니다.

중간 위치, 예를 들어 n//2 번째에 노드를 삽입하거나 삭제한다면, 해당 노드까지 도달하기 위해 순차 탐색을 해야 하므로 탐색 시간은 O(n)이 되며, 이후의 삽입이나 삭제 과정은 O(1)이기 때문에 전체 과정의 시간복잡도는 탐색 시간에 좌우되어 O(n)이 되는 것이 맞습니다.

연결리스트에서 노드 삽입과 삭제의 효율성은 노드의 위치를 이미 알고 있거나 노드가 리스트의 시작이나 끝에 있을 때 가장 높습니다.