Änderung der Reihenfolge der Elemente in verknüpften Liste

Question

Ich versuche einfach verkettete Liste zu verwenden:

struct index 
{ 
    struct index* next_element; 
    int data; 
    struct index* previous_element; 
} 

Was ist der beste Weg, um Elemente in Bezug auf die Leistung zu ändern? Zum Beispiel habe ich 1 2 3 4 5 6 7 8 und ich brauche 1 4 2 3 5 6 7 8.

Answer 1

Es ist schwer zu sagen, im Allgemeinen. Es scheint, dass Sie Element 4 nach Element 1 verschieben möchten. Haben Sie die index* für beide? Oder wissen Sie einfach, dass sich das vierte Element um zwei Stellen bewegen muss? Dies beeinflusst offensichtlich die Menge an Listwalking, die Sie tun müssen.

Im Allgemeinen für maximale Effizienz, eine Funktion wünschen würde

void list_remove_unsafe_(index* i) { 
    // These two have to change (minimum needed) 
    i->previous_element->next_element = i->next_element; 
    i->next_element->previous_element-> = i->previous_element; 
    // We leave i itself unchanged (dangling) 
} 

und ein Follow-up

void list_insert_unsafe_(index* after, index* i) { 
    // These four have to change (minimum needed) 
    index* before = after->next_element; 
    i->previous_element = after; 
    i->next_element = before; 
    before->previous_element = i; 
    after->next_element = i; 
} 

Diese Operationen sind unsicher, weil sie vorübergehend die Liste in einem gebrochenen Zustand verlassen und viele Annahmen treffen (zB keine Überprüfung auf Beginn/Ende von Listen). Diese brauchen spezielle Handhabung. Für die Grundoperation sind diese 6 Zeigerschreibvorgänge das absolute Minimum.