May 11, 2022

Reverse Doubly Linked Lists

Kulwinder Kaurkulwinder3213

DURATION

13min

Difference Between a Linked List and Doubly Linked List

Linked List

Doubly Linked List

Structures of Singly and Doubly Linked Lists

Singly 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;
  }
}

Doubly Linked List

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;
  }

};

Structure

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.

Types

There are two types of doubly linked lists.

Open Linked List

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

Circular Linked List

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 Deletion Algorithms for Doubly Linked List

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.

Insertion in DLL

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

Deletion in a Doubly Linked List

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 Doubly Linked List

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