Understanding Linked Lists: Types, Operations, and Real-Life Uses

Baibhav Kumar
1d
367
0
1

Article

Introduction

In the world of Data Structures, a Linked List is one of the most fundamental and widely used structures. It provides a flexible way to store and manage data, especially when the number of elements isn’t fixed or when inserting and deleting elements frequently.

Unlike an Array, which stores elements in contiguous memory locations, a Linked List stores elements at different memory locations, connected through links (or pointers). This design makes linked lists more dynamic but also slightly more complex to understand and manage.

What is a Linked List?

A Linked List is a linear data structure where each element, called a node, contains two parts:

Data – The actual value or information to store.
Pointer (Link) – The address (or reference) of the next node in the list.

Together, these nodes form a chain, where each node points to the next.

Example

[10 | next] → [20 | next] → [30 | next] → None

Here, each box (node) holds a value and a pointer to the next node. The last node points to None, which marks the end of the list.

Key Features of Linked Lists

Feature	Description
Dynamic Size	The size of a linked list can grow or shrink as needed, unlike arrays which have a fixed size.
Non-Contiguous Memory	Elements are stored in scattered memory locations.
Efficient Insertions/Deletions	Adding or removing elements does not require shifting data like arrays do.
Sequential Access	Elements can only be accessed sequentially (no direct access by index).
Uses Pointers	Each node contains a pointer/reference to the next node.

Structure of a Node (in Python)

Here’s how a node can be defined in Python using a simple class:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # Pointer to the next node

And a linked list itself can be represented as:

class LinkedList:
    def __init__(self):
        self.head = None  # Start of the linked list

Types of Linked Lists

There are several types of linked lists, each with its own use cases and behavior.

1. Singly Linked List

This is the simplest type, each node points only to the next node. Traversal is possible only in one direction (from head to tail).

Structure Example:

[10 | *] → [20 | *] → [30 | None]

Python Example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node

    def display(self):
        temp = self.head
        while temp:
            print(temp.data, end=" → ")
            temp = temp.next
        print("None")

# Example usage
lst = SinglyLinkedList()
lst.append(10)
lst.append(20)
lst.append(30)
lst.display()

Output:

10 → 20 → 30 → None

2. Doubly Linked List

In this type, each node contains two pointers, one pointing to the next node and another to the previous node.

This allows two-way traversal (forward and backward).

Structure Example:

None ← [10 | * | *] ↔ [20 | * | *] ↔ [30 | * | None]

Python Example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node
        new_node.prev = temp

    def display_forward(self):
        temp = self.head
        while temp:
            print(temp.data, end=" ↔ ")
            temp = temp.next
        print("None")

3. Circular Linked List

In this type, the last node points back to the first node, forming a circle.
This allows traversal to continue indefinitely unless explicitly stopped.

Structure Example:

[10 | *] → [20 | *] → [30 | *] ↺ (back to 10)

Python Example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def display(self):
        temp = self.head
        if not temp:
            return
        while True:
            print(temp.data, end=" → ")
            temp = temp.next
            if temp == self.head:
                break
        print("(back to head)")

Common Operations on Linked Lists

Operation	Description	Time Complexity
Traversal	Visit each node in the list	O(n)
Insertion at Beginning	Add a new node at the start	O(1)
Insertion at End	Add a new node at the end	O(n)
Insertion After a Node	Insert after a specific node	O(1)
Deletion	Remove a node	O(n)
Search	Find a node with specific data	O(n)

Example: Inserting at Beginning

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

Example: Deleting a Node

def delete(self, key):
    temp = self.head
    if temp and temp.data == key:
        self.head = temp.next
        return
    prev = None
    while temp and temp.data != key:
        prev = temp
        temp = temp.next
    if temp is None:
        return
    prev.next = temp.next

Advantages of Linked Lists

Dynamic Size – Can grow or shrink at runtime without memory wastage.
Efficient Insertions/Deletions – No need to shift elements like in arrays.
No Predefined Memory Requirement – Memory is allocated as needed.

Disadvantages of Linked Lists

No Random Access – Must traverse nodes one by one.
Extra Memory – Each node needs a pointer/reference field.
Slower Access Time – Takes longer to find an element compared to arrays.
Complex Implementation – Managing pointers requires careful handling.

Real-Life Applications of Linked Lists

Undo/Redo Operations in text editors (Doubly Linked List).
Image Viewer navigation (Next and Previous).
Music Playlists where songs are linked (Circular Linked List).
Browser History (Doubly Linked List – forward and backward navigation).
Memory Management in operating systems.
Implementation of Stacks, Queues, and Hash Tables.

Array vs Linked List

Feature	Array	Linked List
Memory Allocation	Contiguous	Non-contiguous
Size	Fixed	Dynamic
Access Time	O(1)	O(n)
Insertion/Deletion	Expensive (O(n))	Efficient (O(1) for beginning)
Extra Memory	None	Required for pointers
Cache Performance	Better	Poorer

Summary

A Linked List is a linear data structure made up of nodes, each containing data and a pointer to the next node.
It’s dynamic, efficient for insertions/deletions**, but slower for random access.
There are different types: Singly, Doubly, and Circular Linked Lists.
Common uses include browser history, playlist navigation, and undo-redo systems.
Understanding linked lists is essential for mastering data structures, as many advanced structures (like stacks, queues, graphs) are built using them.