Java Program to Implement Doubly Linked List

Problem Description

Write a Java Program to implement a Doubly Linked List.

What is a Doubly Linked List in Java?

A Doubly Linked List in Java is a data structure that consists of a sequence of nodes, where each node has a reference to both the previous and the next node in the list. This allows for both forward and backward traversal of the list, which is not possible with a singly linked list.

In Java, a Doubly Linked List can be implemented using a custom class that defines the structure of each node and the operations that can be performed on the list. The class would typically have methods to add, remove, and access elements in the list, as well as to traverse the list in both directions.

Doubly Linked List Operations

Here are some commonly used operations on a doubly linked list:

1. Insertion: Add a new node to the list at a given position or at the beginning/end of the list.

addFirst(): This operation inserts a new element at the beginning of the list. To do this, the list’s head pointer is updated to point to the new node, and the new node’s next pointer is set to the old head node. If the list was empty, the tail pointer is also updated to point to the new node.
addLast(): This operation inserts a new element at the end of the list. To do this, the list’s tail pointer is updated to point to the new node, and the new node’s previous pointer is set to the old tail node. If the list was empty, the head pointer is also updated to point to the new node.

2. Deletion: Remove a node from the list at a given position or by specifying the node to be removed.

removeFirst(): This operation removes the first element from the list. To do this, the head pointer is updated to point to the second node in the list, and the new head node’s previous pointer is set to null. If the list becomes empty after the removal, the tail pointer is also updated to null.
removeLast(): This operation removes the last element from the list. To do this, the tail pointer is updated to point to the second-to-last node in the list, and the new tail node’s next pointer is set to null. If the list becomes empty after the removal, the head pointer is also updated to null.

3. Traversal: Visit each node in the list in forward or backward direction.

get(int index): This operation returns the element at the specified index. To do this, the list is traversed either from the head or the tail depending on which direction is shorter, until the node at the specified index is reached. Then, the data in that node is returned.

Program/Source Code

Here is the source code of the Java program to implement Doubly Linked List. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

Note: Join free Sanfoundry classes at Telegram or Youtube

```
/*
```

 *  Java Program to Implement Doubly Linked List

```
 */
```
```
 
```
```
import java.util.Scanner;
```
```
 
```
```
/*  Class Node  */
```
```
class Node
```
```
{
```
```
    protected int data;
```
```
    protected Node next, prev;
```
```
 
```
```
    /* Constructor */
```
```
    public Node()
```
```
    {
```
```
        next = null;
```
```
        prev = null;
```
```
        data = 0;
```
```
    }
```
```
    /* Constructor */
```
```
    public Node(int d, Node n, Node p)
```
```
    {
```
```
        data = d;
```
```
        next = n;
```
```
        prev = p;
```
```
    }
```

    /* Function to set link to next node */

```
    public void setLinkNext(Node n)
```
```
    {
```
```
        next = n;
```
```
    }
```

    /* Function to set link to previous node */

```
    public void setLinkPrev(Node p)
```
```
    {
```
```
        prev = p;
```
```
    }    
```

    /* Funtion to get link to next node */

```
    public Node getLinkNext()
```
```
    {
```
```
        return next;
```
```
    }
```

    /* Function to get link to previous node */

```
    public Node getLinkPrev()
```
```
    {
```
```
        return prev;
```
```
    }
```
```
    /* Function to set data to node */
```
```
    public void setData(int d)
```
```
    {
```
```
        data = d;
```
```
    }
```

    /* Function to get data from node */

```
    public int getData()
```
```
    {
```
```
        return data;
```
```
    }
```
```
}
```
```
 
```
```
/* Class linkedList */
```
```
class linkedList
```
```
{
```
```
    protected Node start;
```
```
    protected Node end ;
```
```
    public int size;
```
```
 
```
```
    /* Constructor */
```
```
    public linkedList()
```
```
    {
```
```
        start = null;
```
```
        end = null;
```
```
        size = 0;
```
```
    }
```

    /* Function to check if list is empty */

```
    public boolean isEmpty()
```
```
    {
```
```
        return start == null;
```
```
    }
```
```
    /* Function to get size of list */
```
```
    public int getSize()
```
```
    {
```
```
        return size;
```
```
    }
```

    /* Function to insert element at begining */

```
    public void insertAtStart(int val)
```
```
    {
```

        Node nptr = new Node(val, null, null);

