Latest Linked List Using Java with all Operations Cheatsheet

1. Introduction to Linked Lists 2. Singly Linked List - Basic Operations 3. Singly Linked List - Deletion Operations 4. Singly Linked List - Search and Utility 5. Reversing a Linked List 6. Doubly Linked List - Implementation 7. Circular Linked List 8. Common Linked List Problems - Part 1 9. Common Linked List Problems - Part 2 10. Time Complexity Analysis 11. Java Collections Framework - LinkedList 12. Best Practices and Tips

Introduction to Linked Lists

Understanding the fundamental concepts and advantages of linked lists

basics

Linked List: A linear data structure where elements are stored in nodes, and each node contains a data field and a reference (link) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, which provides dynamic memory allocation and efficient insertion and deletion operations. Linked lists are particularly useful when the size of the data structure is unknown or changes frequently during program execution.

java

// Basic Node Structure
class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Linked List Class Structure
class LinkedList {
    Node head;
    
    LinkedList() {
        this.head = null;
    }
}

java

// Advantages of Linked Lists
// 1. Dynamic size - can grow or shrink at runtime
// 2. Efficient insertion/deletion - O(1) at beginning
// 3. No memory waste - allocate only what you need
// 4. Easy to implement stacks and queues

// Disadvantages of Linked Lists
// 1. No random access - must traverse from head
// 2. Extra memory for pointers
// 3. Cache performance is poor compared to arrays
// 4. Reverse traversal is difficult (singly linked)

Singly Linked List - Basic Operations

Implementing fundamental operations in a singly linked list

singly-linked-list

Singly Linked List: The simplest form of linked list where each node contains data and a single pointer to the next node. The list starts with a head pointer that points to the first node, and the last node points to null, indicating the end of the list. This structure allows efficient insertion and deletion at the beginning of the list, making it ideal for implementing stacks and queues where operations are performed at one end.

java

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

// Insert at the end
public void insertAtEnd(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;
}

java

// Insert at specific position
public void insertAtPosition(int data, int position) {
    Node newNode = new Node(data);
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        return;
    }
    Node current = head;
    for (int i = 0; i < position - 1 && current != null; i++) {
        current = current.next;
    }
    if (current != null) {
        newNode.next = current.next;
        current.next = newNode;
    }
}

java

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

// Get size of linked list
public int size() {
    int count = 0;
    Node current = head;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

Singly Linked List - Deletion Operations

Removing nodes from different positions in a singly linked list

singly-linked-list

Deletion Operations: Removing nodes from a linked list requires careful handling of pointers to maintain the list structure. When deleting a node, you must update the previous node to point to the next node, effectively bypassing the node to be deleted. Special cases include deleting the head node, the last node, and nodes in the middle. Proper memory management is crucial, especially in languages without automatic garbage collection, though Java handles this automatically.

java

// Delete from beginning
public void deleteFromBeginning() {
    if (head == null) {
        return;
    }
    head = head.next;
}

// Delete from end
public void deleteFromEnd() {
    if (head == null || head.next == null) {
        head = null;
        return;
    }
    Node current = head;
    while (current.next.next != null) {
        current = current.next;
    }
    current.next = null;
}

java

// Delete by value
public void deleteByValue(int data) {
    if (head == null) {
        return;
    }
    if (head.data == data) {
        head = head.next;
        return;
    }
    Node current = head;
    while (current.next != null) {
        if (current.next.data == data) {
            current.next = current.next.next;
            return;
        }
        current = current.next;
    }
}

// Delete at specific position
public void deleteAtPosition(int position) {
    if (head == null) {
        return;
    }
    if (position == 0) {
        head = head.next;
        return;
    }
    Node current = head;
    for (int i = 0; i < position - 1 && current != null; i++) {
        current = current.next;
    }
    if (current != null && current.next != null) {
        current.next = current.next.next;
    }
}

Singly Linked List - Search and Utility

Searching for elements and common utility functions

singly-linked-list

Search and Utility Functions: Searching in a linked list requires linear traversal from the head to the target element, making it an O(n) operation. Unlike arrays, there is no random access, so you must visit each node sequentially until you find the desired value or reach the end of the list. Utility functions such as checking if the list is empty, finding the middle element, and reversing the list are common operations that every developer should master when working with linked lists.

java

// Search for an element
public boolean search(int data) {
    Node current = head;
    while (current != null) {
        if (current.data == data) {
            return true;
        }
        current = current.next;
    }
    return false;
}

// Get element at index
public int get(int index) {
    Node current = head;
    for (int i = 0; i < index && current != null; i++) {
        current = current.next;
    }
    if (current == null) {
        throw new IndexOutOfBoundsException();
    }
    return current.data;
}

java

// Check if list is empty
public boolean isEmpty() {
    return head == null;
}

// Clear the entire list
public void clear() {
    head = null;
}

// Check if list contains element
public boolean contains(int data) {
    return search(data);
}

Reversing a Linked List

Different approaches to reverse a singly linked list

algorithms

Reversing a Linked List: Reversing a linked list is one of the most common interview questions and a fundamental operation that tests your understanding of pointer manipulation. There are multiple approaches to reverse a linked list, including iterative and recursive methods. The iterative approach uses three pointers to traverse and reverse the links, while the recursive approach leverages the call stack to reverse the list from the end. Both methods have their advantages, with iterative being more memory-efficient and recursive being more elegant.

java

// Iterative approach to reverse
public void reverse() {
    Node prev = null;
    Node current = head;
    Node next = null;
    
    while (current != null) {
        next = current.next;    // Store next node
        current.next = prev;    // Reverse the link
        prev = current;         // Move prev forward
        current = next;         // Move current forward
    }
    head = prev;                // Update head
}

java

// Recursive approach to reverse
public Node reverseRecursive(Node node) {
    if (node == null || node.next == null) {
        return node;
    }
    Node rest = reverseRecursive(node.next);
    node.next.next = node;
    node.next = null;
    return rest;
}

// Wrapper method
public void reverseRecursive() {
    head = reverseRecursive(head);
}

java

// Reverse in groups of k
public Node reverseInGroups(Node head, int k) {
    Node current = head;
    Node prev = null;
    Node next = null;
    int count = 0;
    
    while (current != null && count < k) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }
    
    if (next != null) {
        head.next = reverseInGroups(next, k);
    }
    
    return prev;
}

