In einer doppelt verknüpften Liste Wie viele Zeiger sind bei einer Einfügeoperation betroffen?

Question

Ich hatte gestern ein Interview. Als es begann, war das erste, was der Interviewer

gefragt: „In einer doppelt verknüpften Liste, wie viele Zeiger auf einem Einsetzvorgang betroffen sein?“

---

Da hat er nicht ausdrücklich gefragt wo ich einfügen wollte, antwortete ich, dass es darauf ankommt, wie viele Knoten es in der DLL gibt.

Die Gesamtzahl der betroffenen Zeiger hängt davon ab, ob die Liste leer ist oder nicht und wo eingefügt wird.

Aber er sagte nichts, ob ich ihn überzeugt hatte oder nicht.

War ich richtig oder habe ich etwas übersehen?

Answer 1

Ich denke, die Antwort hängt davon ab, ob wir den neuen Knoten in der Mitte der Liste (umgeben von zwei Knoten) oder am Anfang oder Ende der Liste einfügen.

Einfügungen in der Mitte der Liste, in einem neuen Knoten spleißen wie folgt:

A --- B 
    ^^ splice M in here 

A.next = M 
M.prev = A 
B.prev = M 
M.next = B 

Daher vier Zeigerzuweisungen erfolgen. Wenn jedoch die Einfügung am Anfang oder Ende erfolgt, wären nur zwei Zeigerzuordnungen erforderlich:

TAIL (insert M afterward) 

TAIL.next = M 
M.prev = TAIL