As if a linked list itself isn’t one of the most terrifying things in C, another beast exists: the double-linked list. It mixes structures and pointers and offers gross potential for extreme mayhem. That sounds like fun!
As a review, a linked list is a chain of structures. It works like an array, though it’s allocated dynamically: Each structure is created in memory and it references the next structure in the chain. That’s the “link” part, the specific structure member that’s a pointer to the next structure. Figure 1 illustrates the linked list concept.
Figure 1. A linked list should be this simple.
I cover linked lists in my book, Beginning Programming with C For Dummies. I don’t cover double-linked lists because the publisher allots me only so many pages and I have a lot of ground to cover. Double-linked lists got cut.
The concept of a double-linked list is like a linked list, but with one addition: a second pointer member that references the previous structure in the chain. Figure 2 illustrates the extra pointer as well as the original pointer as lines that reference other structures.
Figure 2. A double-linked list has a lot of pointers, links, and messy lines.
As you might suspect, it takes some thought to create and manage that second pointer. So why bother?
Yes, there is a reason: The advantage to the double-linked list is that you can work both forward and backward. You can reference the current structure, the next structure, and the previous structure. For complex data, this type of arrangement is beneficial.
To create a double-linked list, the structure must have two self-referencing structure pointers as members. One references the next structure in the list and the other references the previous structure. Null pointers mark the start and end of the chain.
Here is an example of a double-linked list structure:
struct greek {
struct greek *prev;
char *letter;
struct greek *next;
};
greek is the name of the structure. Two members are pointers to other greek structures, *prev and *next. The other member is a char pointer, a string.
If multiple functions refer to the double-linked list structure, it must be declared externally. Further, the structure must be declared before any function that references the structure, as well as any structure variables. You can get into lots of trouble if you don’t heed this admonition.
To work with the double-linked list, four structure pointer variables are required:
struct greek *first;
struct greek *last;
struct greek *current;
struct greek *created;
The first and last pointers reference the first and last items in the double-linked list, respectively. first is set when the list is initially created; last is set when the final structure in the list is created. The current and created pointers are used as the list is built.
I’m using the variable name
createdfor newly-allocated structures in the linked list. The traditional variable name isnew, though new is a reserved word in the C++ language, so I shy away from it.
In next week’s Lesson, I present code that builds a double-linked list of greek structure variables.
May I suggest you combine the following:
struct greek *first;
struct greek *last;
struct greek *current;
struct greek *created;
into a struct?
There is also a data structure called a circular list where the last item points back to the first, although strictly speaking there is no first or last.
A problem with data structures like these in C is that you need a different one per struct type, as the struct itself incorporates 1 or 2 pointers. C# has generics which enable general-purpose code to be written to handle any specified type, for example you could write a linked list class that can be instantiated to handle objects of any class (although you wouldn’t bother as Microsoft have already done so, as part of the .NET Framework).
I’ll have to work out sometime how to write a set of general-purpose functions in C for managing a linked list using void pointers, preferably in a type-safe way. I have a book called Mastering Algorithms with C (Kyle Loudon / O’Reilly) which covers this topic so after I have figured it out for myself I’ll look at the book and see what he has to say on the matter.
It seems every language has a few books on data structures and algorithms, all covering basically the same material. Usually they are called something like “Data Structures and Algorithms in XYZ” but with the C book they didn’t bother with the “Data Structures and” bit of the title, even though the first half of the book covers them.
Yes, C is weak on data structures, so a linked list is how it’s done for just about everything. In fact, I’d offer that other languages coded in C use double-linked lists internally for their fancy data structures.
Can you explain the advantage of sticking the four pointers into a single structure? It seems like extra overhead to me.
Also, is what you refer to as a “circular list” a ring buffer? I’ve used ring buffers before but am unfamiliar with a circular list.
Thank you for your input, Chris!
According to Wikipedia “A circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end” so it’s different to a linked list as it’s fixed size.
https://en.wikipedia.org/wiki/Circular_buffer
The study of data structures can sometimes be rather overwhelming – you start off with a few basic ones, discover there are more and more variations on those, and then discover that many of them have several different names!
Whenever I have two or more related variables my instinct is to combine them into a struct, even in C. Maybe it is because I have been using various OO languages for a long time. My thinking is that you then just have one variable to deal with as a single point of access to all the data structure’s bits and pieces. If you have more than one linked list in your program this could simplify the code considerably.
That’s a good observation and probably the exact way I’d handle multiple linked lists. Thank you, Chris.