Kulwinder Kaurkulwinder3213

Suppose we are given a Doubly Linked List (DLL) and we need to reverse it so that the pointer currently pointing to the head of the list will point to the tail of the DLL. In this article we will learn about DLLs and then we will go through different methods of reversing a doubly linked list.

```
1
2
3
4
5
6
7
8
9
```

```
// A Singly Linked List Node
class NodeStructure_SLL {
int data;
Node next;
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
```

```
1
2
3
4
5
6
7
8
9
10
11
12
```

```
// A Node Structure for Doubly LinkedList
class NodeStructure_DLL {
public: int data;
Node * next; // ptr to nxt node in node in DLL
Node * prev; // prev Node in DLL
Node(int d) {
data = d;
next = prev = null;
}
};
```

The basic structure of a linked list will have only data and a link to the next node. But, in the case of a doubly linked list it will include data, a link pointing to the previous node, and a second link pointing to the next node. In a single linked list we cannot traverse in a backward direction, but in a doubly linked list that is possible using the link which points to the previous node. This link to the previous node will increase access to elements of the doubly linked list. This also means that a doubly linked list will use more space as the number of fields will be increased by one for each node. We prefer a doubly linked list when space is not an issue and any traversal algorithm has to be performed.

There are two types of doubly linked lists.

A doubly linked list where the pointer to the next node of a last node is pointing to null.

A doubly linked list where the pointer to the next node of the last node is pointing to the head node rather than pointing to null. This makes the DLL circular.

Insertion complexity into singly linked lists is O(N), but in the case of a doubly linked list it becomes O(1) as we also have access to the previous node.

If we are given node (N1) after which we need to insert a new node (N2) in a DLL, then we will take the pointer to the next node of N1 and keep it in the next of N2. Then the address of current Node N1 will be placed in the first (pointer) of N2 and the address of N2 will be placed in the next (pointer) of N1.

**Algorithm:**

Step1 : InsertDLL(Node N2, Node current, Node head) // Current = N1

Step2: N2->next = current.next;

Step3: current.next= N2;

Step4: N2.first= current

Step5: Return Head of DLL

Suppose a pointer pointing to a node is given which has to be deleted from a DLL. First we will check if this is the only node in the DLL. If yes, NULL (Empty DLL) will be returned, otherwise we will take the next (pointer) of the current node and keep it in next (pointer) of the previous node to this. Then we can remove or delete this node or it can be garbage collected.

**Algorithm**

Step1: DeleteNodeDLL(Node head, Node current)

Step2: check if current Node if First Node, only One Node in DLL

If First Node then head= current->next; Then Step 4

If only one Node then head= null, then Step 4

Step3: prevNode=current.prev;

prev.next=current.next;

Step4: Return head

Reversing a DLL is easier than reversing a singly linked list because of the presence of a pointer to the previous node. That means after the end of a function call where we are passing a head pointer to the DLL, we will get a linked list reversed, whose head will be pointing to the last node of passed DLL. In this we will check if the DLL has only one node, then head will be returned, or else we will take a current node and will store its pointer to prev node. Then we will take the next node (N2) of the current node and will make the next pointer of N2 point to the current node. Note we have to update the prev of the current node with temp. Then we can update the current node by making it point to the current’s prev pointer. For better understanding, it is helpful to take a paper and pen and draw a DLL and the process, using the steps accordingly as mentioned in the algorithm.

**Algorithm**

Step 1: function Called reverseDLL(Node head)

Step 2: if head == null or head.next=null GOTO step 6

Step 3: declaration

tempNode with NULL

currentNode pointing to head of DLL

Step 4: Run a Loop until currentNode start pointing to NULL

Step 5: Under Loop

//will store the prev because next Node will be pointed from here as it will become previous to current Node

→temp= current.prev

//current Node should come after its Next Node so

→current.prev=current.next

//current’s previous Node should come after it so will take it and keep it in its Next

//Which we have stored in temp

→current.next=temp

//Current Should be updated for processing next nodes

→current= current.prev

Note:

Reason behind above (current= current.prev) is as the next node has become previous to current node, we will take that node from current’s prev pointer.

Step6: Return temp.prev as It will be New head of reversed DLL

**Java Implementation**

```
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
```

```
public class UserDefDLL {
public Node head;
public Node tail;
static class Node {
//data
int data;
// pointer to nxtNode
Node next;
// pointer to prevNode
Node prev;
}
//Node Class Ends
// Create a Doubly Linked List
public UserDefDLL() {
this.head = null;
this.tail = null;
}
// Method for reversing doubly linked list
public Node reverseDLL() {
//this will store our Previous Node which we will used to make prev Node
//to make it as Next node of Current Node
Node previousNode = null;
Node current = head;
while (current != null) {
previousNode = current.prev;
current.prev = current.next;
current.next = previousNode;
current = current.prev;
}
return previousNode;
}
}
public static void main(String[] args) {
//userDefined Class for Doubly Linked List
UserDefDLL dll = new UserDefDLL();
//insertDLL will insert into DLL
dll.insertDLL(4);
dll.insertDLL(3);
dll.insertDLL(2);
dll.insertDLL(1);
// Now DLL we have is 4->3->2->1
dll = dll.reverseList();
//Now we have reversed DLL
}
}
```

**Code Output**

https://en.wikipedia.org/wiki/Theoretical_Computer_Science_(journal)

https://www.worldscientific.com/doi/abs/10.1142/S0218195911003767

Discuss this article in the forums
Even though computers can perform literally millions of mathematical
comp...

Read More There are two well-known types of linked lists; the singly linked list and the
doubly linked list. In a singly...

Read More About List Interface
List is an interface that belongs to the utility package and can be imported to
our progr...

Read More