Java Custom Linked List Implementation

Yatin BatraMarch 18th, 2025Last Updated: March 14th, 2025

0 119 6 minutes read

Arrays store elements in a contiguous memory block, whereas a linked list spreads its nodes across different memory locations. Each node holds both data and a reference to the next, allowing efficient element insertion without the need for memory reallocation. Hence, let us delve into understanding the internals of a Java linked list, by developing a custom linked list implementation from scratch with functionalities like insertion, deletion, retrieval, and element counting.

1. What is Linked List Data Structure in Java?

A Linked List is a linear data structure where elements (nodes) are linked using pointers. Unlike arrays, linked lists do not require a contiguous memory location. Each node contains:

Data: The actual value stored in the node.
Pointer: A reference to the next node in the sequence.

Unlike arrays, linked lists provide dynamic memory allocation, making them efficient for insertions and deletions. However, they require additional memory for storing pointers.

1.1 Types of Linked Lists

Linked lists can be categorized into different types based on how nodes are linked together. Each type has its own structure and use case.

Singly Linked List: Each node contains data and a pointer to the next node in the sequence.
Doubly Linked List: Each node contains data, a pointer to the next node, and a pointer to the previous node, allowing traversal in both directions.
Circular Linked List: The last node points back to the first node, forming a circular structure. This can be singly or doubly linked.

1.2 Advantages of Linked Lists

Linked lists offer several benefits over arrays, making them suitable for certain applications where dynamic memory allocation and efficient modifications are required.

Efficient insertions and deletions: Unlike arrays, linked lists do not require shifting elements when inserting or deleting elements.
Dynamic memory allocation: They grow and shrink as needed, avoiding unnecessary memory usage.
Faster reorganization: Data structures like stacks and queues can be implemented efficiently using linked lists.

1.3 Disadvantages of Linked Lists

Despite their advantages, linked lists also have some downsides, primarily due to their pointer-based structure.

Extra memory overhead: Each node requires additional space for storing pointers, increasing memory consumption.
Slower search operations: Unlike arrays, linked lists do not allow direct access to elements, requiring sequential traversal.
More complex implementation: Managing pointers and memory allocation makes linked lists harder to implement compared to arrays.

2. Understanding Linked List via Code

Let’s explore the Singly Linked List and its various implementations through a code example.

// Class representing a Node in the Linked List
class Node {
    int data; // Data stored in the node
    Node next; // Reference to the next node
 
    /**
     * Constructor to initialize a new node with given data.
     * @param data The value to store in the node.
     */
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
// Class representing the Linked List
class LinkedList {
    private Node head; // Head (first node) of the linked list
 
    /**
     * Inserts a new node at the end of the linked list.
     * @param data The value to insert.
     */
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
 
    /**
     * Inserts a new node at the beginning of the linked list.
     * @param data The value to insert.
     */
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
 
    /**
     * Inserts a new node at a specific position in the linked list.
     * @param data The value to insert.
     * @param position The position at which to insert the new node (0-based index).
     */
    public void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 0) {
            insertAtBeginning(data);
            return;
        }
        Node temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }
        if (temp == null) {
            System.out.println("Position out of range.");
            return;
        }
        newNode.next = temp.next;
        temp.next = newNode;
    }
 
    /**
     * Deletes the first occurrence of a node with the given value.
     * @param data The value to delete.
     */
    public void deleteByValue(int data) {
        if (head == null) return;
 
        if (head.data == data) {
            head = head.next;
            return;
        }
 
        Node temp = head;
        while (temp.next != null && temp.next.data != data) {
            temp = temp.next;
        }
 
        if (temp.next == null) {
            System.out.println("Element not found.");
            return;
        }
        temp.next = temp.next.next;
    }
 
    /**
     * Searches for a node with the given value in the linked list.
     * @param key The value to search for.
     * @return true if the value is found, otherwise false.
     */
    public boolean search(int key) {
        Node temp = head;
        while (temp != null) {
            if (temp.data == key) return true;
            temp = temp.next;
        }
        return false;
    }
 
    /**
     * Reverses the linked list.
     */
    public void reverse() {
        Node prev = null, current = head, next;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }
 
    /**
     * Displays the linked list elements.
     */
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}
 
