O (1) 복잡도를 가진 단일 연결 목록에서 하나의 요소를 삭제하기위한 알고리즘

Question

저는 독일에서 컴퓨터 과학을 전공하고 있습니다. 교수님은 다음과 같은 질문을 생각해 보았습니다 :

'하나의 링크 된 목록 (마지막 노드가 아닌 노드)에 대한 참조가 주어졌습니다. 무결성을 유지하면서 복잡성이 O (1) 인 목록에서이 요소를 삭제하는 알고리즘을 제공하십시오.

나는 이것에 대해 생각했지만 꽤 그런 알고리즘은 없다고 확신한다. 링크 된 단일 목록이기 때문에 노드의 next-Pointer를 삭제해야하기 때문에 삭제해야하는 노드에 도달 할 때까지 목록의 모든 노드를 반복해야합니다. O (n) 복잡도로 이어질 것입니다.

나는 무엇이 있습니까?

Answer 1

노드가 변경 가능한지 여부에 달려 있습니다.

toDelete.value = toDelete.next.value 
toDelete.next = toDelete.next.next 

이 toDelete의 정보는 이제 이전 toDelete.next의 정보에 의해, 덮어 쓴 모든 : 당신이 노드와 같은 일을 할 수있는 경우가

는, 그 일을하는 방법입니다. (플랫폼에 따라 이전 toDelete.next을 해제해야 할 수도 있습니다. 즉 임시 참조를 유지해야합니다. 다른 사람이 아직 참조를 유지하고 있으면 좋지 않습니다 .Java/C#에서는 무시할 수 있습니다. .)

내가 포기하지 않고 암시하는 방법을 해결하려고 노력하지만, 좀 까다로운

...

그것은이 비록 목록의 마지막 노드 없다는 의지 않습니다.

Answer 2

정확하게 노드를 삭제하는 것으로 간주하지만 다음 노드를 현재에 다음 노드의 데이터를 복사하고 삭제할 수 없음 :

// pseudocode: 
this.data = next.data; 
var temp = this.next; 
this.next = next.next; 
delete temp; 

Answer 3

예. 이전 목록의 다음 포인터에 대한 포인터 인 반복 포인터로 유지합니다. 노드가 메모리의 기본 구조 인 경우

walk = &head; 
while (!match(*walk)) { 
    walk = &walk[0]->next; 
    if (!*walk) return ; 
} 
*walk = walk[0]->next; 

Answer 4

, 삭제 된 노드의 메모리 위치에 "다음"노드의 내용을 복사하고 "다음"노드로 사용되는 메모리 할당을 취소 할 수 있습니다.

Answer 5

삭제하려는 노드에 대한 포인터가 있다고 가정합니다. 다음 값을 현재 노드에 복제합니다. 다음 가리키는 노드에 현재 포인터를 바꿉니다.

Answer 6

링크가 아니라 데이터 이동 다른 스레드를 찾으십시오 : Deleting a middle node from a single linked list when pointer to the previous node is not available