Implementing a Doubly Linked List program in Java

Introduction

In this post, we’ll delve into the implementation of a doubly linked list in Java. A doubly linked list allows traversal in both directions, providing a more flexible data structure than a singly linked list.

Code Overview

We’ll create three classes: Node, DoublyLinkedList, and Main. The Node class represents each node in the list, DoublyLinkedList manages the operations, and Main demonstrates how to use the list.

Node Class

The Node class holds data and pointers to the previous and next nodes.

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

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

DoublyLinkedList Class

The DoublyLinkedList class provides methods to insert, remove, and check values, and print the list.

class DoublyLinkedList {
    Node head;
    Node tail;

    DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    public void insert(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    public boolean remove(int val) {
        Node current = head;
        while (current != null) {
            if (current.data == val) {
                if (current == head) {
                    head = current.next;
                    if (head != null) head.prev = null;
                } else if (current == tail) {
                    tail = current.prev;
                    if (tail != null) tail.next = null;
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public boolean contains(int val) {
        Node current = head;
        while (current != null) {
            if (current.data == val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

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

    public void printerReverse() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
}

Main Class

The Main class demonstrates how to use the doubly linked list by inserting nodes, checking for values, removing nodes, and printing the list in both directions.

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.insert(40);
        list.insert(50);

        System.out.println("Initial list:");
        list.printer();

        System.out.println("List printed in reverse:");
        list.printerReverse();

        // Check if list contains 30
        System.out.println("List contains 30: " + list.contains(30));

        // Remove 20 and print the list again
        System.out.println("Removing 20:");
        list.remove(20);
        list.printer();

        // Check if list contains 20
        System.out.println("List contains 20: " + list.contains(20));

        // Remove 50 and print the list again
        System.out.println("Removing 50:");
        list.remove(50);
        list.printer();

        // Print list in reverse again
        System.out.println("List printed in reverse after removals:");
        list.printerReverse();
    }
}

Summary

In this post, we explored the implementation of a doubly linked list in Java. We implemented methods for inserting, removing, and checking nodes, and demonstrated these operations. Doubly linked lists are versatile and can be used in various applications where bidirectional traversal is beneficial.

Stay tuned for more data structure tutorials and happy coding!

Notes

Printing Methods: printer() and printerReverse() help visualize the list’s contents.
Node Removal: The remove method handles edge cases (head and tail removal).
Value Checking: The contains method checks if a value exists in the list.

This post and the code provide a comprehensive guide to implementing and using a doubly linked list in Java.