Linked List: Zero to Hero Guide

Introduction

A linked list is a data structure used to store a collection of elements (known as node), where each element is connected to the next element through a link i.e. pointer. Each node contains two parts: first part contains the data/values that is being stored & the second part contains a reference (i.e. address) to the next node which itself will contain these two parts. Unlike arrays, linked lists do not have a fixed size and can easily grow or shrink in size during runtime which makes linked list more flexible than an array.

Below are the commonly used terms in Linked List.

Node: The basic building block of a linked list. It has of two parts – data and an address of the next node.
Head: The first node in a linked list.
Tail: The last node in a linked list.
Pointer: A variable that stores the address of another node.
Null pointer: A pointer that does not point to any valid memory location i.e. NULL (0).
Traversal: The process of visiting each node in a linked list in any particular order.
Insert: An operation of adding a new element/node in the linked list.
Delete: An operation of removing an element/node from the linked list.

Now let us understand the Linked list with en example where we will using the above-mentioned terms.

#include <stdio.h>
#include <stdlib.h>

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

void insert(Node* head, int data) {
    // create a new node
    Node* newNode = (Node*) malloc(sizeof(Node));
    
    if(newNode == NULL) {
        printf("Unabe to alloc memory to new Node.\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;

    // traverse the list to find the last node
    Node* curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }

    // append the new node to the end of the list
    curr->next = newNode;
}

void delete(Node* head, int data) {
    // traverse the list to find the node to delete
    Node* curr = head->next;
    Node* prev = head;

    while (curr != NULL && curr->data != data) {
        prev = curr;
        curr = curr->next;
    }

    // if node to delete is found, remove it from the list
    if (curr != NULL) {
        prev->next = curr->next;
        free(curr);
        curr = NULL;
    }
}

void printList(Node* head) {
    Node* curr = head->next;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    // create an empty list
    Node* head = (Node*) malloc(sizeof(Node));
    if(head == NULL) {
        printf("Unabe to alloc memory to Head.\n");
        return;
    }

    head->next = NULL;

    // insert some nodes
    insert(head, 10);
    insert(head, 20);
    insert(head, 30);

    // print the list
    printf("List: ");
    printList(head);

    // delete a node and print the list again
    delete(head, 20);
    printf("List after deleting 20: ");
    printList(head);

    // free the memory allocated for the list
    Node* curr = head->next;
    while (curr != NULL) {
        Node* temp = curr->next;
        free(curr);
        curr = temp;
    }
    free(head);

    return 0;
}

In the above code we had defined a struct called Node, that have two members: an integer data value and a pointer to the next node in the list.

After that we have defined the functions to do the operations like insert, delete and printing the whole LL.

• insert(): This function takes a pointer to the head of the list and a data value as arguments. It creates a new node with the given data. In this function we traverses the linked list to find the last node. Once we find the last node then we are appending the new node to the end of the list.
• delete(): This function takes a pointer of the head of the list and a data value as arguments. Here we are traversing the list to find the node with the given data. Once we find the node then we are removing the node from the list, and frees its memory and reconnect the nodes if required.
• printList(): This function takes a pointer to the head of the list as an argument and prints the complete linked list.

Rest of the code is self-explanatory, and I would recommend you try to understand yourself.

Advantage and Disadvantages of Linked List

Comparision of Linked List and Array

The linked list can be implemented in various manner depending on the use cases. Let us discuss some of them in detail.

Single Linked List

A Single Linked List is a type of linked list where each node contains a single pointer to the next node in the list. This makes traversal through the list easy but makes operations like deletion from the end of the list more difficult.

Double Linked List

A Double Linked List is a type of linked list where each node has a pointer to both the next and previous nodes of the list. It has a head node that points to the first node in the list, and the last node points to null. This makes it easier to traverse the list in both directions and makes operations like deletion from the end of the list easier.

Circular linked list

A circular linked list is a type of linked list where the last node points back to the first node, forming a loop. It can be either singly or doubly linked. The advantage of a circular linked list is that it allows for efficient traversal and can be used to implement circular buffers.

Skip list

A skip list is a type of linked list that uses a hierarchy of linked lists to provide efficient search and insertion operations. It uses probabilistic balancing to keep the height of each list logarithmic with respect to the number of nodes in the list. The advantage of a skip list is that it provides efficient search and insertion operations in O(log n) time.

Self-organizing linked list

A self-organizing linked list is a type of linked list that rearranges its elements based on the frequency of their access. It can be either singly or doubly linked. The advantage of a self-organizing linked list is that it can improve the performance of frequently accessed elements.

Unrolled linked list

An unrolled linked list is a type of linked list that stores multiple elements in each node. It can be thought of as a hybrid of an array and a linked list. The advantage of an unrolled linked list is that it provides efficient access to elements in the list.

XOR linked list

An XOR linked list is a type of linked list that uses bitwise XOR to store the addresses of the next and previous nodes in a single pointer. This allows for efficient memory usage and traversal in both directions. The disadvantage of an XOR linked list is that it can be more difficult to implement and debug.

Hashed linked list

A hashed linked list is a type of linked list that uses a hash function to determine the index of each element in the list. This allows for efficient access to elements based on their key values. The disadvantage of a hashed linked list is that collisions can occur, which can lead to slower access times.

Sparse linked list

A sparse linked list is a type of linked list where nodes with a value of zero are not stored in memory. This can save memory in cases where many nodes have a value of zero. The disadvantage of a sparse linked list is that it can be more difficult to implement and can result in slower access times due to the need to skip over zero-value nodes during traversal.

Array-backed linked list

An array-backed linked list is a type of linked list that combines the advantages of arrays and linked lists. It is essentially an array of nodes, where each node has a pointer to the next node in the list. The main advantage of this structure is that it allows for constant time access to any element/node, as array indexing is a constant time operation.

References

• Linked list – Wikipedia

You might be interested in:

• Doubly Linked List
• Singly Linked List