Linked List

A linked list is a linear data structure where elements called nodes are connected through pointers. Unlike arrays, linked lists provide dynamic memory allocation and efficient insertion/deletion operations at the cost of sequential access requirements.

Interactive Linked List Visualization

Explore how nodes are connected through pointers and see the dynamic behavior of linked list operations. Watch as the head pointer updates and nodes are linked or unlinked during modifications.

Linked List Operations

Append (Add to End)

Add new node at the end

Prepend (Add to Start)

Add new node at the beginning

Delete (by Value)

Remove node by value

Linked List Visualization

List Length: 3

Values: 10 → 20 → 30 → null

How Linked List Operations Work:

Append (O(n)):

Traverse to the end of the list and update the last node's pointer to point to the new node.

Prepend (O(1)):

Create a new node, set its next pointer to the current head, then update head to point to the new node.

Delete (O(n)):

Traverse the list to find the target node, then update the previous node's pointer to skip the target node.

Understanding Linked Lists

Nodes

The building blocks of a linked list. Each node contains:

• Data: The actual value stored
• Next Pointer: Reference to the next node

Head Pointer

Critical reference that:

• Points to the first node in the list
• Provides entry point for all operations
• When null, indicates an empty list
• Must be updated during insertions/deletions

Tail Pointer (Optional)

Points to the last node:

• Optimizes append operations to O(1)
• Last node's next pointer is null
• Requires maintenance during modifications
• Trade-off: memory vs performance

Linked Lists vs Arrays

Aspect	Linked Lists	Arrays
Memory Layout	Non-contiguous, scattered	Contiguous block
Size	Dynamic (grows/shrinks)	Static (fixed at creation)
Access Time	O(n) sequential	O(1) random access
Insertion/Deletion	O(1) at known position	O(n) shifting required
Memory Overhead	Extra pointer storage	No extra overhead
Cache Performance	Poor (scattered memory)	Excellent (locality)

Complexity Analysis

Operation	Time Complexity	Space Complexity	Explanation
Access	O(n)	O(1)	Must traverse from head to target index
Search	O(n)	O(1)	Linear search through all nodes in worst case
Insertion (Head)	O(1)	O(1)	Direct insertion at beginning, update head pointer
Insertion (Tail)	O(n)	O(1)	Traverse to end unless tail pointer maintained
Deletion	O(n)	O(1)	Search for target, then update pointers

Node & LinkedList Class Implementation

Complete implementations showing Node class structure and LinkedList class with essential operations. Study how pointers are manipulated to maintain list integrity during append, prepend, and delete operations.

 # Node class definition
class Node:
    """
    A single node in a linked list
    Contains data and a reference to the next node
    """
    def __init__(self, data):
        self.data = data
        self.next = None
    
    def __str__(self):
        return f"Node({self.data})"

# LinkedList class definition
class LinkedList:
    """
    A singly linked list implementation
    Maintains a reference to the head node
    """
    def __init__(self):
        self.head = None
        self.size = 0
    
    def append(self, data):
        """
        Add a new node at the end of the list
        Time Complexity: O(n) - must traverse to end
        Space Complexity: O(1)
        """
        new_node = Node(data)
        
        # If list is empty, new node becomes head
        if not self.head:
            self.head = new_node
            self.size += 1
            return
        
        # Traverse to the end of the list
        current = self.head
        while current.next:
            current = current.next
        
        # Link the last node to the new node
        current.next = new_node
        self.size += 1
    
    def prepend(self, data):
        """
        Add a new node at the beginning of the list
        Time Complexity: O(1) - direct insertion
        Space Complexity: O(1)
        """
        new_node = Node(data)
        new_node.next = self.head  # Point new node to current head
        self.head = new_node       # Update head to new node
        self.size += 1
    
    def delete(self, data):
        """
        Delete the first occurrence of data from the list
        Time Complexity: O(n) - may need to traverse entire list
        Space Complexity: O(1)
        """
        if not self.head:
            return False
        
        # If head node contains the data to delete
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return True
        
        # Search for the node to delete
        current = self.head
        while current.next:
            if current.next.data == data:
                # Bypass the node to be deleted
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        
        return False  # Data not found
    
    def display(self):
        """Display the linked list as a string"""
        if not self.head:
            return "Empty list"
        
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        
        return " -> ".join(elements) + " -> None"
    
    def __len__(self):
        return self.size

# Example usage
if __name__ == "__main__":
    ll = LinkedList()
    
    # Test append
    ll.append(10)
    ll.append(20)
    ll.append(30)
    print("After appends:", ll.display())
    
    # Test prepend
    ll.prepend(5)
    print("After prepend:", ll.display())
    
    # Test delete
    ll.delete(20)
    print("After deleting 20:", ll.display())
    print("List size:", len(ll)) 
 // Node class definition
class Node {
    int data;
    Node next;
    
    /**
     * Constructor to create a new node
     * @param data The data to store in the node
     */
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
    
    @Override
    public String toString() {
        return "Node(" + data + ")";
    }
}

// LinkedList class definition
public class LinkedList {
    private Node head;
    private int size;
    
    /**
     * Constructor to create an empty linked list
     */
    public LinkedList() {
        this.head = null;
        this.size = 0;
    }
    
