Example of a doubly-linked list in C
This is an example C program for a doubly-linked list. It illustrates traversing the list in either order and deleting elements from the list. To run the example program, compile it with DLLTEST defined:
cc -DDLLTEST dll.c
#include <stdlib.h> #include <stdio.h> #ifdef DLLTEST /* strchr, declared in string.h, is used in the examples. */ #include <string.h> #define HEADER #else #include "dll.h" #endif #ifdef HEADER /* The type link_t needs to be forward-declared in order that a self-reference can be made in "struct link" below. */ typedef struct link link_t; /* _ _ _ | (_)_ __ | | __ | | | '_ \| |/ / | | | | | | < |_|_|_| |_|_|\_\ */ /* A link_t contains one of the links of the linked list. */ struct link { const void * data; link_t * prev; link_t * next; }; /* _ _ _ _ _ _ _ | (_)_ __ | | _____ __| | | (_)___| |_ | | | '_ \| |/ / _ \/ _` | | | / __| __| | | | | | | < __/ (_| | | | \__ \ |_ |_|_|_| |_|_|\_\___|\__,_|___|_|_|___/\__| |_____| */ /* linked_list_t contains a linked list. */ typedef struct linked_list { int count; link_t * first; link_t * last; } linked_list_t; #endif /* def HEADER */ /* The following function initializes the linked list by putting zeros into the pointers containing the first and last links of the linked list. */ void linked_list_init (linked_list_t * list) { list->first = list->last = 0; list->count = 0; } /* _ _ __ _ __| | __| | / _` |/ _` |/ _` | | (_| | (_| | (_| | \__,_|\__,_|\__,_| */ /* The following function adds a new link to the end of the linked list. It allocates memory for it. The contents of the link are copied from "data". */ void linked_list_add (linked_list_t * list, const void * data) { link_t * link; /* calloc sets the "next" field to zero. */ link = calloc (1, sizeof (link_t)); if (! link) { fprintf (stderr, "calloc failed.\n"); exit (EXIT_FAILURE); } link->data = data; if (list->last) { /* Join the two final links together. */ list->last->next = link; link->prev = list->last; list->last = link; } else { list->first = link; list->last = link; } list->count++; } /* _ _ _ __| | ___| | ___| |_ ___ / _` |/ _ \ |/ _ \ __/ _ \ | (_| | __/ | __/ || __/ \__,_|\___|_|\___|\__\___| */ void linked_list_delete (linked_list_t * list, link_t * link) { link_t * prev; link_t * next; prev = link->prev; next = link->next; if (prev) { if (next) { /* Both the previous and next links are valid, so just bypass "link" without altering "list" at all. */ prev->next = next; next->prev = prev; } else { /* Only the previous link is valid, so "prev" is now the last link in "list". */ prev->next = 0; list->last = prev; } } else { if (next) { /* Only the next link is valid, not the previous one, so "next" is now the first link in "list". */ next->prev = 0; list->first = next; } else { /* Neither previous nor next links are valid, so the list is now empty. */ list->first = 0; list->last = 0; } } free (link); list->count--; } /* _ | |_ _ __ __ ___ _____ _ __ ___ ___ | __| '__/ _` \ \ / / _ \ '__/ __|/ _ \ | |_| | | (_| |\ V / __/ | \__ \ __/ \__|_| \__,_| \_/ \___|_| |___/\___| */ void linked_list_traverse (linked_list_t * list, void * data, void (*callback) (void *, void *)) { link_t * link; for (link = list->first; link; link = link->next) { callback (data, (void *) link->data); } } /* _ __ _____ _____ _ __ ___ ___ | '__/ _ \ \ / / _ \ '__/ __|/ _ \ | | | __/\ V / __/ | \__ \ __/ |_| \___| \_/ \___|_| |___/\___| */ void linked_list_traverse_in_reverse (linked_list_t * list, void * data, void (*callback) (void *, void *)) { link_t * link; for (link = list->last; link; link = link->prev) { callback (data, (void *) link->data); } } /* _ | |_ _ __ __ ___ _____ _ __ ___ ___ | __| '__/ _` \ \ / / _ \ '__/ __|/ _ \ | |_| | | (_| |\ V / __/ | \__ \ __/ \__|_| \__,_| \_/ \___|_| |___/\___| ___ _ _ _ ( _ ) __| | ___| | ___| |_ ___ / _ \/\ / _` |/ _ \ |/ _ \ __/ _ \ | (_> < | (_| | __/ | __/ || __/ \___/\/ \__,_|\___|_|\___|\__\___| */ void linked_list_traverse_delete (linked_list_t * list, int (*callback) (void *)) { link_t * link; link_t * next; for (link = list->first; link; link = next) { next = link->next; if (callback ((void *) link->data)) { linked_list_delete (list, link); } } } /* __ / _|_ __ ___ ___ | |_| '__/ _ \/ _ \ | _| | | __/ __/ |_| |_| \___|\___| */ /* Free the list's memory. */ void linked_list_free (linked_list_t * list) { link_t * link; link_t * next; for (link = list->first; link; link = next) { /* Store the next value so that we don't access freed memory. */ next = link->next; free (link); } } #ifdef DLLTEST /* Example traverse delete function - delete everything. */ static int delete_all (void * data) { return 1; } /* Example traverse delete function - delete things with an "a" in them. */ static int delete_a (void * data) { return (int) strchr ((char *) data, 'a'); } /* Example callback function. */ static void print_list (void * user_data, void * data) { printf ("\t%s\n", (char *) data); } /* Make a list of words and then print them out. */ int main () { linked_list_t list; linked_list_init (& list); linked_list_add (& list, "dingo"); linked_list_add (& list, "kangaroo"); linked_list_add (& list, "koala"); linked_list_add (& list, "kookaburra"); linked_list_add (& list, "tasmanian devil"); linked_list_add (& list, "wallabee"); linked_list_add (& list, "wallaroo"); linked_list_add (& list, "wombat"); printf ("Australian animals, in reverse alphabetical order:\n"); linked_list_traverse_in_reverse (& list, 0, print_list); printf ("\n"); linked_list_traverse_delete (& list, delete_a); printf ("These Australian animals don't have an 'a' in their names:\n"); linked_list_traverse (& list, 0, print_list); printf ("\n"); linked_list_traverse_delete (& list, delete_all); printf ("All the Australian animals are now extinct:\n"); linked_list_traverse (& list, 0, print_list); printf ("\n"); linked_list_free (& list); return 0; } #endif /* def DLLTEST */
The output of the example looks like this:
Australian animals, in reverse alphabetical order: wombat wallaroo wallabee tasmanian devil kookaburra koala kangaroo dingo These Australian animals don't have an 'a' in their names: dingo All the Australian animals are now extinct:
Doubly-linked lists are similar to singly-linked lists but they also make it easy to traverse the list in either direction. They also make it easier to delete elements from the list.
Acknowledgements: Nicolas Chaufette found an error in the code.
Web links
-
Support Australian Wildlife Conservancy
To help prevent real Australian animals from becoming extinct, support the Australian Wildlife Conservancy.
Copyright © Ben Bullock 2009-2024. All
rights reserved.
For comments, questions, and corrections, please email
Ben Bullock
(benkasminbullock@gmail.com) or use the discussion group at Google Groups.
/
Privacy /
Disclaimer