top of page

DSA Java - Doubly Linked List

Doubly Linked List Basics

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways either forward and backward easily as compared to Single Linked List. Following are important terms to understand the concepts of doubly Linked List

  • Link − Each Link of a linked list can store a data called an element.

  • Next − Each Link of a linked list contain a link to next link called Next.

  • Prev − Each Link of a linked list contain a link to previous link called Prev.

  • LinkedList − A LinkedList contains the connection link to the first Link called First and to the last link called Last.


As per above shown illustration, following are the important points to be considered.

  • Doubly LinkedList contains an link element called first and last.

  • Each Link carries a data field(s) and a Link Field called next.

  • Each Link is linked with its next link using its next link.

  • Each Link is linked with its previous link using its prev link.

  • Last Link carries a Link as null to mark the end of the list.

Basic Operations

Following are the basic operations supported by an list.

  • Insertion − add an element at the beginning of the list.

  • Deletion − delete an element at the beginning of the list.

  • Insert Last − add an element in the end of the list.

  • Delete Last − delete an element from the end of the list.

  • Insert After − add an element after an item of the list.

  • Delete − delete an element from the list using key.

  • Display forward − displaying complete list in forward manner.


  • Display backward − displaying complete list in backward manner.

Certainly! Here's an updated version of the DoublyLinkedListExample class that includes the basic operations you mentioned:




public class DoublyLinkedListExample<T> {
    private Node<T> head;
    private Node<T> tail;

    private static class Node<T> {
        private T data;
        private Node<T> prev;
        private Node<T> next;

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

    public void insertAtFront(T data) {
        Node<T> newNode = new Node<>(data);

        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    public void deleteAtFront() {
        if (head == null) {
            return;
        }

        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
    }

    public void insertAtEnd(T data) {
        Node<T> newNode = new Node<>(data);

        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    public void deleteAtEnd() {
        if (tail == null) {
            return;
        }

        if (head == tail) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
    }

    public void insertAfter(T key, T data) {
        Node<T> newNode = new Node<>(data);

        Node<T> current = head;
        while (current != null) {
            if (current.data.equals(key)) {
                if (current == tail) {
                    tail = newNode;
                } else {
                    newNode.next = current.next;
                    current.next.prev = newNode;
                }
                newNode.prev = current;
                current.next = newNode;
                return;
            }
            current = current.next;
        }
    }

    public void delete(T key) {
        Node<T> current = head;
        while (current != null) {
            if (current.data.equals(key)) {
                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;
            }
            current = current.next;
        }
    }

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

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

    public static void main(String[] args) {
        DoublyLinkedListExample<Integer> doublyLinkedList = new DoublyLinkedListExample<>();

        doublyLinkedList.insertAtFront(10);
        doublyLinkedList.insertAtFront(5);
        doublyLinkedList.insertAtEnd(20);

        doublyLinkedList.displayForward(); // Output: 5 10 20
        doublyLinkedList.displayBackward(); // Output: 20 10 5

        doublyLinkedList.deleteAtFront();
        doublyLinkedList.deleteAtEnd();

        doublyLinkedList.displayForward(); // Output: 10
        doublyLinkedList.displayBackward(); // Output: 10

        doublyLinkedList.insertAfter(10, 15);

        doublyLinkedList.displayForward(); // Output: 10 15
        doublyLinkedList.displayBackward(); // Output: 15 10

        doublyLinkedList.delete(10);

        doublyLinkedList.displayForward(); // Output: 15
        doublyLinkedList.displayBackward(); // Output: 15
    }
}
  • deleteAtFront(): Deletes the element at the beginning of the list. If the list is empty, it does nothing. If the list has only one element, both head and tail are set to null. Otherwise, it updates the head and the prev pointer of the new head.

  • deleteAtEnd(): Deletes the element at the end of the list. If the list is empty, it does nothing. If the list has only one element, both head and tail are set to null. Otherwise, it updates the tail and the next pointer of the new tail.

  • insertAfter(T key, T data): Inserts a new element after a given key in the list. It searches for the key starting from the head and stops when it finds the first occurrence. If the key is found, it inserts the new element after the key by updating the next, prev, and next.prev pointers accordingly. If the key is not found, no insertion is performed.

  • delete(T key): Deletes the first occurrence of an element with the given key from the list. It searches for the key starting from the head and stops when it finds the first occurrence. If the key is found, it updates the next and prev pointers of the adjacent nodes to skip the node with the key. If the key is not found, no deletion is performed.

  • displayForward(): Displays the complete list in forward manner, starting from the head.

  • displayBackward(): Displays the complete list in backward manner, starting from the tail.


Related Posts

See All

DSA Java - Stack

In computer science, a stack is an abstract data type that represents a collection of elements with a last-in, first-out (LIFO) order of access. This means that the most recently added element is the

Java Algorithms

Java is a popular programming language that provides a wide range of tools and libraries for implementing various algorithms. Here are some commonly used algorithms in Java: Sorting Algorithms: Bubble

Java - Data Structures

When it comes to Data Structures and Algorithms (DSA) in Java, there are several commonly used data structures that can be implemented. Here are some of the main data structures and their correspondin

Comments


bottom of page