Doubly Linked list

In a doubly linked list (DLL), each node has two link fields to store information about the one to the next and also about the one ahead of the node. Each node has knowledge of its successor and also its predecessor. In DLL, from every node, the list can be traversed in both the directions. DLLs are also called two-way lists.

Each node of a DLL has three fields in general

The class of a doubly linked list node

class DLL_Node

{

Public:

int Data;

DLL_Node *Prev, *Next;

DLL_Node()

{

Prev = Next = Null;

}

};

Creation of DLL has the same procedure as that of SLL, only difference is that each node must be linked to both its predecessor and successor.

class DList

{

private:

DLL_Node *Head, *Tail;

public:

DList()

{

Head = Tail = Null;

}

:

// member functions

:

};

 

I. Insertion of a node in a doubly Linked List

To insert a node, four links has to be modified as each node points to its predecessor as well as successor.

 

 

To insert Current node,

Current node predecessor should be node1 and node1 successor should be Current node.

Current node successor should be node2 and node1 predecessor should be current node.

 

the statements are:

node1->Next = Current;

node2->Prev = Current;

Current->Next = node2;

Current->Prev = node1;

 

To insert a node at starting

 

Current node (new node) is to be inserted at start of the given DLL, Current node successor should be Head and Head predecessor should be Current node. After making the modification of these links make Current node as Head and the Current node predecessor should be Null.

This is represented by the following statements:

Current->Next = Head;

Head->Prev = Current;

Head = Current;

Current->Prev = Null;

To insert a node at last

If Current is new node to be inserted at last, the tail successor should be current, the Current node predecessor should be tail.

Current node has to be made tail and current node next pointer should be pointing to Null

            tail-> Next=Current;

Current->Prev= tail;

tail = Current

            Current->Next = Null;

 

II. Deletion of a node from a Doubly Linked List

Deleting a node from DLL needs the deleted node’s predecessor, if any to be pointed to the deleted node’s successor.

In addition, the successor, if any, should be set to point to the predecessor node.

 

The core steps involved in this process are the following:

(curr->Prev)->Next = curr->Next;

(curr->Next)->Prev = curr->Prev;

delete curr;