How to add nodes to the beginning, end and middle of a doubly linked list?

Posted on | In | Views

Question

How to add nodes to the beginning, end and middle of a doubly linked list?

1. Illustration and Steps

1.1. Add nodes to the beginning of the doubly linked list

Illustration (GeeksforGeeks, 2022):

Add nodes to the beginning of the doubly linked list

Steps:

1
2
3
4
5
6
7
8
//Step1: newNode->next set to head
newNode.next = head;
//Step2: head->previous set to newNode
head.previous = newNode;
//Step3: newNode becomes new head
head = newNode;
//Step4: head's previous point to null
head.previous = null;

1.2. Add nodes to the end of the doubly linked list

Illustration (GeeksforGeeks, 2022):

Add nodes to the end of the doubly linked list

Steps:

1
2
3
4
5
6
7
8
//Step1: tail->next set to newNode
tail.next = newNode;
//Step2: newNode->previous set to tail
newNode.previous = tail;
//Step3: newNode becomes new tail
tail = newNode;
//Step4: tail's next point to null
tail.next = null;

1.3. Add nodes in between the doubly linked list

Illustration (GeeksforGeeks, 2022):

Add nodes in between the doubly linked list

Steps:

1
2
3
4
5
6
7
8
9
10
//Step1: newNode->next set to preNode.next
newNode.next = preNode.next;
//Step2: preNode->next set to newNode
preNode.next = newNode;
//Step3: newNode->previous set to preNode
newNode.previous = preNode;
//Step4: newNode->next->previous set to newNode
if (newNode.next != null) {
    newNode.next.previous = newNode;
}

2. Program

2.1. Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/**
 * This program adds nodes to the head, tail, and middle of a doubly linked list.
 *
 * Reference1: https://www.softwaretestinghelp.com/doubly-linked-list-in-java/
 * Reference2: https://www.geeksforgeeks.org/doubly-linked-list/
 *
 * @author Zhiyao He
 */
public class DoublyLinkedList {
    //a node class for doubly linked list
    class Node {
        int item;
        Node previous;
        Node next;

        public Node(int item) {
            this.item = item;
        }
    }

    //initially, heade and tail is set to null
    Node head, tail = null;

    //add a node at the end of the list
    public void addTailNode(int item) {
        //Create a new node
        Node newNode = new Node(item);

        //if list is empty, head and tail points to newNode
        if (head == null) {
            head = tail = newNode;
            //head's previous will be null
            head.previous = null;
            //tail's next will be null
            tail.next = null;
        } else {
            //Step1: tail->next set to newNode
            tail.next = newNode;
            //Step2: newNode->previous set to tail
            newNode.previous = tail;
            //Step3: newNode becomes new tail
            tail = newNode;
            //Step4: tail's next point to null
            tail.next = null;
        }
    }

    //add a node at the beginning of the list
    public void addHeadNode(int item) {
        //Create a new node
        Node newNode = new Node(item);

        //if list is empty, head and tail points to newNode
        if (head == null) {
            head = tail = newNode;
            //head's previous will be null
            head.previous = null;
            //tail's next will be null
            tail.next = null;
        } else {
            //Step1: newNode->next set to head
            newNode.next = head;
            //Step2: head->previous set to newNode
            head.previous = newNode;
            //Step3: newNode becomes new head
            head = newNode;
            //Step4: head's previous point to null
            head.previous = null;
        }
    }

    //add a node in between the list
    public void addIntermediateNode(int item, Node preNode) {
        //create a new node
        Node newNode = new Node(item);

        //check if the given prev_node is NULL
        if (preNode == null) {
            System.out.println("The given previous node cannot be NULL ");
            return;
        } else {
            //Step1: newNode->next set to preNode.next
            newNode.next = preNode.next;
            //Step2: preNode->next set to newNode
            preNode.next = newNode;
            //Step3: newNode->previous set to preNode
            newNode.previous = preNode;
            //Step4: newNode->next->previous set to newNode
            if (newNode.next != null) {
                newNode.next.previous = newNode;
            }
        }
    }

    //print all the nodes of doubly linked list
    public void printNodes() {
        //node current will point to head
        Node current = head;
        if (head == null) {
            System.out.println("Doubly linked list is empty");
            return;
        }
        //System.out.println("Nodes of doubly linked list: ");
        while (current != null) {
            //Print each node and then go to next.
            System.out.print(current.item + " ");
            current = current.next;
        }
        System.out.println();
        System.out.println();
    }

    public static void main(String[] args) {
        //create a DoublyLinkedList object
        DoublyLinkedList dl_List = new DoublyLinkedList();

        //add nodes to the end of the linked list,
        //and it becomes 6->7->10
        dl_List.addTailNode(6);
        dl_List.addTailNode(7);
        dl_List.addTailNode(10);

        //print the nodes of DoublyLinkedList
        System.out.println("Add nodes at the end of the linked list:");
        dl_List.printNodes();

        //Add nodes to the head of the linked list,
        // and it becomes 1->2->3->4->5->6->7->10
        dl_List.addHeadNode(5);
        dl_List.addHeadNode(4);
        dl_List.addHeadNode(3);
        dl_List.addHeadNode(2);
        dl_List.addHeadNode(1);

        //print the nodes of DoublyLinkedList
        System.out.println("Add nodes at the beginning of the linked list:");
        dl_List.printNodes();

        //Add nodes in between the linked list,
        //and it becomes 1->2->3->4->5->6->7->8->9->10
        dl_List.addIntermediateNode(9, dl_List.tail.previous);
        dl_List.addIntermediateNode(8, dl_List.tail.previous.previous);

        //print the nodes of DoublyLinkedList
        System.out.println("Add nodes in between the linked list:");
        dl_List.printNodes();
    }
}

2.2. Outputs

1
2
3
4
5
6
7
8
9
10
Add nodes at the end of the linked list:
6 7 10 

Add nodes at the beginning of the linked list:
1 2 3 4 5 6 7 10 

Add nodes in between the linked list:
1 2 3 4 5 6 7 8 9 10 

Process finished with exit code 0

Word count: 738

References

1.GeeksforGeeks. (2022). Doubly Linked List | Set 1 (Introduction and Insertion).
https://www.geeksforgeeks.org/doubly-linked-list/

2.SoftwareTestingHelp. (2022). Doubly Linked List In Java – Implementation & Code Examples.
https://www.softwaretestinghelp.com/doubly-linked-list-in-java/

​

This is the ending, thanks for reading.
Exclusive for Local Squires and Tyrants