Code-Schnipsel

Analog zu Philip (broesel) seiner Linked List Lib möchte ich meine Implementierung einer doppelt verketteten Liste vorstellen.

/*
 * Copyright (c) 2010 Patrick-Oliver Scheinert
 *
 * Hiermit wird unentgeltlich, jeder Person, die eine Kopie der Software und
 * der zugehoerigen Dokumentationen (die "Software") erhaelt, die Erlaubnis
 * erteilt, uneingeschraenkt zu benutzen, inklusive und ohne Ausnahme, dem
 * Recht, sie zu verwenden, kopieren, aendern, fusionieren, verlegen,
 * verbreiten, unterlizenzieren und/oder zu verkaufen, und Personen, die diese
 * Software erhalten, diese Rechte zu geben, unter den folgenden Bedingungen:
 *
 * Der obige Urheberrechtsvermerk und dieser Erlaubnisvermerk sind in allen
 * Kopien oder Teilkopien der Software beizulegen.
 *
 * DIE SOFTWARE WIRD OHNE JEDE AUSDRUECKLICHE ODER IMPLIZIERTE GARANTIE
 * BEREITGESTELLT, EINSCHLIESSLICH DER GARANTIE ZUR BENUTZUNG FUER DEN
 * VORGESEHENEN ODER EINEM BESTIMMTEN ZWECK SOWIE JEGLICHER RECHTSVERLETZUNG,
 * JEDOCH NICHT DARAUF BESCHRAENKT. IN KEINEM FALL SIND DIE AUTOREN ODER
 * COPYRIGHTINHABER FUER JEGLICHEN SCHADEN ODER SONSTIGE ANSPRUECHE HAFTBAR ZU
 * MACHEN, OB INFOLGE DER ERFUELLUNG EINES VERTRAGES, EINES DELIKTES ODER ANDERS
 * IM ZUSAMMENHANG MIT DER SOFTWARE ODER SONSTIGER VERWENDUNG DER SOFTWARE
 * ENTSTANDEN.
 */

/**
 * Bsp.
 *
 * Node *stack = NULL;
 * Node *node = new_node();
 * unshift_node(&stack, &node);
 *
 * while (NULL != (node=shift_node(&stack)))
 *  free_node(&node);
 */


#ifndef my_stack
#define my_stack


#include <stdlib.h> // malloc, free
#include <assert.h> // assert


struct node {
 void        *data;
 struct node *prev;
 struct node *next;
} typedef Node;


inline Node * new_node ( void );
inline void * free_node ( Node ** const );
inline Node * delete_node ( Node ** const, Node ** const );
inline Node * unshift_node ( Node ** const, Node ** const );
inline Node * shift_node ( Node ** const );
inline Node * last_node ( Node ** const );
inline Node * push_node ( Node ** const, Node ** const );
inline Node * pop_node ( Node **const );


/*******************************************************************************
* Erstellt ein neues Element vom Typ Node.
*
* @return *Node oder NULL
*******************************************************************************/
inline
Node *
new_node () {
 Node *node = (Node *)malloc(sizeof(Node));

 if (NULL != node) {
  node->data = NULL;
  node->prev = NULL;
  node->next = NULL;
 }

 return node;
}


/*******************************************************************************
* Gibt Speicher frei und platziert Zeiger auf NULL.
*
* @param  **Node Zeiger auf Zeiger auf Struktur vom Typ Node.
* @return NULL
*******************************************************************************/
inline
void *
free_node ( Node ** const node ) {
 assert(NULL != node);

 if (NULL != *node) {
  if (NULL != (*node)->data)
   free((*node)->data);

  free(*node);
 }

 return (*node=NULL);
}


