Java Data Structures: Implementing Linked Lists and BST Operations

Posted on Oct 28, 2025 in Computer Engineering in Computer Engineering

Singly Linked List (SLL) Implementation in Java

Singly Linked List: Insertion Operations

This section demonstrates the basic structure and insertion methods for a Singly Linked List.

public class SinglyList {
    private Node head;

    private class Node {
        int data;
        Node next;
    }

    public boolean isEmpty() {
        return (head == null);
    }

    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        head = newNode;
    }

    public void insertAfterData(int dataAfter, int item) {
        if (isEmpty()) {
            System.out.println("List is empty. Insertion not possible.");
            return;
        }

        Node temp = head;

        Node newNode = new Node();
        newNode.data = item;

        while (temp != null && temp.data != dataAfter) {
            temp = temp.next;
        }

        if (temp == null) {
            System.out.println("Node is not present in the list.");
            return;
        }

        newNode.next = temp.next;
        temp.next = newNode;
    }

    public void displayList() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

Singly Linked List: Deletion Operations

This implementation includes a Node constructor and methods for deleting elements from the beginning, end, or after a specific data value.

public class SinglyList {
    private Node head;

    private class Node {
        int data;
        Node next;

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

    public boolean isEmpty() {
        return head == null;
    }

    public void insertFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    public void insertLast(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    public void insertAfterData(int dataAfter, int item) {
        if (isEmpty()) {
            System.out.println("List is empty. Insertion not possible.");
            return;
        }
        Node temp = head;
        while (temp != null && temp.data != dataAfter) {
            temp = temp.next;
        }
        if (temp == null) {
            System.out.println("Node with data " + dataAfter + " not found.");
            return;
        }
        Node newNode = new Node(item);
        newNode.next = temp.next;
        temp.next = newNode;
    }

    public void deleteFirst() {
        if (isEmpty()) {
            System.out.println("List is empty. Deletion not possible.");
            return;
        }
        head = head.next;
    }

    public void deleteLast() {
        if (isEmpty()) {
            System.out.println("List is empty. Deletion not possible.");
            return;
        }
        if (head.next == null) {
            head = null;
            return;
        }
        Node temp = head;
        while (temp.next.next != null) {
            temp = temp.next;
        }
        temp.next = null;
    }

    public void deleteAfterData(int data) {
        if (isEmpty()) {
            System.out.println("List is empty. Deletion not possible.");
            return;
        }
        Node temp = head;
        while (temp != null && temp.data != data) {
            temp = temp.next;
        }
        if (temp == null || temp.next == null) {
            System.out.println("Node with data " + data + " not found or it's the last node.");
            return;
        }
        temp.next = temp.next.next;
    }

    public void displayList() {
        if (isEmpty()) {
            System.out.println("List is empty.");
            return;
        }
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}

Doubly Linked List (DLL) Implementation in Java

Doubly Linked List: Insertion Methods

The Doubly Linked List allows traversal in both forward and reverse directions, requiring prev and next pointers.

public class DoublyLinkedList {
    private Node head;
    private Node last;

    private class Node {
        int data;
        Node next;
        Node prev;

        Node(int data) {
            this.data = data;
        }
    }

    public int listSize() {
        Node trav = head;
        int s = 0;
        while (trav != null) {
            s++;
            trav = trav.next;
        }
        return s;
    }

    public void insertAtPosition(int data, int position) {
        int size = listSize();
        if (position > 0 && position <= size + 1) {
            Node newNode = new Node(data);
            if (position == 1) {
                insertFirst(data);
            } else if (position == size + 1) {
                insertLast(data);
            } else {
                Node current = head;
                // Traverse to the node *before* the insertion point (position - 1)
                // Note: The original code traverses to the node *at* the insertion point
                for (int j = 1; j < position; j++) {
                    current = current.next;
                }
                // current is now the node *at* the position where the new node should go
                newNode.next = current;
                newNode.prev = current.prev;
                current.prev.next = newNode;
                current.prev = newNode;
            }
        } else {
            System.out.println("Position " + position + " not valid for list size " + size);
        }
    }

    public boolean isEmpty() {
        return (head == null);
    }

    public void displayList(Node trav) {
        if (isEmpty()) {
            System.out.println("List is empty. Nothing to show.");
            return;
        }
        if (trav == null) {
            trav = head;
        }
        System.out.println("Forward traversal");
        while (trav != null) {
            System.out.print(trav.data + " ");
            last = trav; // Keep track of the last node
            trav = trav.next;
        }
        System.out.println();
        System.out.println("Reverse traversal");
        while (last != null) {
            System.out.print(last.data + " ");
            last = last.prev;
        }
        System.out.println();
    }

    private void insertFirst(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = last = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    private void insertLast(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = last = newNode;
        } else {
            last.next = newNode;
            newNode.prev = last;
            last = newNode;
        }
    }
}

Doubly Linked List: Deletion Methods

Methods for calculating size and deleting a node at a specific index (0-based).

// Assuming the class structure from the insertion section continues

public int listSize() {
    Node trav = head;
    int s = 0;
    while (trav != null) {
        s++;
        trav = trav.next;
    }
    return s;
}

public void deleteAtPosition(int position) {
    if (isEmpty()) {
        System.out.println("List is empty (underflow). Deletion stopped.");
        return;
    }
    int size = listSize();
    // Assuming 0-based indexing for position
    if (position < 0 || position >= size) {
        System.out.println("Index " + position + " is not valid in the linked list of size " + size);
        return;
    }
    Node current = head;
    if (position == 0) {
        deleteFirst();
    } else if (position == size - 1) {
        deleteLast();
    } else {
        // Traverse to the node to be deleted
        for (int j = 0; j < position; j++) {
            current = current.next;
        }
        // Bypass the current node
        current.prev.next = current.next;
        current.next.prev = current.prev;
    }
}

// Note: deleteFirst and deleteLast methods must be implemented within the DLL class

public void displayList(Node trav) {
    if (isEmpty()) {
        System.out.println("List is empty. Nothing to show.");
        return;
    }
    
    // The original code snippet had redundant initialization for 'next'
    
    System.out.println("Forward traversal");
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
    
    System.out.println("Reverse traversal");
    Node lastNode = head;
    if (lastNode != null) {
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }
        while (lastNode != null) {
            System.out.print(lastNode.data + " ");
            lastNode = lastNode.prev;
        }
    }
    System.out.println();
}

Binary Search Tree (BST) Operations

BST Insertion and Inorder Traversal

These recursive methods demonstrate how to insert a node into a Binary Search Tree and perform an inorder traversal (which outputs elements in sorted order).

// Assuming a Node class exists with data, left, and right fields

Node insertBinarySearchTree(Node root, int item) {
    if (root == null) {
        root = new Node(item);
        return root;
    }
    if (item < root.data)
        root.left = insertBinarySearchTree(root.left, item);
    else
        root.right = insertBinarySearchTree(root.right, item);
    return root;
}

void inorderDisplay(Node root) {
    if (root != null) {
        inorderDisplay(root.left);
        System.out.print(root.data + " ");
        inorderDisplay(root.right);
    }
}