Bei einem Problem half der Listenkopf jedoch nicht weiter: Zum Entfernen und Hinzufügen von Elementen benötigen wir weiterhin grundsätzlich den Vorgänger, den wir nur mit sehr viel Aufwand wieder herausfinden können. Eine triviale Lösung ohne mehr Speicherverbrauch gibt es nicht, also bemühen wir eine triviale Lösung, die etwas mehr Speicher verbraucht.

struct AddressNode
{
  struct AddressNode * Next;
  struct AddressNode * Prev;
 
  struct Address       Data;
};

Listen dieser Art nennt man 'doppelt verkettete Liste'. Auch den Listenkopf kann man entsprechend anpassen:

struct AddressList
{
  struct AddressNode * First;
  struct AddressNode * Last;
 
  char               * FileName;
};

Statt nun aufwendig, den Vorgänger zu bestimmen, nehmen wir das entsprechende Vorgängerelement. Ein weiterer Vorteil ist, dass man nun die Liste auch rückwärts ohne Mehraufwand durchlaufen kann.

NewNode und DeleteNode müssen nun natürlich zusätzlich zu Next auch Prev beachten und zusätzlich zu First im Listenkopf Last beachten.

struct AddressNode * NewNode( struct AddressList * list, struct AddressNode * prevNode )
{
  struct AddressNode * newNode = (struct AddressNode *) malloc( sizeof( struct AddressNode ) );
 
  if( prevNode ) 
  {
    newNode ->Next = prevNode->Next;
    prevNode->Next = newNode;
    newNode->Prev  = prevNode;
  }
  else  
  {
    newNode->Next = list->First;
    list->First = newNode;
  }
 
  if( list->Last == prevNode )
    list->Last == newNode;
 
  return newNode;
}

Ebenso ändern wir DeleteNode:

void DeleteNode( struct AddressList * list, struct AddressNode * toBeRemoved )
{
  /* Vorgänger finden */
 
  if( toBeRemoved == list->First )
  {
    /* Wir entfernen den Listenkopf, daher beginnt die Liste ab sofort am Nachfolgerelement */
 
    list->First = list->First->Next;          // Listenkopf verschieben
  }
  else
  {
    /* Es ist nicht das Kopfelement */
 
    toBeRemoved->Prev->Next = toBeRemoved->Next;
  }
 
  if( toBeRemoved == list->Last )
  {
    list->Last = toBeRemoved->Prev;
  }
  else
  {
    toBeRemoved->Next->Prev = toBeRemoved->Prev;
  }
 
  free( toBeRemoved );
}

Bisher werden Nodes grundsätzlich einer Liste zugeordnet, ein Wechsel von einer Liste in eine andere ist nicht vorgesehen.

Das muss nicht grundsätzlich das gewünschte Verhalten sein. Es kann durchaus mehrere Listen geben, die gleichartige Elemente verwalten, die aber unterschiedliche Zustände enthalten. So könnte es eine Liste für Kundenadressen geben, wie auch eine Liste für Empfänger von Werbung, die allerdings noch nichts bestellt haben. Bestellt nun ein Werbungsempfänger zum ersten Mal, so wird er zum Kunden, seine Adresse muss nun in der anderen Liste geführt werden. Daher erstellen wir Funktionen, die das Hinzufügen und Entfernen aus Listen übernehmen.

void InsertNode( struct AddressList * list, struct AddressNode * prevNode, struct AddressNode * newNode )
{
  if( prevNode ) 
  {
    newNode ->Next = prevNode->Next;
    prevNode->Next = newNode;
    newNode->Prev  = prevNode;
  }
  else  
  {
    newNode->Next = list->First;
    list->First = newNode;
  }
 
  if( list->Last == prevNode )
    list->Last = newNode;
}

Ebenso erzeugen wir eine Funktion, die ein Element aus einer Liste herausnimmt.

void RemoveNode( struct AddressList * list, struct AddressNode * toBeRemoved )
{
  if( toBeRemoved == list->First )
  {
    /* Wir entfernen den Listenkopf, daher beginnt die Liste ab sofort am Nachfolgerelement */
 
    list->First = list->First->Next;          // Listenkopf verschieben
  }
  else
  {
    /* Es ist nicht das Kopfelement */
 
    toBeRemoved->Prev->Next = toBeRemoved->Next;
  }
 
  if( toBeRemoved == list->Last )
  {
    list->Last = toBeRemoved->Prev;
  }
  else
  {
    toBeRemoved->Next->Prev = toBeRemoved->Prev;
  }
}

Der Unterschied zu NewNode() und DeleteNode() ist lediglich, dass die Node nicht erzeugt bzw. zerstört wird. Um Redundanz zu vermeiden, benutzen wir den Code hier ebenfalls in NewNode() und DeleteNode:

struct AddressNode * NewNode( struct AddressList * list, struct AddressNode * prevNode )
{
  struct AddressNode * newNode = (struct AddressNode *) malloc( sizeof( struct AddressNode ) );
 
  InsertNode( list, prevNode, newNode );
 
  return newNode;
}
 
void DeleteNode( struct AddressList * list, struct AddressNode * toBeRemoved )
{
  RemoveNode( list, toBeRemoved );
 
  free( toBeRemoved );
}

Das war's auch schon, nun können wir Elemente nach belieben in Listen herumreichen.

Doch leider haben wir uns damit gleich ein neues Problem eingefangen. Ein Element kann nur in einer Liste enthalten sein, aber was passiert eigentlich, wenn ich ein Element aus einer Liste entferne, in der es nicht verwaltet wird? Oder ein Element mehreren Listen hinzufüge? Die Chance ist gegeben, die Liste in der das Element zuerst eingefügt wurde zu zerhacken. Das führt dazu, dass das Programm wahrscheinlich abstürzt, sobald die zerhackte Liste das nächste Mal verwendet wird.

Der Absturz tritt also nicht in dem Moment auf, in dem der Programmfehler abgearbeitet wird, sondern an einer Stelle, die eigentlich richtig programmiert wurde, die aber mit zerhackten Daten nicht arbeiten kann.

Hier ist also Vorsicht geboten, oder… man nutzt eine Rückreferenz auf den Listenkopf.