Linked List in Data Structures and Algorithms

Data Structures and Algorithms

A linked list is a linear data structure where elements are stored in separate objects called nodes, and each node holds a reference to the next one. Unlike arrays, the nodes are not stored side by side in memory.

• Data is stored in nodes, not in one continuous block
• Each node knows the address of the next node
• Size grows and shrinks at runtime, no resizing cost
• Insertion and deletion are cheap, random access is not

This tutorial covers the structure of a node, all three types of linked lists, time complexity, working code in Java and Python, common mistakes, and interview questions.

Why Linked Lists Matter

• Foundation for stacks, queues, graphs, and hash table chaining
• Used internally by LinkedList and LinkedHashMap in Java
• Powers undo history, music playlists, browser back and forward buttons
• One of the most asked topics in coding interviews and university exams

Structure of a Node

Every linked list is built from a single repeating unit:

• Data – the actual value stored
• Next – reference to the following node
• Prev – reference to the previous node (doubly linked list only)

[ data | next ] -> [ data | next ] -> [ data | next ] -> null
     head                                        tail

The head pointer is the entry point. Lose the head and you lose the entire list.

Array vs Linked List

Feature	Array	Linked List
Memory layout	Contiguous	Scattered
Access by index	O(1)	O(n)
Insert or delete at start	O(n)	O(1)
Insert or delete at end	O(1) amortized	O(n) without tail pointer
Size	Fixed or resized by copying	Dynamic
Extra memory	None	One or two pointers per node
Cache performance	Good	Poor

Types of Linked Lists

1. Singly Linked List

• Each node points only to the next node
• Traversal is one directional, head to tail
• Last node points to null
• Lowest memory overhead of the three
• Limitation: you cannot move backward, so deleting a node needs its previous node

10 -> 20 -> 30 -> null

2. Doubly Linked List

• Each node stores both next and prev
• Traversal works in both directions
• Deletion of a known node is O(1), no need to track the previous node
• Costs one extra pointer per node
• Used in LRU cache, text editors, and browser history

null <- 10 <-> 20 <-> 30 -> null

3. Circular Linked List

• Last node points back to the head instead of null
• Can be singly or doubly circular
• Traversal never ends naturally, you must stop when you reach the head again
• Used in round robin CPU scheduling, multiplayer turn systems, looping playlists

10 -> 20 -> 30 --+
^                |
+----------------+

AI Study Timetable Generator Project

Time Complexity Reference

Operation	Singly	Doubly	Circular
Access by position	O(n)	O(n)	O(n)
Search	O(n)	O(n)	O(n)
Insert at head	O(1)	O(1)	O(1) with tail pointer
Insert at tail	O(n)	O(1) with tail pointer	O(1) with tail pointer
Delete a known node	O(n)	O(1)	O(n)
Space per node	1 pointer	2 pointers	1 or 2 pointers

Core Operations Explained

Insertion at the beginning

• Create the new node
• Point its next to the current head
• Move head to the new node

Insertion at the end

• Walk to the last node using a temporary pointer
• Set that node’s next to the new node
• If the list is empty, the new node becomes the head

Deletion

• Find the node just before the target
• Set prev.next = target.next so the target is skipped
• In a doubly linked list, also fix target.next.prev

Traversal

• Start at head
• Process the current node, then move to current.next
• Stop at null, or at the head again for circular lists

Java Implementation

YT:- DecodeIT

Singly Linked List in Java

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SinglyLinkedList {
    Node head;

    // Insert at end
    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Insert at beginning
    void prepend(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Delete first node with given value
    void delete(int key) {
        if (head == null) return;
        if (head.data == key) {
            head = head.next;
            return;
        }
        Node current = head;
        while (current.next != null && current.next.data != key) {
            current = current.next;
        }
        if (current.next != null) {
            current.next = current.next.next;
        }
    }

    void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.prepend(5);
        list.delete(20);
        list.display();   // 5 -> 10 -> 30 -> null
    }
}

Doubly Linked List in Java

class DNode {
    int data;
    DNode next, prev;

    DNode(int data) {
        this.data = data;
    }
}

public class DoublyLinkedList {
    DNode head, tail;

    void append(int data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    void displayForward() {
        DNode current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    void displayBackward() {
        DNode current = tail;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.prev;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.displayForward();    // 10 <-> 20 <-> 30 <-> null
        list.displayBackward();   // 30 <-> 20 <-> 10 <-> null
    }
}

Circular Linked List in Java

public class CircularLinkedList {
    Node head, tail;

    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            newNode.next = head;
            return;
        }
        tail.next = newNode;
        newNode.next = head;
        tail = newNode;
    }

