Playing with a Double-Linked List

Posted on by

In last week’s Lesson, I demonstrated code that builds a double-linked list: Each structure in the list references both the next structure and the previous structure. The first and last structure addresses are saved. And NULL pointers within the list its start and end. How all that junk becomes useful is apparent as you work with the list.

The code presented in last week’s Lesson walked through the linked list from the first structure to the last, displaying each structure’s data. This feat you can perform in single-linked lists as well. To move through a double-linked list in reverse order, the code looks like this:

    /* display list back-to-front */
    current = last;
    while(current)
    {
        printf("%s\n",current->letter);
        current = current->prev;
    }

The current pointer is assigned to the last structure in the list (instead of first). Within the while loop, the current pointer is updated to the value of current->prev instead of current->next. The result is that the first ten letters of the Greek alphabet are output in reverse order:

kappa
iota
theta
eta
zeta
epsilon
delta
gamma
beta
alpha

For a standard, single-linked list, this task would be difficult, especially if you wanted to show the list both ways in the same program. Click here to view the full code.

Another advantage of a double-linked list is that you can move forward or backward from any specific structure, even accessing neighboring structure’s data.

The following code accesses the fifth structure in the linked list. It displays the current, previous, and next letter names in the Greek alphabet:

    /* display item 5 in the list */
    current = first;
    for(x=0;x<4;x++)
        current = current->next;
    printf("The fifth letter is %s\n",current->letter);
    printf("The previous letter is %s\n",(current->prev)->letter);
    printf("The next letter is %s\n",(current->next)->letter);

The for loop advances the current pointer through the list. Because variable x is post-incremented in the for loop, the value of x equals 4 when the loop is done, which represents the fifth item in the list.

The letter name of the current pointer’s structure is accessed from current->letter.

The previous structure is referenced through the current->prev pointer. That structure’s letter member is accessed through the (current->prev)->letter construction. Likewise, the next structure’s letter member is accessed by using (current->next)->letter. (The parentheses are optional; I’ve added them for readability.)

Here’s the output:

The fifth letter is epsilon
The previous letter is delta
The next letter is zeta

Similar output could be generated for each structure in the list; previous and next structures’ members can always be accessed. Click here to view the full code.

Just to be obnoxious, the following construction is also possible with a linked list:

    /* display item 5 in the list */
    printf("The fifth letter is %s\n",
            first->next->next->next->next->letter);

I find this type of structure-pointer reference ugly, yet it proves that the method shown earlier ((current->next)->letter) isn’t really as weird as it potentially could be.

4 thoughts on “Playing with a Double-Linked List”

  1. The main advantage of using a linked list is fast insertion and deletion: you just need to reassign pointers whereas with an array you would need to move other items forward or backwards to inset or delete.

    The downsides are extra memory for all those pointers, and only having serial access (although of course in both directions with a double linked list).

    It’s therefore a design decision which type of data structure to use depending on the requirements of the particular project.

    By the way, some people reading the code might wonder why it’s necessary to cast the return value of malloc to a greek pointer. Actually it isn’t but it can make the code clearer.

  2. I suppose you could also add the pointers to an array, which would allow for random access. That gets messy when structures are inserted and deleted, however.

    My casting of the malloc() function is out of habit. Yes, it does make the statement look less comprehensible, but I’m conditioned to always cast a pointer. And at one time, the compiler might have groused about not casting, but not any more!

  4. I cover inserting and deleting structures in the book. It works the same for a double-linked list, though you must update four pointers instead of two.

    Sorry if I misunderstood you about casting malloc(). It does add clarity and consistency to the code.

Leave a Reply