/*******************************************************************************
* Loescht Node-Element aus einer doppelt verketteten Liste.
*
* @param  Node** Liste, aus der geloescht wird.
* @param  Node** Element, welches geloescht wird.
* @return Node*  Element, welches geloescht wird.
*******************************************************************************/
inline
Node *
delete_node ( Node ** const stack,
              Node ** const node ) {
 assert(NULL != stack);
 assert(NULL != node);

 if (NULL != *node) {
  // Ist das zu loeschende Element das Erste in der Liste ...
  if (*stack == *node) {
   // ... muss *stack auf den Nachfolger von *node zeigen.
   // *node kann in diesem Fall keinen Vorgaenger haben.
   // Wenn *stack nach der Zuweisung ungleich NULL ist,
   // muss der Vorgaenger von *stack nun auf NULL zeigen.
   // Zuvor hat dieser auf *node bzw. *stack verwiesen.
   // Verwirrt? Ich auch ;-)
   if ((*stack = (*node)->next)) {
    (*stack)->prev = NULL;
   }
  }
  // Oder das zu loeschende Element ist irgendwo in der Liste
  // und *stack muss nicht angepasst werden.
  // Wird die Funktion vom Programmierer "richtig" eingesetzt,
  // kann (*node)->prev nicht NULL sein.
  else if(NULL != (*node)->prev) {
   // *node muss einen Vorgaenger haben,
   // weil es nicht das erste Element der Liste ist.
   // Wenn (*node)->next nicht NULL ist,
   // muss ((*node)->next)->prev angepasst werden.
   if ((((*node)->prev)->next = (*node)->next)) {
    ((*node)->next)->prev = (*node)->prev;
   }

   // Hinweis:
   // In den o.g. Bedingungen werden Rueckgabewerte von ZUWEISUNGEN ueberprueft!
   // Wird NULL zugewiesen, sind die Bedingungen nicht erfuellt.

   // Sicherstellen, dass die Funktion auch bei erneutem Aufruf mit den selben
   // Daten keinen Speicherzugriffsfehler verursacht.
   (*node)->prev = NULL;
   (*node)->next = NULL;
  }
 }

 return *node;
}


/*******************************************************************************
* Haengt Node-Element vorne an Liste an.
*
* @param  Node** Adresse des ersten Elementes eines Liste.
* @param  Node** Element, welches Liste anfuehren soll.
* @return Node** Neues, erstes Element der Liste.
*******************************************************************************/
inline
Node *
unshift_node ( Node ** const stack,
               Node ** const node ) {
 assert(NULL != stack);
 assert(NULL != node);

 if (NULL != *node) {
  if (NULL != *stack) {
   Node *index = *stack;

   // *stack sollte bereits auf das erste Element des Stapels zeigen.
   for (; index->prev; index=index->prev);

   index->prev   = *node;
   (*node)->next = index;
  }

  return (*stack=*node);
 }

 return *stack;
}


/*******************************************************************************
* Loescht das erste Node-Element aus einer doppelt verketteten Liste und gibt
* dieses zurueck.
*
* @param  Node** Liste, aus der geloescht wird.
* @return Node*  Ehemals erstes Element der Liste.
*******************************************************************************/
inline
Node *
shift_node ( Node ** const stack ) {
 assert(NULL != stack);

 Node *node = *stack;
 return delete_node(stack, &node);
}


/*******************************************************************************
* Gibt Zeiger auf das letzte Node-Element aus einer doppelt verketteten Liste
* zurueck.
*
* @param  Node** Liste.
* @return Node*  Das letzte Element der Liste.
*******************************************************************************/
inline
Node *
last_node ( Node ** const stack ) {
 assert(NULL != stack);

 if (NULL == *stack)
  return NULL;

 Node *last = *stack;
 for(; last->next; last=last->next);

 return last;
}


/*******************************************************************************
* Haengt Node-Element hinten an Liste an.
*
* @param  Node** Adresse des ersten Elementes eines Liste.
* @param  Node** Element, welches an Liste angehaengt werden soll.
* @return Node** Erste Element der Liste.
*******************************************************************************/
inline
Node *
push_node ( Node ** const stack,
            Node ** const node ) {
 assert(NULL != stack);
 assert(NULL != node);

 if (NULL != *node) {
  // Letzte Element der Liste ermitteln.
  // Wenn Liste gleich NULL, dann gibt last_node NULL zurueck.
  Node *last = last_node(stack);

  if (NULL != last) {
   last->next = *node;
   (*node)->prev = last;

   // Am Ende sollte (*node)->next auf NULL zeigen.
   // Vorerst wird das dem Programmierer als Feature offen gehalten.
  }
  else
   *stack = *node;
 }

 return *stack;
}


/*******************************************************************************
* Loescht das letzte Node-Element aus einer doppelt verketteten Liste und gibt
* dieses zurueck.
*
* @param  Node** Liste, aus der geloescht wird.
* @return Node*  Ehemals letztes Element der Liste.
*******************************************************************************/
inline
Node *
pop_node ( Node ** const stack ) {
 assert(NULL != stack);

 Node *last = last_node(stack);
 return delete_node(stack, &last);
}


#endif

Änderungen:
2012-01-07 Typecast bei malloc

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.