Linked-list which uses sentinels to avoid passing itself

This is a typical C implementation of a (doubly) linked-list.

Normal C implementation of a linked-list with two elements.

I want to avoid passing the element and the list itself to functions which operate on and possibly modify the list; the element alone should be all I need. I separated the prev and next into it’s own struct.

Still has problems.

This is not closed; start has nothing pointing to it, so I still need to pass List.

Circular linked list with undefined behaviour waiting to happen.

This is closed, but it has no way to differentiate the struct List from the struct Link; not only will this go round-and-round, it will crash.


This works. head and tail have a distinctive property that one of their pointers is null. I can test for this.

List.h, (C89/90,)

typedef void (*Action)(int *const);  struct X { struct X *prev, *next; }; struct Link { struct X x; int data; }; struct List { struct X head, tail; };  void ListClear(struct List *const list); void ListPush(struct List *const list, int *const add); void ListAddBefore(int *const data, int *const add); void ListForEach(struct List *const list, const Action action); 


#include <stddef.h> /* offset_of */ #include "List.h"  /* Minimal example without checks. */  static struct Link *x_upcast(struct X *const x) {     return (struct Link *)(void *)((char *)x - offsetof(struct Link, x)); }  static struct Link *data_upcast(int *const data) {     return (struct Link *)(void *)((char *)data - offsetof(struct Link, data)); }  static void add_before(struct X *const x, struct X *const add) {     add->prev = x->prev;     add->next = x;     x->prev->next = add;     x->prev = add; }  static void clear(struct List *const list) {     list->head.prev = list-> = 0;     list-> = &list->tail;     list->tail.prev = &list->head; }  /** Clears and removes all values from {list}, thereby initialising the {List}.  All previous values are un-associated. */ void ListClear(struct List *const list) {     if(!list) return;     clear(list); }  /** Initialises the contents of the node which contains {add} to add it to the  end of {list}. */ void ListPush(struct List *const list, int *const add) {     if(!list || !add) return;     add_before(&list->tail, &(data_upcast)(add)->x); }  /** Initialises the contents of the node which contains {add} to add it  immediately before {data}. */ void ListAddBefore(int *const data, int *const add) {     if(!data || !add) return;     add_before(&data_upcast(data)->x, &data_upcast(add)->x); }  /** Performs {action} for each element in {list} in the order specified. */ void ListForEach(struct List *const list, const Action action) {     struct X *x, *next_x;     if(!list || !action) return;     for(x = list->; (next_x = x->next); x = next_x)         action(&(x_upcast)(x)->data); } 

Use this as,

#include <stdio.h>  /* printf */ #include <stdlib.h> /* EXIT_ */ #include <errno.h> #include "List.h"  /* Very basic fixed capacity; returns null after full. */ static struct Link links[20]; static const size_t links_no = sizeof links / sizeof *links; static size_t links_used; static int *get_link(const int data) {     struct Link *link;     if(links_used >= links_no) { errno = ERANGE; return 0; }     link = links + links_used++;     link->data = data;     return &link->data; }  static void sub_ten(int *const i) { ListAddBefore(i, get_link(*i - 10)); }  static void show(int *const i) { printf("%d.\n", *i); }  static struct List list;  int main(void) {     size_t i;     ListClear(&list);     /* Create 10 nodes, [1, 10]. */     for(i = 0; i < 10; i++) ListPush(&list, get_link(links_used + 1));     /* Creates a copy of all the data minus ten. */     ListForEach(&list, &sub_ten);     /* Prints. */     ListForEach(&list, &show);     return errno ? perror("ints"), EXIT_FAILURE : EXIT_SUCCESS; } 


-9. 1. -8. 2. -7. 3. -6. 4. -5. 5. -4. 6. -3. 7. -2. 8. -1. 9. 0. 10. 

(If you go above the fixed number of elements, it will print an error.)

Do I really need four pointers in List to call it on Link alone? If I wanted to add the valid static initial state, I would have to branch each time I iterate on null/not-null. Further, how would I deal with two equivalent states, that is, = tail.prev = null and = tail; tail.prev = head, in the most robust way possible?