Listenköpfe

Den Aufwand, bei jedem Entfernen auch zu prüfen, ob man den Listenkopf überarbeiten muss, möchte man sich selbstverständlich sparen, zumal die Überprüfung in dieser Form sich im Code häufig wiederholen würde. Code, der sich wiederholt, gehört in eine entsprechende Funktion. Eine Möglichkeit ist DeleteNode zusätzlich die Addresse vom Zeiger auf den Listenkopf zu übergeben:

DeleteNode( &head, prev, node );

Oftmals bestehen Listen allerdings nicht nur aus Elemente, sondern haben zusätzliche Informationen, die für die Liste als Ganzes gelten. Als Beispiel: Ein Text hat einen Dateinamen, der für alle Zeilen gilt. Alle Zeilen, die in diesem Text aufgelistet sind, werden in einer Datei gespeichert, daher hat es keinen Sinn, den Dateinamen in jeder Zeile zu speichern. Man erstellt einen Listenkopf, der neben der Information, wo die Liste beginnt auch zusätzlich alle Informationen speichern kann, die für diese spezielle Liste erforderlich sind. Da der Listenkopf im Programm die vollständige Liste repräsentiert, wird er in der Regel auch als Liste bezeichnet:

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

Mit einer solchen Struktur überlassen wir es den Hilfsfunktionen, die Liste selbst zu organisieren. Alle Funktionalität, die für die Listen erforderlich ist, kann so ausschließlich in den wenigen Funktionen untergebracht werden und findet sich nicht mehr verstreut über den Quelltext. In NewNode können wir die Liste mitübergeben, so dass die neue Node automatisch als erstes Listenelement gilt, sofern wir keinen Vorgänger übergeben.

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;
  }
  else  
  {
    newNode->Next = list->First;
    list->First = newNode;
  }
 
//  list->Count++;
 
  return newNode;
}

Ebenfalls können wir DeleteNode() entsprechend erweitern, so dass es die Liste in einem gültigen Zustand hinterlässt, auch wenn das erste Element entfernt wird.

void DeleteNode( struct AddressList * list, struct AddressNode * toBeRemoved )
{
  /* Vorgänger finden */
 
  struct AddressNode * prev;
 
//  list->Count--;
 
  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 */
 
    int index = GetIndex( list, toBeRemoved );
    prev = GetNode( list, index - 1 );
    prev->Next = toBeRemoved->Next;
  }
 
  free( toBeRemoved );  
}

Entsprechend können GetNode() und GetIndex() nun angepasst werden, so dass sie statt des ersten Elementes eine AddressList verlangen. Da Listen nun einen eigenen Datentyp besitzen, sind sie auch nicht mehr so einfach mit dem Element zu verwechseln, welches nunmal zufälligerweise den Start der Liste repräsentiert.

NewNode und DeleteNode haben beide Zugriff auf die Liste, so dass beide Funktionen nun in struct AddressList einen Zähler verwalten könnten, so dass man die Liste direkt fragen könnte, aus wievielen Elementen sie besteht und dafür die Listenelemente nicht mehr zählen müsste.

Schlussendlich hat eine eigene Struktur für den Listenkopf ausschließlich Vorteile, die den geringen Mehraufwand durchaus rechtfertigen. Eine Sache ist allerdings noch zu beachten: Ein Listenkopf muss vor der ersten Verwendung initialisiert werden, es muss also der Zeiger auf das erste Element auf NULL gesetzt werden und, wenn man einen Zähler in der Liste einbaut, so muss dieser natürlich ebenfalls auf 0 gesetzt werden, da die Liste zu Beginn natürlich 0 Elemente beinhaltet.

Aus diesem Grund schreiben wir uns auch hierfür eine kleine Funktion, die einen Listenkopf konstruiert.

struct AddressList * NewAddressList()
{
  struct AddressList * newList = (struct AddressList *) malloc( sizeof( struct AddressList ) );
 
  newList->First = NULL;
// newList->Counter = 0;  // Für den Fall, dass ein Counter implementiert wird
 
  return newList;
}

Als kleine Zugabe kann man nun eine Funktion schreiben, die eine Liste vollständig zerstört:

void DeleteAddressList( struct AddressList * toBeRemoved )
{
  /* Alle Elemente entfernen */
 
  while( toBeRemoved->First )
    DeleteNode( toBeRemoved, toBeRemoved->First );
 
  free( toBeRemoved );
}

Damit sieht die main()-Funktion von zuvor schon einiges kürzer aus:

int main( void )
{
  struct AddressList * list;
  struct AddressNode * node;
 
  list = NewAddressList();
 
  node = NewNode( list, NULL );  // Erste Node anlegen.
  node = NewNode( list, node );  // zweite Node anlegen
  node = NewNode( list, node );  // dritte Node anlegen
  NewNode( list, node );         // vierte Node anlegen, Variable 'node' zeigt weiterhin auf 3. Node
 
  /* Node entfernen, auf die 'node' zeigt */
 
  DeleteNode( list, node );
 
  /* Zuvor haben wir uns um die Freigabe des Speichers gar nicht gekümmert! */
 
  DeleteAddressList( list );
 
  return EXIT_SUCCESS;
}

Die Funktionen GetNode() und GetIndex() müssen ebenso angepasst werden. Die Änderungen der beiden Funktionen können im Download nachgelesen werden.

Download

Quelltexte zum Experimentieren als Make-Projekt: list_head.zip