Die einfachste Form einer Liste ist ein Node, das ein Datenelement enthält und einem Zeiger auf das nachfolgende Element. Besteht ein Datensatz zum Beispiel aus einer Adresse, so kann ein Datensatz zum Beispiel so aussehen:

struct Address
{
  char Street[64];
  int  Number;
  int  ZipCode;
  char Town[64];
};
 
struct AddressNode
{
  struct AddressNode * Next;
 
  struct Address       Data;
};

Ein Node kann nun einfach angelegt werden und beschrieben werden, wie eine normale Struktur:

struct AddressNode * myNode;
 
myNode = (struct AddressNode *) malloc( sizeof( struct AddressNode ) );
myNode->Next = NULL;

Diese einzelne Node stellt nun gewissermaßen bereits eine kleine Liste mit nur einem Element dar. Da Next auf NULL zeigt, endet die Liste auch mit diesem Element. Auf den Datensatz kann man nun mit myNode→Data nach belieben zugreifen. Grundsätzlich sollte man nach malloc() prüfen, ob man überhaupt Speicher erhalten hat. Zugunsten der Übersicht wird hier und in den folgenden Beispielen darauf verzichtet.

Um ein Element hinter ein anderes Element einzufügen, muss man lediglich ein neues Element erzeugen und dem Vorgänger-Element mitteilen, wo die Liste weiter geht. Dafür schreiben wir uns eine Funktion.

struct AddressNode * NewNode( struct AddressNode * prevNode )
{
  struct AddressNode * newNode = (struct AddressNode *) malloc( sizeof( struct AddressNode ) );
  newNode->Next = NULL;
 
  if( prevNode )
    prevNode->Next = newNode;
 
  return newNode;
}

Wird als Argument NULL übergeben, erhalten wir eine einzelne Node, die keinen Nachfolger hat. NewNode() eignet sich also auch, um eine Liste zu beginnen.

Möchte man ein Element innerhalb einer Liste einfügen, so muss nicht nur der Vorgänger verändert werden, sondern auch die neue Node erhält einen Nachfolger. Hierfür muss NewNode noch etwas verändert werden.

struct AddressNode * NewNode( struct AddressNode * prevNode )
{
  struct AddressNode * newNode = (struct AddressNode *) malloc( sizeof( struct AddressNode ) );
 
  if( prevNode ) 
  {
    newNode ->Next = prevNode->Next;
    prevNode->Next = newNode;
  }
  else 
    newNode->Next = NULL;
 
  return newNode;
}

Ein großer Vorteil von Listen besteht darin, dass man Elemente jederzeit entfernen kann und kein Loch im Datensatz erhält. Dafür muss man die Kette allerdings wieder zusammensetzen: Der Vorgänger der zu entfernenden Node muss auf den Nachfolger der zu entfernenden Node zeigen.

void DeleteNode( struct AddressNode * prevNode, struct AddressNode * toBeRemoved )
{
  if( prevNode )
    prevNode->Next = toBeRemoved->Next;
 
  free( toBeRemoved );
}

Hierfür muss das vorherige Element bekannt sein. Dies kann man zum Beispiel herausfinden, wenn man sich den Kopf der Liste merkt und zunächst einmal den eigenen Index in der Liste herausfindet. Dafür muss die Liste durchlaufen werden, bis das gesuchte Element gefunden ist.

int GetIndex( struct AddressNode * head, struct AddressNode * element )
{
  int index = 0;
 
 
  while( head != element && element != NULL )
  {
    index ++;
 
    element = elemnt->Next;
  }
 
  /* index zurückgeben, wenn gefunden */
 
  if( head == element ) 
    return index;
 
  /* Falls nicht gefunden, Fehler zurückgeben */
 
  return -1;
}

Da der Zeiger element beim Aufruf der Funktion kopiert wird, die Variable element also für diese Funktion extra angelegt wird, können wir diese Variable auch ändern, da wir den ursprünglichen Wert im Verlauf der Funktion nicht mehr benötigen. Wenn wir den Wert noch benötigen würden, müssten wir zunächst eine Kopie des Zeigers in einer anderen Variable machen.

Nun können wir herausfinden, an welcher Position sich das zu entfernende Element befindet. Wir durchlaufen die Liste erneut und halten einfach ein Element vorher an. Die Funktion, um an einen Index zu gelangen kann so formuliert werden:

struct AddressNode * GetNode( struct AddressNode * head, int index )
{
  while( index > 0 && head != NULL )
  {
    head = head->Next;
    index--;
  }
 
  return head;
}

Nun können wir die eigene Position herausfinden und damit anschließend das vorhergehende Element bestimmen. Sollte es kein vorhergehendes Element geben, so wird der Kopf der Liste entfernt und das Kopfelement muss neu gesetzt werden.

Wenn ein Element entfernt wird, müssen wir im Hauptprogramm mit dieser Liste also immer darauf achten, dass der Kopf der Liste nicht verloren geht:

int main( void )
{
  struct AddressNode * head;
  struct AddressNode * node;
 
  node = NewNode( NULL );  // Erste Node anlegen.
  head = node;             // als Kopf der Liste merken
  node = NewNode( node );  // zweite Node anlegen
  node = NewNode( node );  // dritte Node anlegen
  NewNode( node );         // vierte Node anlegen, Variable 'node' zeigt weiterhin auf 3. Node
 
  /* Node entfernen, auf die 'node' zeigt */
 
  if( node == head )
  {
    /* Wir entfernen den Listenkopf, daher beginnt die Liste ab sofort am Nachfolgerelement */
 
    head = head->Next;          // Listenkopf verschieben
    DeleteNode( NULL, node );   // alten Listenkopf entfernen
  }
  else
  {
    /* Es ist nicht das Kopfelement */
 
    int index = GetIndex( head, node );
    struct AddressNode * prev = GetNode( head, index - 1 );
    DeleteNode( prev, node );
  }
 
  /* ... Freigabe der anderen Nodes ... */
 
  // Hierum werden wir uns im nächsten Kapitel kümmern - hier verschwinden sie jetzt unerlaubterweise mal im Nirvana
 
  return EXIT_SUCCESS;
}

Quelltexte zum Experimentieren als Make-Projekt: list_simple.zip