• About WordPress
    • WordPress.org
    • Documentation
    • Support
    • Feedback
  • Log In
  • Register
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment
Cuitutorial
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment

Data Structure

Home » Blog » Doubly Link List

Doubly Link List

  • Posted by saqib
  • Categories Data Structure
  • Date November 11, 2022
  • Comments 0 comment

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.

doubly link list
node doubly link 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

doubly link list
doubly link list
  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
new node in doubly link list
insert new node in doubly link list

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
delete node
delete node in doubly link list

 

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

 

  • Share:
author avatar
saqib

Previous post

Circular Link list Data Structure
November 11, 2022

Next post

Josephus Problem in C++
November 11, 2022

You may also like

Counting Sort
6 December, 2022

Counting sort is a type of Linear Time Sort Counting Sort was invented by H.H.Seward in 1954 All the sorting algorithms introduced so far share an                              …

Insertion Sort
6 December, 2022

Insertion Sort using loop and recursive function complete code On the ith pass we “insert” the ith element A[i] into its rightful place among A[1],A[2],…A[i-1] which were placed in sorted order. After this insertion A[1],A[2],…A[i] are in sorted order. Time …

Bubble Sort using C++
6 December, 2022

Bubble sort using loop and bubble sort in link list One of the simplest sorting methods. The basic idea is to move required value (smallest or highest ) to the top. Compare adjacent values (all elements) Swap values if required …

Leave A Reply Cancel reply

You must be logged in to post a comment.

admin@cuitutorial.com
Facebook-f Twitter Youtube Linkedin Instagram Stack-overflow Pinterest Github Quora Whatsapp
Courses
  • All Courses
  • Past Paper
  • Final year projects
  • Interview Questions
  • Contact
Important Pages
  • Privacy Policy
  • Terms of Service
  • Cookie Policy
Links
  • University Events
  • Team
Education & learning platform for All Computer science subjects
Final year projects
Past Paper
Interview questions
Programming, C/C++, Asp.net/MVC. Android, MySql, Jquery, Ajax, javascript, Php, Html5, Bootstrap4.
NTS, GAT, PPSC, FPSC

Copyright © 2021 | Cuitutorial