Doubly Linked List - Implementation

Creating and managing a doubly linked list structure

doubly-linked-list

Doubly Linked List: A doubly linked list is an enhanced version of a singly linked list where each node contains two pointers: one pointing to the next node and another pointing to the previous node. This bidirectional linking allows traversal in both forward and backward directions, making operations like deletion more efficient. The list has both a head pointer pointing to the first node and a tail pointer pointing to the last node, which enables efficient insertion and deletion at both ends of the list.

java

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

// Doubly Linked List Class
class DoublyLinkedList {
    DoublyNode head;
    DoublyNode tail;
    
    DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }
}

java

// Insert at beginning
public void insertAtBeginning(int data) {
    DoublyNode newNode = new DoublyNode(data);
    if (head == null) {
        head = tail = newNode;
        return;
    }
    newNode.next = head;
    head.prev = newNode;
    head = newNode;
}

// Insert at end
public void insertAtEnd(int data) {
    DoublyNode newNode = new DoublyNode(data);
    if (tail == null) {
        head = tail = newNode;
        return;
    }
    tail.next = newNode;
    newNode.prev = tail;
    tail = newNode;
}

java

// Delete from beginning
public void deleteFromBeginning() {
    if (head == null) {
        return;
    }
    if (head == tail) {
        head = tail = null;
        return;
    }
    head = head.next;
    head.prev = null;
}

// Delete from end
public void deleteFromEnd() {
    if (tail == null) {
        return;
    }
    if (head == tail) {
        head = tail = null;
        return;
    }
    tail = tail.prev;
    tail.next = null;
}

Circular Linked List

Understanding and implementing circular linked lists

circular-linked-list

Circular Linked List: A circular linked list is a variation of a linked list where the last node points back to the first node instead of null, creating a circular structure. This can be implemented as either a circular singly linked list or a circular doubly linked list. The circular structure eliminates the need for a null pointer at the end and allows continuous traversal from any node. This structure is particularly useful in applications like round-robin scheduling, where you need to cycle through elements repeatedly.

java

// Circular Singly Linked List
class CircularLinkedList {
    Node head;
    
    // Insert at beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
            return;
        }
        Node current = head;
        while (current.next != head) {
            current = current.next;
        }
        newNode.next = head;
        current.next = newNode;
        head = newNode;
    }
}

java

// Display circular list
public void display() {
    if (head == null) {
        return;
    }
    Node current = head;
    do {
        System.out.print(current.data + " -> ");
        current = current.next;
    } while (current != head);
    System.out.println("(back to head)");
}

