Doubly Link List

Doubly linked list complete code and application

-doubly linked list c++ -doubly linked list code –doubly linked list in data structure -Data structure and algorithm –Data structure and algorithm in C++ -Data structure using C++ -Data structure projects in C++ -Data structure Project idea -Data structure MCQ -Data structure Interview Question –data structure question paper –free course online –past papers -final year projects for computer science with source code -semester project ideas -computer programming -computer science interview questions- tutorial -cui

In a Doubly linked list, each item is allocated space as it is added to the list. A link is kept with each item to the next item and previous item in the list.

Each node of the list has three elements:

The item being stored in the list
A pointer to the next item in the list
A pointer to the previous item in the list

The last node in the list contains a NULL pointer (next) to indicate that it is the end or tail of the list and first node contains NULL pointer for previous pointer to indicate that it is head of the Link List.

Structure corresponding to above will be
struct node
{
char info;
node *next;
node *previous;
};

Basic Operations on doubly link list

Insertion
Deletion
Traversal
Reverse
Search

Applications Of Doubly Linked List

A Deck of cards in a game is a classic example of a doubly linked list. Given that each card in a deck has the previous card and next card arranged sequentially, this deck of cards can be easily represented using a doubly linked list.
Browser history/cache – The browser cache has a collection of URLs and can be navigated using the forward and back buttons is another good example that can be represented as a doubly linked list.
Most recently used (MRU) also can be represented as a doubly linked list.
Other data structures like Stacks, hash table, the binary tree can also be constructed or programmed using a doubly linked list.

Advantages/Disadvantages Over Singly Linked List

Let us discuss some of the advantages and disadvantages of doubly linked list over the singly linked list.

Advantages:

The doubly linked list can be traversed in forward as well as backward directions, unlike singly linked list which can be traversed in the forward direction only.
Delete operation in a doubly-linked list is more efficient when compared to singly list when a given node is given. In a singly linked list, as we need a previous node to delete the given node, sometimes we need to traverse the list to find the previous node. This hits the performance.
Insertion operation can be done easily in a doubly linked list when compared to the singly linked list.

Disadvantages:

As the doubly linked list contains one more extra pointer i.e. previous, the memory space taken up by the doubly linked list is larger when compared to the singly linked list.
Since two pointers are present i.e. previous and next, all the operations performed on the doubly linked list have to take care of these pointers and maintain them thereby resulting in a performance bottleneck.

Inserting a new node before an existing node

Create new node and enter data
Set back ptr of new node of back of location
Set next ptr of the node before location to new node
Se back of location to new node
Set next ptr of new node to location

Delete Node

Set a pointer to the node you want to delete the pointer node
The back ptr of the after location to the node before location
next ptr of node before location to node after location
4. Delete the node pointed by location

class double_llist
{
public:
void create_list(int value);
void add_begin(int value);
void add_after(int value, int position);
void delete_element(int value);
void search_element(int value);
void display_dlist();
void count();
void reverse();
double_llist()
{
p = NULL;
}
};

int main()
{
int choice, element, position;
double_llist dl;
while (1)
{
cout <<endl;
cout << “1.Insert” << endl;
cout << “2.Add after” << endl;
cout << “3.Delete” << endl;
cout << “4.Display” << endl;
cout << “5.Exit” << endl;
cout << “6. add bigning”<<endl;

cout << “Enter your choice : “;
cin >> choice;
cout << endl;
switch (choice)
{
case 1:
cout << “Enter the element: “;
cin >> element;
dl.create_list(element);
cout << endl;
break;
case 2:
cout << “Enter the element: “;
cin >> element;
cout << “Insert Element after postion: “;
cin >> position;
dl.add_after(element, position);
cout << endl;
break;

case 3:
if (p == NULL)
{
cout << “List empty,nothing to delete” << endl;
break;
}
cout << “Enter the element for deletion: “;
cin >> element;
dl.delete_element(element);
cout << endl;
break;
case 4:
dl.display_dlist();
cout << endl;
break;
case 5:
exit(1);
case 6:
cout << “Enter the element: “;
cin >> element;
dl.add_begin(element);
cout << endl;
break;
default:
cout << “Wrong choice” << endl;
}
}
return 0;
}

//Create Operations

void double_llist::create_list(int value)
{
node *q, *t;
t = new node;
t->data = value;
t->next = NULL;
if (p == NULL)
{
t->prev = NULL;
p = t;
}
else
{
q = p;
while (q->next != NULL)
{
q = q->next;
}
q->next = t;
t->prev = q;
}
}

void double_llist::add_after(int value, int pos)
{
if (p == NULL)
{
cout << “List is empty ,First Create the list.” << endl;
return;
}
node *tmp, *q;
int i;
q = p;
for (i = 0; i < pos – 1; i++)
{
q = q->next;
if (q == NULL)
{
cout << “There are less than “;
cout << pos << ” elements.” << endl;
return;
}
}
tmp = new node;
tmp->data = value;
if (q->next == NULL)
{
q->next = tmp;
tmp->next = NULL;
tmp->prev = q;
}
else
{
tmp->next = q->next;
tmp->next->prev = tmp;
q->next = tmp;
tmp->prev = q;
}
cout << “Element Inserted” << endl;
}

void double_llist::add_begin(int value)
{
if (p == NULL)
{
cout << “First Create the list.” << endl;
return;
}
node *t;
t = new node;
t->prev = NULL;
t->data = value;
t->next = p;
p->prev = t;
p = t;
cout << “Element Inserted” << endl;
}

//Delete Operatrions

void double_llist::delete_element(int value)
{
node *tmp, *q;

if (p->data == value)
{
tmp = p;
p = p->next;
p->prev = NULL;
cout << “Element Deleted” << endl;
delete tmp;
return;
}
q = p;
while (q->next->next != NULL)
{

if (q->next->data == value)
{
tmp = q->next;
q->next = tmp->next;
tmp->next->prev = q;
cout << “Element Deleted” << endl;

delete tmp;
return;
}
q = q->next;
}

if (q->next->data == value)
{
tmp = q->next;
free(tmp);
q->next = NULL;
cout << “Element Deleted” << endl;
return;
}
cout << “Element ” << value << ” not found” << endl;
}

//Display List Operations

void double_llist::display_dlist()
{
node *q;
if (p == NULL)
{
cout << “List empty” << endl;
return;
}
q = p;
cout << “The Doubly Link List is :” ;
while (q != NULL)
{
cout << q->data << ” – “;
q = q->next;
}

}

Doubly Link List

Doubly linked list complete code and application

Basic Operations on doubly link list

Applications Of Doubly Linked List

Advantages/Disadvantages Over Singly Linked List

Delete Node

C++ Code for doubly link list

Search within CuiTutorial

Courses

Important Pages

Links