    void display() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node current = head;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != head);
        System.out.println("(back to head)");
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.display();   // 10 -> 20 -> 30 -> (back to head)
    }
}

Python Implementation

Singly Linked List in Python

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
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

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

    def delete(self, key):
        if not self.head:
            return
        if self.head.data == key:
            self.head = self.head.next
            return
        current = self.head
        while current.next and current.next.data != key:
            current = current.next
        if current.next:
            current.next = current.next.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")


sll = SinglyLinkedList()
sll.append(10)
sll.append(20)
sll.append(30)
sll.prepend(5)
sll.delete(20)
sll.display()      # 5 -> 10 -> 30 -> None

Doubly Linked List in Python

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


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

    def append(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def display_forward(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    def display_backward(self):
        current = self.tail
        while current:
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")


dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.display_forward()     # 10 <-> 20 <-> 30 <-> None
dll.display_backward()    # 30 <-> 20 <-> 10 <-> None

Circular Linked List in Python

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

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

    def display(self):
        if not self.head:
            print("List is empty")
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(back to head)")


cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
cll.display()      # 10 -> 20 -> 30 -> (back to head)

Classic Linked List Problems

• Reverse a linked list – iterative with three pointers, prev, current, next
• Detect a loop – Floyd’s cycle detection, slow pointer moves one step, fast moves two
• Find the middle node – slow and fast pointer, slow lands on the middle
• Nth node from the end – two pointers with a gap of n
• Merge two sorted lists – compare heads and link the smaller one
• Remove duplicates – single pass for a sorted list, hash set for unsorted

Reverse a Singly Linked List

Node reverse(Node head) {
    Node prev = null;
    Node current = head;
    while (current != null) {
        Node next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Detect a Loop

boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Common Mistakes to Avoid

• Losing the head reference during traversal, always use a temporary pointer
• Forgetting the empty list case where head == null
• Updating next before saving the reference you still need
• Updating only next and not prev in a doubly linked list
• Writing a while (current != null) loop on a circular list, it never ends
• Using a linked list where an array or ArrayList would be faster

When to Use a Linked List

• Use it when insertions and deletions are frequent, especially at the front
• Use it when the size is unpredictable and resizing an array is costly
• Use it when you are implementing a stack, queue, or hash table with chaining
• Avoid it when you need fast index based access
• Avoid it when memory is tight, pointers add real overhead
• Avoid it when you scan the data repeatedly, arrays win on cache locality

Interview Questions on Linked Lists

• What is the difference between an array and a linked list?
• Why is insertion at the head O(1) but at the tail O(n)?
• How do you detect and remove a loop in a linked list?
• How do you find the middle node in a single pass?
• When is a doubly linked list better than a singly linked list?
• How does Java’s LinkedList class store its elements internally?
• How would you reverse a linked list in groups of k nodes?

Frequently Asked Questions

Is a linked list faster than an array?

Only for insertion and deletion at known positions. For reading and scanning, arrays are faster because their elements sit next to each other in memory.

Can a linked list store different data types?

Yes. In Python a node can hold any object. In Java you would use generics, for example Node<T>.

Why does Java’s LinkedList perform poorly in practice?

It is a doubly linked list, so every element carries two extra references and the nodes are scattered in memory. For most workloads ArrayList is the better default.

What happens if the head becomes null?

The entire list becomes unreachable and is garbage collected. Always keep a valid head reference.

Which type should a beginner learn first?

Start with the singly linked list. Once insertion, deletion, traversal, and reversal feel natural, move to doubly and circular lists.

Summary

• A linked list stores data in nodes connected by references
• Singly linked list moves forward only, lowest memory cost
• Doubly linked list moves both ways, O(1) deletion of a known node
• Circular linked list loops back to the head, ideal for round robin logic
• Insertion and deletion are cheap, indexed access is O(n)
• Master reversal, cycle detection, and the two pointer technique for interviews

Practice by implementing each type from scratch without looking at the code, then solve the classic problems listed above. That combination covers almost every linked list question asked in university exams and technical interviews.

data structures and algorithms course
data structures and algorithms book
data structures and algorithms pdf
data structures and algorithms by narasimha karumanchi
data structures and algorithms c++
data structures and algorithms using python
data structures and algorithms pdf notes
data structures and algorithms in java
linked list in data structures and algorithms w3schools
linked list in data structures and algorithms python
linked list in data structures and algorithms in c++
linked list in data structures and algorithms example
linked list in data structures and algorithms geeksforgeek
linked list in c
linked list algorithm
type of linked list in data structure