Linked Lists

A linked list is a data structure that consists of a group of nodes that represent a sequence. A linked list has several benefits over a conventional array such that the capacity of the list does not need to be pre-allocated and the nodes can be added or removed from the list easily without reallocation or reorganization of the structure.

A linked list has links to the first and last nodes contained within the list; while each node has links to the next and previous nodes within the list. The two node links allow for traversal of the list in either the forward or backward direction. Each node within the list also contains a pointer to the value (application-defined object) for the node.

Any application-defined object can be placed into multiple lists, but there must be a unique NODE object for each of the lists that the application-defined object will be placed within. All of the list manipulation methods are not inherently thread safe therefore it is up to the calling user code to ensure there are no simultaneous accesses to a particular list (i.e. a list cannot be modified while it is being traversed).

Basic Usage

The following code snippet allocates and initializes a linked list.

#include "Kernel/kernel_list.h"

static LIST list;           /* Allocate a linked list */

void APP_Example(void)
{
    LIST_Init(&list);       /* Initialize the list */
}

Each object that is placed into a linked list requires a NODE object. The NODE object provides the links (pointers) to the other nodes within the list. Although the NODE object could be dynamically allocated, for memory constrained applications it can be advantageous to have the NODE as part of the object that is being placed into a list. An example snippet below illustrates how to define an object using a structure that also provides a built-in node.

#include "Kernel/kernel_list.h"

/* A custom application-defined object */
typedef struct MYOBJECT {
    NODE    node;           /* Allocate a node for inserting into the linked list */
    UINT32  x;              /* An example variable */
    UINT32  y;              /* An example variable */
} MYOBJECT;

static MYOBJECT obj1;       /* Allocate example application-specific object instances */
static MYOBJECT obj2;
static MYOBJECT obj3;

void APP_Example(void)
{
    MYOBJECT* obj;


    LIST_AddLast(&list, &obj1.node, &obj1);     /* Insert each of the example objects into the list */
    LIST_AddLast(&list, &obj2.node, &obj2);
    LIST_AddLast(&list, &obj3.node, &obj3);


    /* The list maintains pointers to the first 
    and last objects contained within the list. */

    obj = LIST_First(&list);                    /* Get the first object within the list (pointer to obj1) */
    obj = LIST_Last(&list);                     /* Get the last object within the list (pointer to obj3) */
}

The following image illustrates the structure of the linked list and nodes as created from the code snippet above.

A list can be walked and iterated using a NODE pointer and the LIST_Foreach() macro. The list is searched forwards from first to last and provides a pointer to each node within the list. For each iteration, the application-defined object can be accessed using node->value. The code snippet below iterates and initializes each object within the list.

void APP_Example(void)
{
    NODE* node;
    MYOBJECT* obj;


    LIST_Foreach(node, &list) {     /* Traverse the list */
        obj = node->value;          /* Capture the value contained within the node */

        obj->x = 0;                 /* Access the application-defined object */
        obj->y = 0;
    }
}