// Driver class to test the Linked List implementation
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
 
        // Insert elements
        list.insert(10);
        list.insert(20);
        list.insert(30);
        System.out.println("Initial Linked List:");
        list.display(); // Output: 10 -> 20 -> 30 -> null
 
        // Insert at the beginning
        list.insertAtBeginning(5);
        System.out.println("After inserting 5 at the beginning:");
        list.display(); // Output: 5 -> 10 -> 20 -> 30 -> null
 
        // Insert at a specific position
        list.insertAtPosition(15, 2);
        System.out.println("After inserting 15 at position 2:");
        list.display(); // Output: 5 -> 10 -> 15 -> 20 -> 30 -> null
 
        // Delete a node by value
        list.deleteByValue(20);
        System.out.println("After deleting 20:");
        list.display(); // Output: 5 -> 10 -> 15 -> 30 -> null
 
        // Search for an element
        System.out.println("Searching for 15: " + list.search(15)); // Output: true
 
        // Reverse the linked list
        list.reverse();
        System.out.println("After reversing the linked list:");
        list.display(); // Output: 30 -> 15 -> 10 -> 5 -> null
    }
}

2.1 Code Explanation and Output

This Java program demonstrates various operations on a singly linked list, including insertion, deletion, searching, and reversing the list. A linked list is a dynamic data structure where elements (nodes) are linked together using pointers, making it different from an array, which requires a contiguous memory location.

The program consists of two main classes:

Node Class: Represents an individual node in the linked list. Each node contains:
- Data: Stores the actual value.
- Next Pointer: Holds the reference to the next node in the list.
LinkedList Class: Manages the linked list and provides various methods to perform operations on it. These methods allow for efficient modification of the list without requiring large-scale memory reallocations.

2.1.1 Key Operations

The LinkedList class provides several essential operations to manipulate the data structure efficiently:

Insertion Methods: The linked list allows inserting nodes in different ways:
- insert(int data): Adds a node at the end of the list. This requires traversing the entire list to find the last node and linking it to the new node.
- insertAtBeginning(int data): Adds a node at the start of the list. This is an efficient operation as it simply updates the head reference to point to the new node.
- insertAtPosition(int data, int position): Adds a node at a specific position. This requires traversing the list to the desired position and updating pointers accordingly.
Deletion Method: The deleteByValue(int data) method removes a node that contains the specified value. It searches for the node and adjusts the references to exclude it from the list.
Search Method: The search(int key) method checks if a given value exists in the linked list. It traverses the list sequentially, making it an O(n) operation.
Reverse Method: The reverse() method reverses the linked list by rearranging node references. This operation transforms the last node into the new head and updates all pointer connections.
Display Method: The display() method prints all the elements of the linked list in sequence. It starts from the head node and follows the next pointers until reaching the end (null).

2.1.2 Code Output

When executed, the code produces the following output:

Initial Linked List:
10 -> 20 -> 30 -> null
 
After inserting 5 at the beginning:
5 -> 10 -> 20 -> 30 -> null
 
After inserting 15 at position 2:
5 -> 10 -> 15 -> 20 -> 30 -> null
 
After deleting 20:
5 -> 10 -> 15 -> 30 -> null
 
Searching for 15: true
 
After reversing the linked list:
30 -> 15 -> 10 -> 5 -> null

3. Conclusion

This program effectively demonstrates how a linked list works in Java, covering fundamental operations like insertion, deletion, searching, and reversal. Understanding these concepts is essential for mastering data structures in Java.

Java Custom Linked List Implementation