Linked Lists Data Structures

Linked Lists Mastery

Master dynamic data structures that form the foundation of advanced algorithms. Learn singly, doubly, and circular linked lists with practical implementations and real-world applications.

Linked List Implementation in Python

# Node class for Singly Linked List
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Singly Linked List Implementation
class LinkedList:
    def __init__(self):
        self.head = None
    
    # Insert at beginning
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    # Insert at end
    def insert_at_end(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
    
    # Delete node by value
    def delete_node(self, key):
        current = self.head
        
        # If head node holds the key
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        
        # Search for the key
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        
        # Key not found
        if not current:
            return
        
        # Unlink the node
        prev.next = current.next
        current = None
    
    # Reverse the linked list
    def reverse(self):
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev
    
    # Detect loop using Floyd's algorithm
    def has_cycle(self):
        slow = self.head
        fast = self.head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
    
    # Traversal
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

1. Singly Linked List

Introduction & Node Structure
Memory Representation & Pointers
Insertion: Beginning, End, Position
Deletion: Beginning, End, Position
Traversal & Searching Algorithms
Reversing a Linked List (Iterative)
Reversing a Linked List (Recursive)
Detecting Loop – Floyd’s Algorithm
Finding Middle Element
Merge Two Sorted Lists

2. Doubly Linked List

Node Structure with Prev & Next Pointers
Advantages over Singly Linked List
Memory Considerations
Insertion: Beginning, End, Position
Deletion: Beginning, End, Position
Forward & Backward Traversal
Reversing a Doubly Linked List
Implementation with Head & Tail
Time Complexity Analysis
Real-World Applications

3. Circular Linked List

Circular Node Structure
Singly vs Doubly Circular Lists
Insertion: Beginning, End
Deletion: Beginning, End
Traversal in Circular List
Detecting Circular Lists
Josephus Problem Solution
Advantages & Use Cases
Implementation Considerations
Real-World Applications

Dynamic Memory

Learn efficient memory utilization with linked structures

Algorithm Mastery

Master essential algorithms like Floyd’s cycle detection

Real Implementations

Practical code in Python, Java, and C++

Complexity Analysis

Understand time and space complexity for all operations

Linked List Visualization

Singly Linked List

Head
↓
10→ 20→ 30→ 40→ NULL

Each node points to the next node. Last node points to NULL.

Doubly Linked List

NULL
⇆
10⇆ 20⇆ 30⇆ 40
⇆
NULL

Each node has pointers to both next and previous nodes.

Circular Linked List

Head
↓
10→ 20→ 30→ 40
↑←←←←←←←←←↓

Last node points back to the first node, forming a circle.

Implementation Examples

Doubly Linked List in Java

// Doubly Linked List Node in Java
class DNode {
    int data;
    DNode prev;
    DNode next;
    
    DNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    DNode head;
    
    // Insert at beginning
    void insertAtBeginning(int data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
    
    // Insert at end
    void insertAtEnd(int data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        DNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.prev = current;
    }
    
    // Forward traversal
    void printForward() {
        DNode current = head;
        while (current != null) {
            System.out.print(current.data + " ⇆ ");
            current = current.next;
        }
        System.out.println("NULL");
    }
    
    // Backward traversal
    void printBackward() {
        if (head == null) return;
        
        DNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        
        while (current != null) {
            System.out.print(current.data + " ⇆ ");
            current = current.prev;
        }
        System.out.println("NULL");
    }
    
    // Delete node by value
    void deleteNode(int key) {
        if (head == null) return;
        
        DNode current = head;
        
        // Find the node to delete
        while (current != null && current.data != key) {
            current = current.next;
        }
        
        if (current == null) return;
        
        // Adjust pointers
        if (current.prev != null) {
            current.prev.next = current.next;
        } else {
            head = current.next;
        }
        
        if (current.next != null) {
            current.next.prev = current.prev;
        }
    }
}

Circular Linked List in C++

// Circular Linked List in C++
#include 
using namespace std;

class CNode {
public:
    int data;
    CNode* next;
    
    CNode(int val) {
        data = val;
        next = nullptr;
    }
};

class CircularLinkedList {
private:
    CNode* head;
    
public:
    CircularLinkedList() {
        head = nullptr;
    }
    
    // Insert at beginning
    void insertAtBeginning(int data) {
        CNode* newNode = new CNode(data);
        
        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
            return;
        }
        
        CNode* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        
        temp->next = newNode;
        newNode->next = head;
        head = newNode;
    }
    
    // Insert at end
    void insertAtEnd(int data) {
        CNode* newNode = new CNode(data);
        
        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
            return;
        }
        
        CNode* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        
        temp->next = newNode;
        newNode->next = head;
    }
    
    // Delete from beginning
    void deleteFromBeginning() {
        if (head == nullptr) return;
        
        if (head->next == head) {
            delete head;
            head = nullptr;
            return;
        }
        
        CNode* temp = head;
        CNode* last = head;
        
        while (last->next != head) {
            last = last->next;
        }
        
        head = head->next;
        last->next = head;
        delete temp;
    }
    
    // Traverse circular list
    void traverse() {
        if (head == nullptr) {
            cout << "List is empty" << endl;
            return;
        }
        
        CNode* temp = head;
        do {
            cout << temp->data << " → ";
            temp = temp->next;
        } while (temp != head);
        
        cout << "(back to head)" << endl;
    }
    
    // Check if list is circular
    bool isCircular() {
        if (head == nullptr) return true;
        
        CNode* slow = head;
        CNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};

Key Linked List Algorithms

Floyd’s Cycle Detection

Also known as the “tortoise and hare” algorithm. Uses two pointers moving at different speeds to detect cycles in O(n) time with O(1) space.

List Reversal (Iterative)

Reverses a linked list in-place using three pointers. Time complexity: O(n), Space complexity: O(1).

List Reversal (Recursive)

Recursive approach to reverse a linked list. Elegant but uses O(n) stack space for recursion depth.

Middle Element Finder

Uses two pointers (slow and fast) to find the middle element in a single traversal without knowing the length.

Merge Two Sorted Lists

Merges two sorted linked lists into one sorted list. Used as a subroutine in merge sort for linked lists.

Josephus Problem

Classic problem efficiently solved using circular linked lists. Eliminates every k-th person until one remains.

Master Linked Lists Today

Join thousands of developers who have strengthened their data structure skills with comprehensive linked list training. Essential for coding interviews and advanced algorithm design.

Start Learning Linked Lists Now