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.

Linked List
Linked List

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

AdvantagesDisadvantages
Dynamically resizableRequires extra memory for pointers
Efficient insertion and deletion of nodesNot cache-friendly
No need to know the size of the list beforehandRandom access is slower compared to arrays
Easy to implement and modifyTraversal requires iteration through the list
Useful in implementing abstract data types such as stacks, queues, and hash tablesNot suitable for applications requiring constant time insertion and deletion at arbitrary positions

Comparision of Linked List and Array

Linked ListArray
Dynamic size: can easily add or remove elementsStatic size: must be declared with a fixed size
No need to shift elements when adding or removing an elementNeed to shift elements when adding or removing an element
Good for inserting or deleting elements in the middle of the listNot efficient for inserting or deleting elements in the middle of the array
Requires extra memory for the pointer/reference in each nodeMore memory efficient since it only needs to store the data itself
No need to know the maximum size of the list beforehandNeed to know the maximum size of the array beforehand
Accessing elements is slower since it needs to follow pointersAccessing elements is faster since it uses direct indexing

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

You might be interested in:

2 thoughts on “Linked List: Zero to Hero Guide”
  1. […] A singly linked list is a type of linked list data structure which is used to store a collection of elements or items. It consists of a sequence of nodes where each node contains two parts: first part consists of the values need to be stored, and second part is a pointer that points to the next node in the list. In other words we can say that the singly linked list is the simplest form of a Linked List. […]

Leave a Reply

Your email address will not be published. Required fields are marked *