```
        if(start == null)
```
```
        {
```
```
            start = nptr;
```
```
            end = start;
```
```
        }
```
```
        else
```
```
        {
```
```
            start.setLinkPrev(nptr);
```
```
            nptr.setLinkNext(start);
```
```
            start = nptr;
```
```
        }
```
```
        size++;
```
```
    }
```

    /* Function to insert element at end */

```
    public void insertAtEnd(int val)
```
```
    {
```

        Node nptr = new Node(val, null, null);

```
        if(start == null)
```
```
        {
```
```
            start = nptr;
```
```
            end = start;
```
```
        }
```
```
        else
```
```
        {
```
```
            nptr.setLinkPrev(end);
```
```
            end.setLinkNext(nptr);
```
```
            end = nptr;
```
```
        }
```
```
        size++;
```
```
    }
```

    /* Function to insert element at position */

    public void insertAtPos(int val , int pos)

```
    {
```

        Node nptr = new Node(val, null, null);

```
        if (pos == 1)
```
```
        {
```
```
            insertAtStart(val);
```
```
            return;
```
```
        }            
```
```
        Node ptr = start;
```
```
        for (int i = 2; i <= size; i++)
```
```
        {
```
```
            if (i == pos)
```
```
            {
```

                Node tmp = ptr.getLinkNext();

```
                ptr.setLinkNext(nptr);
```
```
                nptr.setLinkPrev(ptr);
```
```
                nptr.setLinkNext(tmp);
```
```
                tmp.setLinkPrev(nptr);
```
```
            }
```

            ptr = ptr.getLinkNext();

```
        }
```
```
        size++ ;
```
```
    }
```

    /* Function to delete node at position */

```
    public void deleteAtPos(int pos)
```
```
    {        
```
```
        if (pos == 1) 
```
```
        {
```
```
            if (size == 1)
```
```
            {
```
```
                start = null;
```
```
                end = null;
```
```
                size = 0;
```
```
                return; 
```
```
            }
```

            start = start.getLinkNext();

```
            start.setLinkPrev(null);
```
```
            size--; 
```
```
            return ;
```
```
        }
```
```
        if (pos == size)
```
```
        {
```
```
            end = end.getLinkPrev();
```
```
            end.setLinkNext(null);
```
```
            size-- ;
```
```
        }
```
```
        Node ptr = start.getLinkNext();
```
```
        for (int i = 2; i <= size; i++)
```
```
        {
```
```
            if (i == pos)
```
```
            {
```

                Node p = ptr.getLinkPrev();

                Node n = ptr.getLinkNext();

```
 
```
```
                p.setLinkNext(n);
```
```
                n.setLinkPrev(p);
```
```
                size-- ;
```
```
                return;
```
```
            }
```
```
            ptr = ptr.getLinkNext();
```
```
        }        
```
```
    }    
```

    /* Function to display status of list */

```
    public void display()
```
```
    {
```

        System.out.print("\nDoubly Linked List = ");

```
        if (size == 0) 
```
```
        {
```

            System.out.print("empty\n");

```
            return;
```
```
        }
```

        if (start.getLinkNext() == null)

```
        {
```

            System.out.println(start.getData() );

```
            return;
```
```
        }
```
```
        Node ptr = start;
```

        System.out.print(start.getData()+ " <-> ");

```
        ptr = start.getLinkNext();
```

        while (ptr.getLinkNext() != null)

```
        {
```

            System.out.print(ptr.getData()+ " <-> ");

```
            ptr = ptr.getLinkNext();
```
```
        }
```

        System.out.print(ptr.getData()+ "\n");

```
    }
```
```
}
```
```
 
```
```
/* Class DoublyLinkedList */
```
```
public class DoublyLinkedList
```
```
{    
```

    public static void main(String[] args)

```
    {            
```

        Scanner scan = new Scanner(System.in);

        /* Creating object of linkedList */

        linkedList list = new linkedList();

        System.out.println("Doubly Linked List Test\n");

```
        char ch;
```
```
        /*  Perform list operations  */
```
```
        do
```
```
        {
```

            System.out.println("\nDoubly Linked List Operations\n");

            System.out.println("1. insert at begining");

            System.out.println("2. insert at end");

            System.out.println("3. insert at position");

            System.out.println("4. delete at position");

            System.out.println("5. check empty");

            System.out.println("6. get size");

            System.out.println("Enter your Choice:");

            int choice = scan.nextInt();

