단일 링크 된 목록 및 시간 복잡성

Question

나는 (가능한 한 표준에 가까운) 단일 링크 목록 구현을 직접 작성하려고합니다. 그러나 나는 사람들이 그런 목록에 대해 어느 정도의 시간이 필요한지 궁금해하고있다.

특히 삽입하기 위해 어떻게 구현해야하는지 궁금합니다. 나는 몇몇 사람들이 O (1)이라고 말하고 다른 사람들은 O (n)라고 말하면서 인터넷에서 몇몇 위치를 읽었습니다 - 이중 링크 된리스트는 O (1)이라는 것에 모두 동의합니다. 그러나 나는 O (1)도 단일 연결 목록의 경우라고 생각하십니까?

앞의 노드를 아는 한 이전 노드가 새로운 새 노드를 가리 키도록하고 새 노드는 이전 노드가 원래 가리킨 노드를 가리 키도록합니다.

그렇다면 사람들이 insert이 어떻게 행동 할 것으로 예상하는지 궁금하게 생각하십니까? 통상은, 지정된 반복자의 전에 요소를 삽입합니다. 그러나 단 하나 연결 한 명부로 그것을하기 단단하다 (사람은 O(n) 선행하는 성분을 얻는 시간을 통과해야하고 &는 그 후에 위 방법을 사용한다). 그러한 목록에서 현재 반복자 뒤에 insert 항목을 배치하는 것이 일반적입니까? 아니면 더 나은 - 거기에 또 다른 공통 기능이 있습니까?

Answer 1

삽입의 복잡성은해야 할 일에 달려 있습니다. 이전 노드 (실제로는 이전 노드의 "다음 포인터"를 변경하기에 적합한 핸들) 만 알면 복잡도는 O(1)입니다. 삽입 할 위치를 찾으려면 복잡성은 O(n)입니다.

기대와 관련하여 나는 insert()이 이중 연결 목록과 동일하게 작동 할 것으로 기대하지만 이것을 달성 할 수 없다는 사실도 깨닫습니다. 다른 시간 복잡성이 필요합니다 (전임자를 찾으려면 노드) 또는 다른 반복자 무효화 의미 (즉, 다른 노드의 반복자가 무효화됩니다). 저는 C++ 2011 std::forward_list 클래스 템플릿이 다른 인터페이스를 사용했지만 반복기 유효성을 보장한다고 생각합니다.

반복기 유효성이 영향을받을 수있는 이유를 간략하게 설명합니다. 반복기는 현재 노드에 대해서만 알 필요가 없습니다. 대신 예를 들어 이전 버전의 next 포인터를 가리킬 수 있습니다. 이터레이터의 참조를 해제하면 먼저 next 포인터에 대한 포인터를 역 참조 한 다음이 포인터를 참조하여 실제 노드를 유지합니다. 그 대신 반복기가 업데이트 할 포인터 next을 알고 있기 때문에 이터레이터 앞에 삽입 할 수 있습니다. 불행히도 이것은 반복자가 가리키는 포인터가 변경되어 다른 노드를 참조하기 때문에 반복자가 무효화 될 수 있음을 의미합니다 (노드를 지울 때 반복자가 참조 된 노드가 여전히 있음에도 불구하고 완전히 무효화되었을 수 있음).