Doubly linked list complete code and application

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

1. Create new node and enter data
2. Set back ptr of new node of back of location
3. Set next ptr of the node before location to new node
4. Se back of location to new node
5. Set next ptr of new node to location

Delete Node

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

 

C++ Code for doubly link list

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int data;
node *next;
node *prev;
}*p;

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

}

 

Related links 

Single link list                 Stack              AVL Trees             Binary search          Counting Sort

Doubly link list               Queue              Graphs                  Bubble Sort               Radix sort

Circular link list              Binary search tree       Hashing         Insertion Sort         Bucket Sort

Josephus Problem          Tree Traversal              Heaps                Quick Sort              Merge Sort

 

At Cui tutorial, courses, past papers and final year projects

#tutorial #cui #pastpaper #courses