Appendix A. Linked Lists

A linked list is a data structure that allows the storage and manipulation of a variable number of nodes of data. Unlike a static array, the elements in a linked list are dynamically created. This enables the creation of a variable number of elements that are unknown at compile time. Because the elements are created at different times, they do not necessarily occupy contiguous regions in memory. Therefore, the elements need to be linked together, so each element contains a pointer to the next element. As elements are added or removed from the list, the pointer to the next node is simply adjusted.

The simplest data structure representing such a linked list would look similar to the following:

/* an element in a linked list */
struct list_element {
        void *data;                   /* the payload */
        struct list_element *next;    /* pointer to the next element */
};

Figure A.1 is a linked list.

In some linked lists, each element also contains a pointer to the previous element. These lists are called doubly linked lists because they are linked both forward and backward. Linked lists, similar to the one in Figure A.1, that do not have a pointer to the previous element are called singly linked lists.

A data structure representing a doubly linked list would look similar to this:

/* an element in a linked list */
struct list_element {
        void *data;                   /* the payload */
        struct list_element *next;    /* pointer to the next element */
        struct list_element *prev;    /* pointer to the previous element */
};

Figure A.2 is a doubly linked list.