Linked Lists

Linked Lists

A linked List is a container where data is stored in nodes consisting of a single data item and a reference to the next node.

The concept of linking together simple nodes into a complex structure is the basis of many types of data structures. In fact linked lists can be used as the underlying implementation of other very useful structures, such a stacks and queues.

You can think of a linked list as a chain. Each link in the chain contains a single piece of data, and like a chain, each link is connected to the ones immediately adjacent to it. This means you can get from any link in the list to any other link by starting at the beginning and then moving your way through all the links to the end of the list.
You should note that, there is no a shortcut. You can't jump from the first link to the fifth link without going through the second, third, and fourth link in the chain.

The Node

Each link in the chain is called a node, and a node contains two things:

1. Value: the thing being stored in the container
2. Reference: refers to the next item in the list

Types of inked Lists

There are four types of linked lists

1. Singly Linked Lists
2. Doubly Linked Lists
3. Circular Linked Lists
4. Circular Doubly Linked Lists

Singly Linked List

A linked List that provides forward iteration from the start to the end of the list.

Doubly Linked List

A linked list that provides forward iteration from the start to the end of the list, and reverse iteration from the end to start.

The doubly linked list is just like as a singly linked list, except it also contains a reference to the previous node.

Circular Linked List

Similar to singly linked list but the last node is pointing to the head node. So while traversing, you need to be careful and stop traversing when you revisit the head node.

Circular Doubly Linked Lists

Like the doubly linked list, it has an extra pointer called the previous pointer, and similar to the circular linked list, its last node points at the head node. This type of linked list is the bi-directional list. So, you can traverse it in both directions.

Code Sample in C Language

Linked List Structure

// Self-referential structure
typedef struct LinkedList
{
    char NodeData;                    // Node Value
    struct LinkedList *NextPtr;     //de refernce

}ListNode;

typedef ListNode* ListNodePtr;

Insert into List Function

//Insert a new value into a linked ;ist in sorted order
void insert(ListNodePtr* headPtr, char NodeValue)
{/* Because the list itself is a pointer (to its first element),
 * passing its address creates a pointer to a pointer (double pointer) */

    //Create Node
    ListNodePtr newPtr = (ListNodePtr) malloc(sizeof(ListNode));

    // Check if space is available
    if(newPtr != NULL)
    {
        newPtr->NodeData = NodeValue;
        newPtr->NextPtr = NULL;

        // Two pointers to manage you place the node in the right location
        ListNodePtr previousPtr = NULL;
        ListNodePtr currentPtr = *headPtr;

        // Loop to find correct location in the list
        while((currentPtr != NULL) && (NodeValue > currentPtr->NodeData))
        {
            previousPtr = currentPtr;       //walk to ...
            currentPtr = currentPtr->NextPtr;//... next node
        }

        // Insert new node at the beginning of the list
        if(previousPtr == NULL)
        {
            newPtr->NextPtr = *headPtr;
            *headPtr = newPtr;
        }
        else
        {
            // Insert new node between previousPtr and currentPtr
            previousPtr->NextPtr = newPtr;
            newPtr->NextPtr = currentPtr;
        }
    }
    else
    {
        printf("%c not inserted. No memory available.\n", NodeValue);
    }
}

Delete from List Function

// Delete an element from the list
char delete(ListNodePtr* headPtr, char NodeValue)
{
    // Delete the first node if a match is found
    if(NodeValue == (*headPtr)->NodeData)
    {
        ListNodePtr tempPtr = *headPtr;     // hold onto node being removed
        *headPtr = (*headPtr)->NextPtr;     // de-thread the node
        free(tempPtr);      // free the de-threaded node
        return NodeValue;
    }
    else
    {
        ListNodePtr previousPtr = *headPtr;
        ListNodePtr currentPtr = (*headPtr)->NextPtr;

        // loop to find the correct location in the list
        while((currentPtr != NULL) && (currentPtr->NodeData != NodeValue))
        {
            previousPtr = currentPtr;       // walk to ...
            currentPtr = currentPtr->NextPtr; // ... next node
        }

        // delete node at currentPtr
        if(currentPtr != NULL)
        {
            ListNodePtr tempPtr = currentPtr;
            previousPtr->NextPtr = currentPtr->NextPtr;
            free(tempPtr);
            return NodeValue;
        }
    }

    return '\0';
}

Print List Function

// Print the list
void printList(ListNodePtr currentPtr)
{
    if(currentPtr == NULL)
    {
        puts("List is Empty.\n");
    }
    else
    {
        puts("The List is:");

        while(currentPtr != NULL)
        {
            printf("%c --> ", currentPtr->NodeData);
            currentPtr = currentPtr->NextPtr;
        }

        puts("NULL\n");
    }
}