    /**
     * Add a new node at the end of the list
     * Time Complexity: O(n) - must traverse to end
     * Space Complexity: O(1)
     */
    public void append(int data) {
        Node newNode = new Node(data);
        
        // If list is empty, new node becomes head
        if (head == null) {
            head = newNode;
            size++;
            return;
        }
        
        // Traverse to the end of the list
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        
        // Link the last node to the new node
        current.next = newNode;
        size++;
    }
    
    /**
     * Add a new node at the beginning of the list
     * Time Complexity: O(1) - direct insertion
     * Space Complexity: O(1)
     */
    public void prepend(int data) {
        Node newNode = new Node(data);
        newNode.next = head;  // Point new node to current head
        head = newNode;       // Update head to new node
        size++;
    }
    
    /**
     * Delete the first occurrence of data from the list
     * Time Complexity: O(n) - may need to traverse entire list
     * Space Complexity: O(1)
     */
    public boolean delete(int data) {
        if (head == null) {
            return false;
        }
        
        // If head node contains the data to delete
        if (head.data == data) {
            head = head.next;
            size--;
            return true;
        }
        
        // Search for the node to delete
        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                // Bypass the node to be deleted
                current.next = current.next.next;
                size--;
                return true;
            }
            current = current.next;
        }
        
        return false;  // Data not found
    }
    
    /**
     * Display the linked list as a string
     */
    public String display() {
        if (head == null) {
            return "Empty list";
        }
        
        StringBuilder sb = new StringBuilder();
        Node current = head;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(" -> ");
            }
            current = current.next;
        }
        sb.append(" -> null");
        
        return sb.toString();
    }
    
    /**
     * Get the size of the linked list
     */
    public int size() {
        return size;
    }
    
    // Example usage
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        
        // Test append
        ll.append(10);
        ll.append(20);
        ll.append(30);
        System.out.println("After appends: " + ll.display());
        
        // Test prepend
        ll.prepend(5);
        System.out.println("After prepend: " + ll.display());
        
        // Test delete
        ll.delete(20);
        System.out.println("After deleting 20: " + ll.display());
        System.out.println("List size: " + ll.size());
    }
} 
 #include <iostream>
#include <string>
using namespace std;

// Node class definition
class Node {
public:
    int data;
    Node* next;
    
    /**
     * Constructor to create a new node
     * @param data The data to store in the node
     */
    Node(int data) : data(data), next(nullptr) {}
    
    string toString() const {
        return "Node(" + to_string(data) + ")";
    }
};

// LinkedList class definition
class LinkedList {
private:
    Node* head;
    int size;
    
public:
    /**
     * Constructor to create an empty linked list
     */
    LinkedList() : head(nullptr), size(0) {}
    
    /**
     * Destructor to free allocated memory
     */
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
    
    /**
     * Add a new node at the end of the list
     * Time Complexity: O(n) - must traverse to end
     * Space Complexity: O(1)
     */
    void append(int data) {
        Node* newNode = new Node(data);
        
        // If list is empty, new node becomes head
        if (head == nullptr) {
            head = newNode;
            size++;
            return;
        }
        
        // Traverse to the end of the list
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        
        // Link the last node to the new node
        current->next = newNode;
        size++;
    }
    
    /**
     * Add a new node at the beginning of the list
     * Time Complexity: O(1) - direct insertion
     * Space Complexity: O(1)
     */
    void prepend(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;  // Point new node to current head
        head = newNode;        // Update head to new node
        size++;
    }
    
    /**
     * Delete the first occurrence of data from the list
     * Time Complexity: O(n) - may need to traverse entire list
     * Space Complexity: O(1)
     */
    bool deleteValue(int data) {
        if (head == nullptr) {
            return false;
        }
        
        // If head node contains the data to delete
        if (head->data == data) {
            Node* temp = head;
            head = head->next;
            delete temp;
            size--;
            return true;
        }
        
        // Search for the node to delete
        Node* current = head;
        while (current->next != nullptr) {
            if (current->next->data == data) {
                // Bypass the node to be deleted
                Node* temp = current->next;
                current->next = current->next->next;
                delete temp;
                size--;
                return true;
            }
            current = current->next;
        }
        
        return false;  // Data not found
    }
    
    /**
     * Display the linked list as a string
     */
    string display() const {
        if (head == nullptr) {
            return "Empty list";
        }
        
        string result = "";
        Node* current = head;
        while (current != nullptr) {
            result += to_string(current->data);
            if (current->next != nullptr) {
                result += " -> ";
            }
            current = current->next;
        }
        result += " -> null";
        
        return result;
    }
    
    /**
     * Get the size of the linked list
     */
    int getSize() const {
        return size;
    }
};

// Example usage
int main() {
    LinkedList ll;
    
    // Test append
    ll.append(10);
    ll.append(20);
    ll.append(30);
    cout << "After appends: " << ll.display() << endl;
    
    // Test prepend
    ll.prepend(5);
    cout << "After prepend: " << ll.display() << endl;
    
    // Test delete
    ll.deleteValue(20);
    cout << "After deleting 20: " << ll.display() << endl;
    cout << "List size: " << ll.getSize() << endl;
    
    return 0;
} 