A doubly linked list is a data structure consisting of a group of nodes linked together linearly. Each node consists of data elements with links to the next node and previous nodes. The main advantage of linked lists (over simple arrays) is the nodes can be inserted and removed anywhere in the list without reallocating the entire array. Linked list nodes don't need to be stored contiguously in memory, but nodes then you can't access by index, you have to be access by traversing the list.

Creating and Initializing Lists

To create and initialize a linked list the user must create a le_dls_List_t typed list and assign LE_DLS_LIST_INIT to it. The assignment of LE_DLS_LIST_INIT can be done either when the list is declared or after its declared. The list must be initialized before it can be used.

// Create and initialized the list in the declaration.

le_dls_List_t MyList = LE_DLS_LIST_INIT;

Or

// Create list.
le_dls_List_t MyList;
// Initialize the list.
MyList = LE_DLS_LIST_INIT;

Elements of le_dls_List_t MUST NOT be accessed directly by the user.

Creating and Accessing Nodes

Nodes can contain any data in any format and is defined and created by the user. The only requirement for nodes is that it must contain a le_dls_Link_t link member. The link member must be initialized by assigning LE_DLS_LINK_INIT to it before it can be used. Nodes can then be added to the list by passing their links to the add functions (le_dls_Stack(), le_dls_Queue(), etc.). For example:

// The node may be defined like this.
typedef struct
{
     dataType someUserData;
     ...
     le_dls_Link_t myLink;
}
MyNodeClass_t;
// Create and initialize the list.
le_dls_List_t MyList = LE_DLS_LIST_INIT;
void foo (void)
{
    // Create the node.  Get the memory from a memory pool previously created.
    MyNodeClass_t* myNodePtr = le_mem_ForceAlloc(MyNodePool);
    // Initialize the node's link.
    myNodePtr->myLink = LE_DLS_LINK_INIT;
    // Add the node to the head of the list by passing in the node's link.
    le_dls_Stack(&MyList, &(myNodePtr->myLink));
}

The links in the nodes are actually added to the list and not the nodes themselves. This allows a node to be included on multiple lists through links added to different lists. It also allows linking different type nodes in a list.

To obtain the node itself, use the CONTAINER_OF macro defined in le_basics.h. Here's a code sample using CONTAINER_OF to obtain the node:

// Assuming mylist has been created and initialized and is not empty.
le_dls_link_t* linkPtr = le_dls_Peek(&MyList);
// Now we have the link but still need the node to access user data.
// We use CONTAINER_OF to get a pointer to the node given the node's link.
if (linkPtr != NULL)
{
    MyNodeClass_t* myNodePtr = CONTAINER_OF(linkPtr, MyNodeClass_t, myLink);
}

The user is responsible for creating and freeing memory for all nodes; the linked list module only manages the links in the nodes. The node must be removed from all lists before its memory can be freed.

The elements of le_dls_Link_t MUST NOT be accessed directly by the user.

Adding Links to a List

To add nodes to a list, pass the node's link to one of these functions:

le_dls_Stack() - Adds the link to the head of the list.
le_dls_Queue() - Adds the link to the tail of the list.
le_dls_AddAfter() - Adds the link to a list after another specified link.
le_dls_AddBefore() - Adds the link to a list before another specified link.

Removing Links from a List

To remove nodes from a list, use one of these functions:

le_dls_Pop() - Removes and returns the link at the head of the list.
le_dls_PopTail() - Removes and returns the link at the tail of the list.
le_dls_Remove() - Remove a specified link from the list.

Accessing Links in a List

To access a link in a list without removing the link, use one of these functions:

le_dls_Peek() - Returns the link at the head of the list without removing it.
le_dls_PeekTail() - Returns the link at the tail of the list without removing it.
le_dls_PeekNext() - Returns the link next to a specified link without removing it.
le_dls_PeekPrev() - Returns the link previous to a specified link without removing it.

Swapping Links

To swap two links, use:

le_dls_Swap() - Swaps the position of two links in a list.

The le_dls_Swap() function can be used to sort a list.

Querying List Status

These functions can be used to query a list's current status:

le_dls_IsEmpty() - Checks if a given list is empty.
le_dls_IsInList() - Checks if a specified link is in the list.
le_dls_IsHead() - Checks if a specified link is at the head of the list.
le_dls_IsTail() - Checks if a specified link is at the tail of the list.
le_dls_NumLinks() - Checks the number of links currently in the list.
le_dls_IsListCorrupted() - Checks if the list is corrupted.

Queues and Stacks

This implementation of linked lists can be used for either queues or stacks.

To use the list as a queue, restrict additions to the list to le_dls_Queue() and removals from the list to le_dls_Pop().

To use the list as a stack, restrict additions to the list to le_dls_Stack() and removals from the list to le_dls_Pop().

Thread Safety and Re-Entrancy

All linked list function calls are re-entrant and thread safe. If the nodes and/or list object is shared by multiple threads, explicit steps must be taken to maintain mutual exclusion of access.

Copyright (C) Sierra Wireless Inc. Use of this work is subject to license.