Example of a singly-linked list in C
This is an example C program demonstrating a singly-linked list containing arbitrary data.
This singly-linked list supports addition of elements to its end
with linked_list_add
, and traversing the list in order
with linked_list_traverse
. It is also able to free all
the memory allocated with linked_list_free
.
#include <stdlib.h> #include <stdio.h> /* 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 * next; }; /* linked_list_t contains a linked list. */ typedef struct linked_list { link_t * first; link_t * last; } linked_list_t; /* _ _ _ (_)_ __ (_) |_ | | '_ \| | __| | | | | | | |_ |_|_| |_|_|\__| */ /* The following function initializes the linked list by putting zeros into the pointers containing the first and last links of the linked list. */ static void linked_list_init (linked_list_t * list) { list->first = list->last = 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". */ static void linked_list_add (linked_list_t * list, 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) { list->last->next = link; list->last = link; } else { list->first = link; list->last = link; } } /* _ | |_ _ __ __ ___ _____ _ __ ___ ___ | __| '__/ _` \ \ / / _ \ '__/ __|/ _ \ | |_| | | (_| |\ V / __/ | \__ \ __/ \__|_| \__,_| \_/ \___|_| |___/\___| */ /* Go along the list and operate on the data of each element with "callback". */ static void linked_list_traverse (linked_list_t * list, void (*callback) (void *)) { link_t * link; for (link = list->first; link; link = link->next) { callback ((void *) link->data); } } /* Free the list's memory. */ static 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); } } /* Example callback function. */ static void print_list (void * data) { printf ("%s ", (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, "this"); linked_list_add (& list, "is"); linked_list_add (& list, "a"); linked_list_add (& list, "linked"); linked_list_add (& list, "list"); linked_list_traverse (& list, print_list); printf ("\n"); linked_list_free (& list); return 0; }
The output of the example looks like this:
this is a linked list
A singly linked list is useful for the case when one wants to create a list of things and add to the end of the list. It is possible to delete elements from a singly-linked list, but a doubly-linked list makes deletion simpler.
Thanks to Bill Martin for spotting an error on this page.
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