```
            switch (choice)
```
```
            {
```
```
            case 1 : 
```

                System.out.println("Enter integer element to insert");

                list.insertAtStart( scan.nextInt() );

                break;

```
            case 2 : 
```

                System.out.println("Enter integer element to insert");

                list.insertAtEnd( scan.nextInt() );

                break;

```
            case 3 : 
```

                System.out.println("Enter integer element to insert");

                int num = scan.nextInt() ;

                System.out.println("Enter position");

                int pos = scan.nextInt() ;

                if (pos < 1 || pos > list.getSize() )

                    System.out.println("Invalid position\n");

```
                else
```

                    list.insertAtPos(num, pos);

                break;

```
            case 4 : 
```

                System.out.println("Enter position");

                int p = scan.nextInt() ;

                if (p < 1 || p > list.getSize() )

                    System.out.println("Invalid position\n");

```
                else
```

                    list.deleteAtPos(p);

```
                break;     
```
```
            case 5 : 
```

                System.out.println("Empty status = "+ list.isEmpty());

```
                break;            
```
```
            case 6 : 
```

                System.out.println("Size = "+ list.getSize() +" \n");

                break;

```
            default : 
```

                System.out.println("Wrong Entry \n ");

```
                break;   
```
```
            }    
```
```
            /*  Display List  */ 
```
```
            list.display();
```

            System.out.println("\nDo you want to continue (Type y or n) \n");

            ch = scan.next().charAt(0);

```
 
```

        } while (ch == 'Y'|| ch == 'y');

```
    }
```
```
}
```

Program Explanation

1. The Node class defines a node in the doubly linked list. It has two constructors, one with no arguments and one with three arguments (data, next, and prev).
2. The setLinkNext, setLinkPrev, getLinkNext, getLinkPrev, setData, and getData methods are used to set and get the data and links of a node.
3. The linkedList class defines the doubly linked list. It has a constructor with no arguments that initializes the start and end pointers to null and the size variable to 0. Here are some methods:

The isEmpty method checks if the list is empty.
The getSize method returns the size of the list.
The insertAtStart method inserts a node at the beginning of the list.
The insertAtEnd method inserts a node at the end of the list.
The insertAtPos method inserts a node at a specific position in the list.
The deleteAtPos method deletes a node at a specific position in the list.
The display method displays the status of the list.

4. The main method in the DoublyLinkedList class creates an object of the linkedList class and performs the list operations based on user input.
5. It displays a menu of options, including insertion at the beginning, insertion at the end, insertion at a specific position, deletion at a specific position, and display.
6. The user selects an option by entering a number, and the program calls the corresponding method of the linkedList class to perform the operation.
7. The program continues to display the menu of options until the user chooses to exit.

Program Output:

Doubly Linked List Test
 
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
1
Enter integer element to insert
5
 
Doubly Linked List = 5
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
1
Enter integer element to insert
2
 
Doubly Linked List = 2 <-> 5
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
2
Enter integer element to insert
6
 
Doubly Linked List = 2 <-> 5 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
1
Enter integer element to insert
7
 
Doubly Linked List = 7 <-> 2 <-> 5 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
3
Enter integer element to insert
3
Enter position
3
 
Doubly Linked List = 7 <-> 2 <-> 3 <-> 5 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
4
Enter position
2
 
Doubly Linked List = 7 <-> 3 <-> 5 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
3
Enter integer element to insert
4
Enter position
4
 
Doubly Linked List = 7 <-> 3 <-> 5 <-> 4 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
6
Size = 5
 
 
Doubly Linked List = 7 <-> 3 <-> 5 <-> 4 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
4
Enter position
1
 
Doubly Linked List = 3 <-> 5 <-> 4 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
4
Enter position
2
 
Doubly Linked List = 3 <-> 4 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
4
Enter position
2
 
Doubly Linked List = 3 <-> 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
4
Enter position
1
 
Doubly Linked List = 6
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
4
Enter position
1
 
Doubly Linked List = empty
 
Do you want to continue (Type y or n)
 
y
 
Doubly Linked List Operations
 
1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
Enter your Choice:
5
Empty status = true
 
Doubly Linked List = empty
 
Do you want to continue (Type y or n)
 
n

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Implement Circular Doubly Linked List

» Next - Java Program to Implement Circular Single Linked List

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Practice Programming MCQs
Apply for Computer Science Internship
Check Programming Books

Recommended Articles: