Linked List

Description

A Linked List is a linear data structure in which elements, called nodes, are linked using pointers. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each node contains two components: data and a pointer (or reference) to the next node in the sequence. This design allows for efficient insertions and deletions, especially when compared to arrays.

Linked lists are foundational structures in computer science, forming the basis for more complex data types such as stacks, queues, and graphs.

Types of Linked Lists

1. Singly Linked List

Each node has:

• data: stores the value.
• next: a reference to the next node.

[ data | next ] → [ data | next ] → [ data | null ]

2. Doubly Linked List

Each node has:

• data
• prev: reference to the previous node
• next: reference to the next node

null ← [ prev | data | next ] ↔ [ prev | data | next ] ↔ [ prev | data | null ]

3. Circular Linked List

Similar to singly or doubly linked lists, but the last node points back to the first node, forming a circle.

[ data | next ] → ... → [ data | next ] ─┐
                     ↑__________________|

Basic Operations

Insertion

• At beginning: Create a new node and point it to the current head.
• At end: Traverse to the last node and point it to the new node.
• At specific position: Traverse, then insert.

Deletion

• From beginning: Change the head pointer to the second node.
• From end: Traverse to the second last and set its next to null.
• From middle: Adjust the next of the previous node to skip the deleted node.

Traversal

Loop through the list using the next pointer until you reach a null reference.

Search

Iterate over nodes to match a target value.

Advantages

• Dynamic size: Grows or shrinks at runtime.
• Efficient insertions/deletions: Especially in the middle of the list.
• Memory efficient for certain operations.

Disadvantages

• Extra memory: Requires pointer storage.
• Linear time access: Cannot access random elements efficiently (unlike arrays).
• Poor cache locality: Due to non-contiguous memory.

Time Complexity

Applications

• Implementing stacks and queues
• Memory management
• Polynomial arithmetic
• Adjacency list in graph algorithms

Implementation Examples

Python

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

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

    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

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

C

#include 
#include 

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

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

Real-World Example

Music Playlist

Each song in a playlist is a node. You can go to the next song or go back (if it’s a doubly linked list).

Browser History

Navigating forward and backward through visited web pages mimics a doubly linked list.

Visual Representation

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

Doubly linked list:

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

Summary

A Linked List is a flexible and powerful data structure ideal for dynamic memory allocation. Its structure allows for efficient insertions and deletions but trades off random access speed. From simple one-directional lists to complex bidirectional and circular forms, linked lists underpin many core algorithms and systems across computing disciplines.