Java Data Structures and Algorithms for Beginners

Linked List Data Structure

Definition and Concepts

A linked list is a linear data structure consisting of a sequence of nodes, where each node contains data and a reference (or link) to the next node. Unlike arrays, linked lists do not store elements in contiguous memory locations, allowing dynamic memory allocation. In a singly linked list, each node points to the next node, with the last node pointing to null. You can visualize a linked list as a chain of boxes, where each box holds a value and an arrow pointing to the next box. Linked lists are flexible for insertions and deletions but require traversal to access elements, making them suitable for dynamic data.

Why Use It?

Linked lists are used when you need a dynamic data structure that can grow or shrink efficiently without requiring contiguous memory. They allow fast insertions and deletions at known positions (e.g., head or tail) compared to arrays. Linked lists are ideal for applications where the size of the list is unknown or changes frequently, and they serve as a foundation for other data structures like stacks and queues.

Where to Use? (Real-Life Examples)

• Dynamic Data Storage: Linked lists are used in applications like music playlists, where songs can be added or removed dynamically.
• Implementation of Stacks and Queues: Stacks and queues are often implemented using linked lists due to their flexibility in size.
• Browser History: Web browsers use linked lists to maintain a history of visited pages, allowing easy navigation forward and backward.
• Memory Management: Operating systems use linked lists to manage free memory blocks in dynamic memory allocation.

Explain Operations

• Insert at Head: This operation adds a new node at the beginning of the list. It has a time complexity of O(1).
• Insert at Tail: This operation adds a new node at the end of the list. It has a time complexity of O(n) due to traversal.
• Delete at Head: This operation removes the first node. It has a time complexity of O(1).
• Delete by Value: This operation removes the first node with a given value. It has a time complexity of O(n) due to traversal.
• Search: This operation finds a node with a given value. It has a time complexity of O(n).
• isEmpty: This operation checks whether the linked list is empty. It has a time complexity of O(1).
• Size: This operation returns the number of nodes in the linked list. It has a time complexity of O(1) if maintained.

Java Implementation

The following Java code implements a singly linked list with basic operations.

public class LinkedList {
    private class Node {
        int value; // Value stored in the node
        Node next; // Reference to the next node

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

    private Node head; // Head of the linked list
    private int size; // Number of nodes in the linked list

    // Constructor to initialize an empty linked list
    public LinkedList() {
        head = null;
        size = 0;
    }

    // Insert at Head: Adds a new node at the beginning
    public void insertAtHead(int value) {
        Node newNode = new Node(value); // Creates a new node
        newNode.next = head; // Points new node to current head
        head = newNode; // Updates head to new node
        size++; // Increments size
    }

    // Insert at Tail: Adds a new node at the end
    public void insertAtTail(int value) {
        Node newNode = new Node(value); // Creates a new node
        if (isEmpty()) { // If list is empty, sets head to new node
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) { // Traverses to the last node
                current = current.next;
            }
            current.next = newNode; // Adds new node at the end
        }
        size++; // Increments size
    }

    // Delete at Head: Removes the first node
    public void deleteAtHead() {
        if (isEmpty()) { // Checks if the list is empty
            throw new IllegalStateException("The linked list is empty.");
        }
        head = head.next; // Moves head to the next node
        size--; // Decrements size
    }

    // Delete by Value: Removes the first node with the given value
    public void deleteByValue(int value) {
        if (isEmpty()) { // Checks if the list is empty
            throw new IllegalStateException("The linked list is empty.");
        }
        if (head.value == value) { // If head has the value, removes head
            head = head.next;
            size--;
            return;
        }
        Node current = head;
        Node prev = null;
        while (current != null && current.value != value) { // Traverses to find the value
            prev = current;
            current = current.next;
        }
        if (current == null) { // If value not found
            throw new IllegalArgumentException("Value not found in the linked list.");
        }
        prev.next = current.next; // Bypasses the node to delete
        size--; // Decrements size
    }

    // Search: Checks if a value exists in the linked list
    public boolean search(int value) {
        Node current = head;
        while (current != null) { // Traverses the list
            if (current.value == value) {
                return true; // Returns true if value is found
            }
            current = current.next;
        }
        return false; // Returns false if value is not found
    }

    // isEmpty: Checks if the linked list is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Size: Returns the number of nodes in the linked list
    public int size() {
        return size;
    }
}

How It Works

1. Initialization: The constructor initializes head as null and size as 0, indicating an empty linked list.
2. Insert at Head:
   • The method creates a new node with the given value, sets its next to the current head, updates head to the new node, and increments size.
3. Insert at Tail:
   • The method creates a new node. If the list is empty, it sets head to the new node. Otherwise, it traverses to the last node and sets its next to the new node, then increments size.
4. Delete at Head:
   • The method checks if the list is empty. If not, it moves head to the next node and decrements size. If empty, it throws an exception.
5. Delete by Value:
   • The method checks if the list is empty or if the head node has the value. If the head is the target, it updates head and decrements size.
   • Otherwise, it traverses the list to find the value, keeping track of the previous node, and bypasses the target node by updating the previous node’s next. It decrements size or throws an exception if the value is not found.
6. Search Operation: The method traverses the list, returning true if the value is found and false if the end (null) is reached.
7. isEmpty Operation: The method returns true if size equals 0, indicating an empty list, and false otherwise.
8. Size Operation: The method returns size, which tracks the number of nodes.

Complexity Analysis Table

Note: n is the number of nodes in the linked list.

Key Differences / Notes

• Singly vs. Doubly Linked List:
  • The implementation above is a singly linked list, where each node points to the next. It is memory-efficient but slow for tail operations (O(n)).
  • A doubly linked list has nodes with pointers to both the next and previous nodes, enabling O(1) tail deletions but using more memory.
• Linked List vs. Array:
  • Linked lists support dynamic sizing and efficient insertions/deletions at the head, but random access and tail operations are O(n).
  • Arrays offer O(1) random access but require contiguous memory and have O(n) insertions/deletions in the middle.
• Thread Safety: The implementation is not thread-safe. For concurrent applications, use Java’s ConcurrentLinkedDeque or synchronize access.
• Java’s Built-in Linked List: Java provides LinkedList in java.util, which is a doubly linked list supporting both List and Deque interfaces.

✅ Tip: Use a linked list when frequent insertions or deletions at the head are needed, or when the size of the list is unknown. For tail operations, consider a doubly linked list or maintain a tail pointer.

⚠ Warning: Avoid using a singly linked list for applications requiring frequent access to the tail or random positions, as traversal is O(n). Use arrays or other structures for such cases.

Exercises

1. Reverse a Linked List: Write a Java program that reverses the linked list using the implementation above. Test it with lists of varying sizes.
2. Cycle Detection: Extend the linked list implementation to detect if it contains a cycle (e.g., using Floyd’s Tortoise and Hare algorithm). Test with cyclic and acyclic lists.
3. Merge Two Sorted Lists: Create a program that merges two sorted linked lists into a single sorted linked list. Use the implementation above and test with different inputs.
4. Middle Element Finder: Implement a method to find the middle element of the linked list in a single pass. Use the fast-and-slow pointer technique and test it.
5. Playlist Manager: Simulate a music playlist using the linked list. Allow users to add songs (insert at head or tail), remove songs (delete by value), and print the playlist.