Similar to a linked list, a double-linked list requires that you work on both the current item in the list as well as the the previous item. You just have one additional structure member to update, which is the pointer from the current item to the previous structure.

In a linked list, two pointer variables are used to create the list. They reference the current and newly-created structures in the list, so I use the variable names current and created (formerly “new”). After allocating the created structure, you update the current structure’s member referencing that new structure, *next, as in:

current->next=created;

So the current structure’s next member helps find the next structure in the list, created.

In a double-linked list you must also set the created structure’s *prev member to reference the previous structure. That structure’s location is saved in the current pointer:

created->prev=current;

That’s really all the overhead you need, though the sequence of events is crucial.

The following code uses the greek structure introduced in last week’s Lesson. The double-linked list created contains the names of the first ten letters of the Greek alphabet.

#include <stdio.h>
#include <stdlib.h>

#define ITEMS 10

int main()
{
    struct greek {
        struct greek *prev;
        char *letter;
        struct greek *next;
    };
    char *ab[] = {
        "alpha", "beta", "gamma", "delta", "epsilon",
        "zeta", "eta", "theta", "iota", "kappa"
    };
    struct greek *first,*last,*current,*created;
    int x;

    /* build the double-linked list */
    for(x=0;x<=<ITEMS;x++)
    {
        created = (struct greek *)malloc(sizeof(struct greek));
        if( created==NULL )
        {
            puts("Unable to allocate memory");
            exit(1);
        }
        /* first item in the list is special */
        if( x==0 )
        {
            created->prev = NULL;
            first = created;
        }
        else
        {
            created->prev = current;
            current->next = created;
        }
        created->letter = ab[x];
        created->next = NULL;
        current = created;
    }
    last = current;

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

    return(0);
}

The code has a lot of setup, which is necessary for a double-linked list: The structure greek is declared at the start of the main() function, as is the *ab[] array, and the pointers required to manage the structure. Because this example uses only the main() function, the greek structure as well as the pointers are declared inside that function. If any other functions referenced the structure pointers, they must be declared externally.

The core of the code is the for loop between Lines 21 and 43.

Line 23 allocates memory for a new structure and assigns that address to the created pointer.

Lines 30 through 34 handle the first item in the double-linked list, which is special: Line 32 sets the *prev element to NULL, marking the start of the list. The first pointer is assigned to the beginning structure to mark its location for reference.

The else statements set options for all structures after the first: The current pointer references what becomes the previous structure in the list; its location is saved in the created structure’s *prev member. The current structure’s *next member is updated to point to the created structure’s address:

created->prev = current;
current->next = created;

Next, the new (created) structure’s letter member is set to a letter of the Greek alphabet (Line 40). The *next member is assigned the NULL pointer. Finally, Line 42 sets the new structure to the current pointer, current=created.

When the for loop is complete, the last pointer is updated to reference current, which becomes the final structure in the list.

To prove that it all works, a while loop displays the double-linked list:

alpha
beta
gamma
delta
epislon
zeta
eta
theta
iota
kappa

Because the list is double-linked, you can also display it in reverse order, as well as reference previous and next items from within the list. I'll explore these options in next week's Lesson.