Linked lists demystified

Linked lists have been a great source of interview questions. They are small, powerful and if you don’t fully understand the concepts, complicated. The interview coding solutions involving linked lists are quick and small. So, what are the typical questions on linked lists? Well, to start with, traverse, insert, delete and modify a linked list are pretty standard operations and are almost parts of a larger question. Other more complicated questions revolve around doubly linked lists, circular lists, trees, graphs and similar data structures. In this blog post, we will explore a small subset of simple linked list operations.

The basic data structure for a linked list involves 2 components: the data itself and the link to the next element. Together (data + link) this structure is typically called a Node. There are generally 2 pointers involved: a head pointer, pointing to the start of the list; and a tail pointer, pointing to the last element of the list. The key property of the last node is that it’s next pointer points to nothing (NULL).

Graphically, a linked list can be represented as a series of nodes as shown below:

In the above diagram, the node consists of an int (data) value and a pointer to the next node. The complete list contains 4 elements (2, 4, 6 and 8).

 

How to represent a linked list node?

The easiest representation of a linked list node is wrapping the data and the link in a struct and giving the (typedef’ing) the struct as a Node pointer. An example representation is

 

typedef struct linked_list
{
    int data;
    struct linked_list *next;
} Node;

How do you traverse a linked list?

Before we can do any operations on a linked list, it is best to understand how to traverse a linked list. This involves starting at the first node (using the head pointer), printing the node data, and then using the next pointer to move along the list till we reach the last node (i.e. the next pointer’s value is NULL).

 

void PrintLinkedList(Node *start)
{
    printf("\nHEAD ->");
    while (start != NULL)
    {
        printf("%d ->", start->data);
        start = start->next;
    }
    printf("NULL\n\n");
}

How to insert a node at the beginning of the list?

Inserting a node at the beginning of the list is probably the easiest of all operations. Let’s talk about what is involved here referring to the diagram above. This involves creating a new node (with the new data, say int 10), making its link point to the current first node pointed to by head (data value 2) and lasting changing head to point to this new node. Simple, right?

Node *head;
void InsertNodeInLinkedListAtFront(int data)
{
    // assumption: head is already defined elsewhere in the program
    // 1. create the new node
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL; // this line is not really needed

    // 2. insert it at the first position
    temp->next = head;

    // 3. update the head to point to this new node
    head = temp;
}

How to insert a node at the end of the list?

This case is a little bit more evolved. If you have a tail pointer, it is as easy as inserting at the beginning of the list. If you do not have a tail pointer, you will have to create the new node, traverse the list till you reach the end (i.e. the next pointer is NULL) and then make that last node’s next pointer point to the new node.

void InsertNodeInLinkedListAtEnd(int data)
{
    // assumption: head is already defined elsewhere in the program
    // 1. create the new node
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL; 

    // check if the list is empty
    if (head == NULL)
    {
        head = temp;
        return;
    }
    else
    {
        // 2. traverse the list till the end
        Node *traveller = head;
        while (traveller->next != NULL)
            traveller = traveller->next;

        // 3. update the last node to point to this new node
        traveller->next = temp;
    }
}

How to insert a node in a random location in a list?

This is the case when you would like to insert a node into the linked list at a given position. As above, you would first create the new node. Now if the position is 1 or the list is empty, you would insert it at first position. Otherwise, you would traverse the list till either you reach the desired position or the list ends. Then you would insert this new node. Inserting in the middle is the tricky case as you have to make sure you do the pointer assignment in the correct order. First, you would set the new nodes next pointer to the node before which the new node is being inserted. Then you would set the node pointing to the position to point to the new node. Review the code below to get more clarification.

void InsertNodeInLinkedList(int data, int position)
{
    // assumption: head is already defined elsewhere in the program
    // 1. create the new node
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL; 

    // check if the position to insert is first or the list is empty
    if ((position == 1) || (head == NULL))
    {
        // set the new node to point to head 
        // as the list may not be empty
        temp->next = head;
        // point head to the first node now
        head = temp;
        return;
    }
    else
    {
        // 2. traverse to the desired position
        // or till the list ends; whichever comes first
        Node *t = head;
        // remember, we already covered the 1st case
        int currPos = 2; 

        while ((currPos < position) && (t->next != NULL))
        {
            t = t->next;
            currPos++;
        }

        // 3. now we are at the desired location
        // 3.a. first set the pointer for the new node
        temp->next = t->next;
        // 3.b. now set the previous node pointer
        t->next = temp;
    }
}

How to delete a node at a specific location?

Deleting a node requires you to pay careful attention to the next pointers. If you do not sequence your operations correctly, you will land up with orphaned lists.Review the function below carefully.

// delete node from the list at the specified 
// position. return a 0 if deletion fails
// assumption: head is defined elsewhere
int DeleteNodeFromLinkedList(int position)
{
    // if the list is empty, return 0
    if (head == NULL)
        return 0;

    // special case: deleting first element
    if (position == 1)
    {
        // set the head to point to the node 
        // that head is pointing to
        head = head->next;
    }
    else
    {
        // deleting at any other position
        // traverse to the desired position
        // or till the list ends; whichever comes first
        Node *t = head;
        // remember, we already covered the 1st case
        int currPos = 2; 

        while ((currPos < position) && (t->next != NULL))
        {
            t = t->next;
            currPos++;
        }

        // now comes the tricky part
        // you have to point the current node to its next node
        if (t->next != NULL)
            t->next = t->next->next; // NOTE THIS
        else
            return 0; // could not find the correct node
    }
    // deletion successful
    return 1;
}

In this lesson, we covered a lot of ground. We first looked at the basics of a linked list, review the data structure followed by inserting elements in a linked list at various points. Finally we reviewed how to delete elements from a linked list. Please feel free to post a comment if you would like me to discuss any other operations.