A singly linked list is a data structure consisting of a group of nodes linked together linearly. Each node consists of data elements and a link to the next node. The main advantage of linked lists over simple arrays is that the nodes can be inserted anywhere in the list without reallocating the entire array because the nodes in a linked list do not need to be stored contiguously in memory. However, nodes in the list cannot be accessed by index but must be accessed by traversing the list.

Creating and Initializing Lists

To create and initialize a linked list, create a le_sls_List_t typed list and assign LE_SLS_LIST_INIT to it. The assignment of LE_SLS_LIST_INIT can be done either when the list is declared or after it's declared. The list must be initialized before it can be used.

// Create and initialized the list in the declaration.

le_sls_List_t MyList = LE_SLS_LIST_INIT;

Or

// Create list.
le_sls_List_t MyList;
// Initialize the list.
MyList = LE_SLS_LIST_INIT;

The elements of le_sls_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_sls_Link_t link member. The link member must be initialized by assigning LE_SLS_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_sls_Stack(), le_sls_Queue(), etc.). For example:

// The node may be defined like this.
typedef struct
{
     dataType someUserData;
     ...
     le_sls_Link_t myLink;
}
MyNodeClass_t;
// Create and initialize the list.
le_sls_List_t MyList = LE_SLS_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_SLS_LINK_INIT;
    // Add the node to the head of the list by passing in the node's link.
    le_sls_Stack(&MyList, &(myNodePtr->myLink));
}

The links in the nodes are added to the list and not the nodes themselves. This allows a node to be simultaneously part of multiple lists simply by having multiple links and adding the links into differently lists. This also means that nodes in a list can be of different types.

Because the links and not the nodes are in the list, the user must have a way to obtain the node itself from the link. This is achieved using the CONTAINER_OF macro defined in le_basics.h. This code sample shows using CONTAINER_OF to obtain the node:

// Assuming mylist has been created and initialized and is not empty.
le_sls_link_t* linkPtr = le_sls_Peek(&MyList);
// Now we have the link but we want the node so we can access the 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 simply manages the links in the nodes. The node must first be removed from all lists before its memory is freed.

The elements of le_sls_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 the following functions:

le_sls_Stack() - Adds the link to the head of the list.
le_sls_Queue() - Adds the link to the tail of the list.
le_sls_AddAfter() - Adds the link to a list after another specified link.

Removing Links from a List

To remove nodes from a list, use le_sls_Pop() to remove and return the link at the head of the list.

Accessing Links in a List

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

le_sls_Peek() - Returns the link at the head of the list without removing it.
le_sls_PeekNext() - Returns the link next to a specified link without removing it.
le_sls_PeekTail() - Returns the link at the tail of the list without removing it.

Querying List Status

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

le_sls_IsEmpty() - Checks if a given list is empty or not.
le_sls_IsInList() - Checks if a specified link is in the list.
le_sls_IsHead() - Checks if a specified link is at the head of the list.
le_sls_IsTail() - Checks if a specified link is at the tail of the list.
le_sls_NumLinks() - Checks the number of links currently in the list.
le_sls_IsListCorrupted() - Checks if the list is corrupted.

Queues and Stacks

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

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

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

Thread Safety and Re-Entrancy

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

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