// Delete from circular list
public void delete(int data) {
    if (head == null) {
        return;
    }
    if (head.data == data && head.next == head) {
        head = null;
        return;
    }
    Node current = head;
    while (current.next != head) {
        if (current.next.data == data) {
            current.next = current.next.next;
            return;
        }
        current = current.next;
    }
}

Common Linked List Problems - Part 1

Solving frequently asked linked list problems

problems

Common Problems: Linked list problems are frequently asked in technical interviews and coding competitions. These problems test your ability to manipulate pointers, handle edge cases, and think algorithmically. Common problems include finding the middle element, detecting cycles, merging sorted lists, and removing duplicates. Mastering these problems requires understanding pointer manipulation, two-pointer techniques, and recursive thinking. Practice with these problems will significantly improve your problem-solving skills.

java

// Find middle element (two-pointer technique)
public int findMiddle() {
    if (head == null) {
        return -1;
    }
    Node slow = head;
    Node fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow.data;
}

// Detect cycle in linked list
public boolean hasCycle() {
    if (head == null) {
        return false;
    }
    Node slow = head;
    Node fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

java

// Remove duplicates from sorted list
public void removeDuplicates() {
    Node current = head;
    while (current != null && current.next != null) {
        if (current.data == current.next.data) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
}

// Find nth node from end
public int getNthFromEnd(int n) {
    Node first = head;
    Node second = head;
    
    for (int i = 0; i < n; i++) {
        if (first == null) {
            return -1;
        }
        first = first.next;
    }
    
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    return second.data;
}

Common Linked List Problems - Part 2

Advanced problem-solving techniques with linked lists

problems

Advanced Problems: More complex linked list problems involve merging multiple lists, detecting intersection points, partitioning lists, and implementing advanced data structures. These problems often require combining multiple techniques like two-pointer approach, recursion, and careful pointer manipulation. Understanding these advanced patterns will help you solve challenging interview questions and real-world problems efficiently. Practice with these problems will build your confidence in handling complex pointer operations and edge cases.

java

// Merge two sorted linked lists
public Node mergeSortedLists(Node list1, Node list2) {
    Node dummy = new Node(0);
    Node current = dummy;
    
    while (list1 != null && list2 != null) {
        if (list1.data <= list2.data) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    if (list1 != null) {
        current.next = list1;
    }
    if (list2 != null) {
        current.next = list2;
    }
    
    return dummy.next;
}

java

// Check if list is palindrome
public boolean isPalindrome() {
    if (head == null || head.next == null) {
        return true;
    }
    
    // Find middle
    Node slow = head;
    Node fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Reverse second half
    Node secondHalf = reverseList(slow.next);
    Node firstHalf = head;
    
    // Compare
    while (secondHalf != null) {
        if (firstHalf.data != secondHalf.data) {
            return false;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }
    return true;
}

java

// Intersection of two linked lists
public Node getIntersectionNode(Node headA, Node headB) {
    if (headA == null || headB == null) {
        return null;
    }
    
    Node a = headA;
    Node b = headB;
    
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    
    return a;
}

// Remove nth node from end
public void removeNthFromEnd(int n) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node first = dummy;
    Node second = dummy;
    
    for (int i = 0; i <= n; i++) {
        first = first.next;
    }
    
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    
    second.next = second.next.next;
    head = dummy.next;
}

Time Complexity Analysis

Understanding time and space complexity of linked list operations

complexity

Time Complexity: Understanding the time and space complexity of linked list operations is crucial for choosing the right data structure for your application. Most operations in linked lists have different complexities compared to arrays. Insertion and deletion at the beginning are O(1) operations, which is a significant advantage over arrays. However, accessing elements by index requires O(n) time since you must traverse from the head. This trade-off makes linked lists ideal for scenarios with frequent insertions and deletions but infrequent random access.

java

// Time Complexity of Common Operations

// Insertion:
// - At beginning: O(1)
// - At end: O(n) - need to traverse
// - At position: O(n) - worst case

// Deletion:
// - From beginning: O(1)
// - From end: O(n) - need to traverse
// - By value: O(n) - need to search first

// Search:
// - By value: O(n) - linear search
// - By index: O(n) - must traverse

// Access:
// - By index: O(n) - no random access
// - First element: O(1)
// - Last element: O(n)

java

// Space Complexity

// Singly Linked List:
// - Space: O(n) - n nodes with data and pointer
// - Each node: data + pointer = O(1) space

// Doubly Linked List:
// - Space: O(n) - n nodes with data and two pointers
// - Each node: data + 2 pointers = O(1) space
// - Slightly more memory than singly linked list

// Comparison with Arrays:
// - Arrays: O(n) contiguous memory
// - Linked Lists: O(n) non-contiguous memory
// - Linked lists have overhead of pointers

java

// When to Use Linked Lists

// Use Linked Lists when:
// 1. Size is unknown and changes frequently
// 2. Frequent insertions/deletions at beginning
// 3. Implementing stacks and queues
// 4. Memory is fragmented
// 5. No need for random access

// Use Arrays when:
// 1. Size is known and fixed
// 2. Need random access by index
// 3. Memory efficiency is critical
// 4. Cache performance matters
// 5. Frequent access by position

Java Collections Framework - LinkedList

Using the built-in LinkedList class in Java

collections

Java Collections Framework: Java provides a built-in LinkedList class in the java.util package that implements the List and Deque interfaces. This implementation uses a doubly linked list internally, providing efficient insertion and deletion operations. The Java LinkedList class offers many convenient methods for common operations, eliminating the need to implement your own linked list in most scenarios. Understanding how to use this class effectively is essential for Java developers, as it is widely used in real-world applications.

java

// Creating and basic operations
import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<>();

// Adding elements
list.add(10);                    // Add at end
list.addFirst(5);                // Add at beginning
list.addLast(20);                // Add at end
list.add(1, 15);                 // Add at index

// Accessing elements
int first = list.getFirst();      // Get first element
int last = list.getLast();        // Get last element
int element = list.get(2);        // Get at index

// Removing elements
list.removeFirst();               // Remove first
list.removeLast();                // Remove last
list.remove(1);                   // Remove at index
list.remove(Integer.valueOf(10)); // Remove by value

java

// Iterating through LinkedList
// Method 1: Enhanced for loop
for (Integer item : list) {
    System.out.println(item);
}

// Method 2: Iterator
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

// Method 3: ListIterator (bidirectional)
ListIterator<Integer> listIterator = list.listIterator();
while (listIterator.hasNext()) {
    System.out.println(listIterator.next());
}

java

// Common utility methods
list.size();                      // Get size
list.isEmpty();                   // Check if empty
list.contains(10);                // Check if contains
list.indexOf(10);                 // Get index of element
list.clear();                     // Clear all elements

// Queue operations (LinkedList implements Deque)
list.offer(30);                   // Add to end
list.poll();                      // Remove from front
list.peek();                      // View front element

// Stack operations
list.push(40);                    // Push to front
list.pop();                        // Pop from front

Best Practices and Tips

Important guidelines and common pitfalls when working with linked lists

best-practices

Best Practices: When working with linked lists, there are several important practices to follow to write efficient and bug-free code. Always check for null pointers before dereferencing, especially when traversing the list. Use dummy nodes to simplify edge case handling, particularly when inserting or deleting at the beginning. Be careful with pointer manipulation to avoid losing references to nodes. Consider using two-pointer techniques for problems involving finding middle elements or detecting cycles. These practices will help you write more robust and maintainable code.

java

// Always check for null
public void safeTraverse() {
    if (head == null) {
        return;  // Handle empty list
    }
    Node current = head;
    while (current != null) {
        // Process current node
        current = current.next;
    }
}

// Use dummy node for simplification
public void insertWithDummy(int data) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node current = dummy;
    
    // Operations become simpler
    // No need to handle head separately
}

java

// Common Pitfalls to Avoid

// 1. Forgetting to update head/tail
// Always update head when inserting/deleting at beginning

// 2. Losing reference to nodes
// Store next node before modifying pointers

// 3. Not handling empty list
// Always check if head == null

// 4. Infinite loops in circular lists
// Use proper termination conditions

// 5. Memory leaks
// Java handles this, but be careful in other languages

java

// Tips for Interview Problems

// 1. Use two-pointer technique for:
//    - Finding middle element
//    - Detecting cycles
//    - Finding nth from end

// 2. Use recursion for:
//    - Reversing list
//    - Problems involving "from end"

// 3. Use dummy nodes for:
//    - Simplifying edge cases
//    - Operations at beginning

// 4. Draw diagrams:
//    - Visualize pointer movements
//    - Understand before coding

Loading...

Loading...

Loading...

Linked List Using Java with all Operations Cheatsheet

Contents

Introduction to Linked Lists

Singly Linked List - Basic Operations

Singly Linked List - Deletion Operations

Singly Linked List - Search and Utility

Reversing a Linked List

Doubly Linked List - Implementation

Circular Linked List

Common Linked List Problems - Part 1

Common Linked List Problems - Part 2

Time Complexity Analysis

Java Collections Framework - LinkedList

Best Practices and Tips