Related Books
Books / Introduction to C Programming Language / Chapter 27
Circular linked lists
For some applications, there is no obvious starting or ending point to a list, and a circular list (where the last element points back to the first) may be appropriate. Circular doubly-linked lists can also be used to build deques; a single pointer into the list tracks the head of the deque, with some convention adopted for whether the head is an actual element of the list (at the front, say, with its left neighbor at the back) or a extra element that is not considered to be part of the list.
The selling point of circular doubly-linked lists as a concrete data structure is that insertions and deletions can be done anywhere in the list with only local information. For example, here are some routines for manipulating a doubly-linked list directly. We’ll make our lives easy and assume (for the moment) that the list has no actual contents to keep track of.
#include <stdlib.h>
/* directions for doubly-linked list next pointers */
#define RIGHT (0)
#define LEFT (1)
struct elt {
struct elt *next[2];
};
typedef struct elt *Elt;
/* create a new circular doubly-linked list with 1 element */
/* returns 0 on allocation error */
Elt
listCreate(void)
{
Elt e;
e = malloc(sizeof(*e));
if(e) {
e->next[LEFT] = e->next[RIGHT] = e;
}
return e;
}
/* remove an element from a list */
/* Make sure you keep a pointer to some other element! */
/* does not free the removed element */
void
listRemove(Elt e)
{
/* splice e out */
e->next[RIGHT]->next[LEFT] = e->next[LEFT];
e->next[LEFT]->next[RIGHT] = e->next[RIGHT];
}
/* insert an element e into list in direction dir from head */
void
listInsert(Elt head, int dir, Elt e)
{
/* fill in e's new neighbors */
e->next[dir] = head->next[dir];
e->next[!dir] = head;
/* make neigbhors point back at e */
e->next[dir]->next[!dir] = e;
e->next[!dir]->next[dir] = e;
}
/* split a list, removing all elements between e1 and e2 */
/* e1 is the leftmost node of the removed subsequence, e2 rightmost */
/* the removed elements are formed into their own linked list */
/* comment: listRemove could be implemented as listSplit(e,e) */
void
listSplit(Elt e1, Elt e2)
{
/* splice out the new list */
e2->next[RIGHT]->next[LEFT] = e1->next[LEFT];
e1->next[LEFT]->next[RIGHT] = e2->next[RIGHT];
/* fix up the ends */
e2->next[RIGHT] = e1;
e1->next[LEFT] = e2;
}
/* splice a list starting at e2 after e1 */
/* e2 becomes e1's right neighbor */
/* e2's left neighbor becomes left neighbor of e1's old right neighbor */
void
listSplice(Elt e1, Elt e2)
{
/* fix up tail end */
e2->next[LEFT]->next[RIGHT] = e1->next[RIGHT];
e1->next[RIGHT]->next[LEFT] = e2->next[LEFT];
/* fix up e1 and e2 */
e1->next[RIGHT] = e2;
e2->next[LEFT] = e1;
}
/* free all elements of the list containing e */
void
listDestroy(Elt e)
{
Elt target;
Elt next;
/* we'll free elements until we get back to e, then free e */
/* note use of pointer address comparison to detect end of loop */
for(target = e->next[RIGHT]; target != e; target = next) {
next = target->next[RIGHT];
free(target);
}
free(e);
}
examples/linkedLists/circular.c
The above code might or might not actually work. What if it doesn’t? It may make sense to include some consistency testing code that we can run to see if our pointers are all going to the right place:
/* assert many things about correctness of the list */
/* Amazingly, this is guaranteed to abort or return no matter
how badly screwed up the list is. */
void
listConsistencyTest(Elt e)
{
Elt check;
assert(e != 0);
check = e;
do {
/* are our pointers consistent with our neighbors? */
assert(check->next[RIGHT]->next[LEFT] == check);
assert(check->next[LEFT]->next[RIGHT] == check);
/* on to the next */
check = check->next[RIGHT];
} while(check != e);
}
What if we want to store something in this list? The simplest approach is to extend the definition of struct elt:
struct elt {
struct elt *next[2];
char *name;
int socialSecurityNumber;
int gullibility;
};
But then we can only use the code for one particular type of data. An alternative approach is to define a new Elt-plus struct:
struct fancyElt {
struct elt *next[2];
char *name;
int socialSecurityNumber;
int gullibility;
};
and then use pointer casts to convert the fancy structs into Elts:
struct fancyElt *e;
e = malloc(sizeof(*e));
/* fill in fields on e */
listInsert(someList, (Elt) e);
The trick here is that as long as the initial part of the struct fancyElt looks like a struct elt, any code that expects a struct elt will happily work with it and ignore the fields that happen to be sitting later in memory. (This is how C++ inheritance works.)
The downside is that if something needs to be done with the other fields (e.g freeing e->name if e is freed), then the Elt functions won’t know to do this. So if you use this trick you should be careful.
A similar technique using void * pointers can be used to implement generic containers.
Useful resources:
- Animated versions can be found at http://www.cs.usfca.edu/~galles/visualization/Algorithms.html.
#/media/File:Tallrik_-_Ystad-2018.jpg){kind=link}