Singly Linked List data structure

Major drawback while inserting, deleting into arrays is to shift all elements right side when insert or delete element to satisfy arrays continuous memory policy. Linked List data structure came up with random memory linking of nodes to overcome the above shifting problem. These nodes can be linked/chained to the next node memory location, the next node links to another until the end of the linked list.

What is Node?

Node is an Object with two basic parts init, those are 1. Data Part and 2. Next nodes address part. Check below the graphical representation of the Node.

Node with integer “10”
// Code to represent a Node
struct Node
{
    // Any data part
    int data;
    // Points to next node
    struct Node *next;
};

In the above node integer “10” is the data part of the node. The next pointer will point to the address of the next node. By now you might get some basic picture about it. Yes many of these types of nodes link together to form a linked list.

Linked list with Head Node 10. List ends with NULL pointer.

Above is the visual representation of the Singly Linked list. Here list contains values { 10, 20, 15, 5 }. Basic operations of any data structure are Insert, Delete, and Find. These operations will be explained in detail below.

Insert

For insertion our use case is to insert a Node with data “9” at the 2nd position of the linked list. For this we need to start a temporary current node initially assigned to head, then move it to 2 positions next to it. Now create a new node with data “9” pointing its next to currents next initially. Check below the step1 diagram in the insertion process.

Create new node assign its next to currents next node.

In the second step de-couple list and assign current’s next node as the new node as shown in the below diagram.

Now, new list created with 9 inserted in 2nd position.

Above is the list after inserting “9” at the second position is { 10, 20, 9, 15, 5 }. Let’s jump into the code part of this illustration.

// Consider node structure here as defined earlier code part.
struct Node* createNode(int value)
{
    struct Node *tmp = (struct Node*)malloc(sizeof(struct Node));
    tmp->data = value;
    tmp->next = NULL;
    return tmp;
}
struct Node* insert(struct Node* head, int value, int pos)
{
    if(head == NULL) return NULL;
    int curr_pos = 0;
    struct Node *current_node = head;
    struct Node *newNode = createNode(value);
    if(pos == 0)
    {
        newNode->next = head;
        return newNode;
    }
    while(current_node->next != NULL)
    {
        curr_pos++;
        current_node = current_node->next;
        if(curr_pos == (pos - 1))
            break;
    }
    newNode->next = current_node->next;
    current_node->next = newNode;
    return head;
}

Complexity of insert is also O(n). By using Linked list here we are reducing swaps that happen with arrays.

Delete

Let’s take the above used linked list. For deletion our use case is to delete node “9” from the linked list. Pictorial representation is as shown below.

Find the node to delete and de-link from the linked list.
Assign delNode next to NULL, and free memory of delNode.

Above is the final linked list after deleting node “9”. The code to delete a node from the linked list is as shown below.

struct Node *delete(struct Node *head, int value)
{
    if(head == NULL) return NULL;
    struct Node *current = head;
    struct Node *delNode = head;
    if(head->data == value)
    {
        head = head->next;
        current->next = NULL;
        free(current);
        return head;
    }
    while(current->next != NULL && current->next->data != value)
    {
        current = current->next;
    }
    if(current->next != NULL)
    {
        delNode = current->next;
        current->next = delNode->next;
        delNode->next = NULL;
        free(delNode);
    }
    return head;
}

Complexity to delete a node from linked list is O(n).

Find

We already did find operation in the above insert & delete operations. It is as similar as in arrays. Just need to traverse one node by one until you find the given value. The code is as shown below.

struct Node *find(struct Node *head, int value)
{
    if(head == NULL) return NULL;
    struct Node *current = head;

    while(current->next != NULL)
    {
        if(current->data == value)
            return current;
        current = current->next;
    }
    return NULL;
}

That’s it for the Linked List. If you find any errors or additional operations on this post, please help readers know by commenting below. Cheers!.