cdll.h-Dateireferenz

CDLL - Circular Double Linked List. Mehr ...

#include <stdbool.h>

gehe zum Quellcode dieser Datei

Datenstrukturen
struct	cdll_t

Funktionen
void	cdll_reset (cdll_t *head)
	Listenkopf der CDLL initialisieren Die Liste ist nach dem Aufruf der Funktion leer und kann verwendet werden. Mehr ...
static bool	cdll_is_empty (cdll_t *head)
	Prüft ob die CDLL-Liste leer ist (also nur aus dem Kopf besteht)
void	cdll_push_front (cdll_t *head, cdll_t *entry)
	Ein Element dem Anfang der CDLL hinzufügen. Mehr ...
void	cdll_push_back (cdll_t *head, cdll_t *entry)
	Ein Element dem Ende der CDLL hinzufügen. Mehr ...
void	cdll_move_front (cdll_t *head, cdll_t *entry)
	Ein Element aus einer beliebigen CDLL entfernen und an den Anfang der übergebenen CDLL setzen. Mehr ...
void	cdll_move_back (cdll_t *head, cdll_t *entry)
	Ein Element aus einer beliebigen CDLL entfernen und an das Ende der übergebenen CDLL setzen. Mehr ...
cdll_t *	cdll_pop_front (cdll_t *head)
	Das erste Element der CDLL entfernen und zurückliefern Liefert 0 zurück wenn die Liste leer ist.
cdll_t *	cdll_pop_back (cdll_t *head)
	Das letzte Element der CDLL entfernen und zurückliefern Liefert 0 zurück wenn die Liste leer ist.
static cdll_t *	cdll_peek_front (cdll_t *head)
	Das erste Element der CDLL zurückliefern Liefert 0 zurück wenn die Liste leer ist.
static cdll_t *	cdll_peek_back (cdll_t *head)
	Das letzte Element der CDLL zurückliefern Liefert 0 zurück wenn die Liste leer ist.
void	cdll_remove (cdll_t *entry)
	Dieses Element aus seiner Liste entfernen.
bool	cdll_contains (cdll_t *head, cdll_t *entry)
	Prüfen ob dieses Element in der Liste enthalten ist.

Ausführliche Beschreibung

CDLL - Circular Double Linked List.

Bei einer doppelt verketteten Liste gibt es bei jedem Element jeweils einen Zeiger auf den Nachfolger und auf den Vorgänger. Bei dieser Implementation wird aus Optimierungsgründen ein zusätzliches Element, der Listenkopf, in die Liste aufgenommen. Dieses Kopfelement wird jedoch bei der Zählung und der Abarbeitung der Liste ignoriert. Die leere Liste enthält nur das Kopfelement. Durch diesen Trick entfallen alle Sonderfälle beim Löschen und Einfügen von Elementen.

        sec. last      last         HEAD         first       second
       +--------+   +--------+   +--------+   +--------+   +--------+
... -->|  next  |-->|  next  |-->|  next  |-->|  next  |-->|  next  |--> ...
... <--|  prev  |<--|  prev  |<--|  prev  |<--|  prev  |<--|  prev  |<-- ...
       +--------+   +--------+   +--------+   +--------+   +--------+
       |        |   |        |                |        |   |        |
       |  DATA  |   |  DATA  |                |  DATA  |   |  DATA  |
       |        |   |        |                |        |   |        |
       +-- -- --+   +-- -- --+                +-- -- --+   +-- -- --+

Bei der leeren Liste zeigen sowohl der next, wie auch der prev Zeiger des Head Elements wiederum auf das Head Element.

Dokumentation der Funktionen

void cdll_move_back	(	cdll_t *	head,
		cdll_t *	entry
	)

Ein Element aus einer beliebigen CDLL entfernen und an das Ende der übergebenen CDLL setzen.

Nachbedingung

cdll_peek_back(head) == entry

void cdll_move_front	(	cdll_t *	head,
		cdll_t *	entry
	)

Ein Element aus einer beliebigen CDLL entfernen und an den Anfang der übergebenen CDLL setzen.

Nachbedingung

cdll_peek_front(head) == entry

void cdll_push_back	(	cdll_t *	head,
		cdll_t *	entry
	)

Ein Element dem Ende der CDLL hinzufügen.

Nachbedingung

cdll_peek_back(head) == entry

void cdll_push_front	(	cdll_t *	head,
		cdll_t *	entry
	)

Ein Element dem Anfang der CDLL hinzufügen.

Nachbedingung

cdll_peek_front(head) == entry

void cdll_reset

(

cdll_t *

head

)

Listenkopf der CDLL initialisieren Die Liste ist nach dem Aufruf der Funktion leer und kann verwendet werden.

Muss vor der ersten Verwendung einer CDLL-Liste aufgerufen werden!

Nachbedingung

cdll_is_empty(head) == true