Write a C program that uses functions to perform the following:

a) Create a doubly linked list of integers.
b) Delete a given integer from the above doubly linked list.
c) Display the contents of the above list after deletion.

A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
Image result for doubly linked list


Following is representation of a DLL node in C language.
/* Node of a doubly linked list */
struct node
{
int data;
struct node *next; // Pointer to next node in DLL
struct node *prev; // Pointer to previous node in DLL
};
Following are advantages/disadvantages of doubly linked list over singly linked list.

Advantages over singly linked list:
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given. In singly linked list, to delete a node, pointer to the previous node is needed. To get this
previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Disadvantages over singly linked list:
1) Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though.
2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.

Algorithm to implement above program:
Initialize the first and last nodes with NULL values
struct node *first=NULL,*last=NULL,*next,*prev,*cur;

1. Algorithm creating a new node:
Step 1: if the list is empty then first==NULL
Step 2: Create a new node
cur=(struct node*) malloc (sizeof (struct node));
Step 3: Read the content of node
Step 4: Assign new node left and right links to NULL
cur->left=NULL;
cur->right=NULL;
Step 5: Assign new node to first & last node
first=cur
last=cur
Step 6: If the list is not empty call insert function
insert ()
Step 7 : Stop



2. Algorithm for Inserting a new node:
Step 1 : Initialize count c to 1
Step 2 : Create inserting node
cur=(struct node*)malloc(sizeof (struct node));
Step 3: Read the content of node
Step 4: Read the position of insertion
Step 5: Inserting in first position
Check if the pos=1 and first!=NULL
cur->right=first;
cur->left=NULL;
first=cur;
Step 6: Inserting in a given position
next=first;
repeat the steps a to c until c < pos
a. prev=next;
b. next=prev->right;
c. c++;
prev->right=cur;
cur->right=next;
Step 7 : Stop

3. Algorithm for Deleting a node:
Step 1 : Initialize count c to 1
Step 2 : Read the position for deletion
Step 3 : Check if first=NULL
print list is empty
Step 4 : If the list contains single element
Check if pos=1 and first->right=NULL
print deleted element is first->data
Step 5 : Assign first to NULL
first=NULL;
Step 6 : If the list contains more than one element and to delete first element if pos=1 and first->right!=NULL
cur=first;
first=first->right;
cur->right=NULL;
print deleted element is cur->data
free(cur);
Step 7 : If the list contains more than one element and to delete an element at given position
next=first;
repeat the steps a to c until c < pos
a. cur=next;
b.next=next->right;
c. c++;
cur->right=next->right;
next->right=NULL;
next->left=NULL;
print deleted element is next->data
free(next);
Step 8 : Stop



4. Algorithm for Displaying a node:
Step1 : Check if first node is NULL print list is empty
Step2: If first node is not NULL then
cur=first;
repeat the steps a to b until cur!=NULL
a. print cur->data
b. cur=cur->right;
Step3 : Stop


Output of the above program:
Insert() : 11 22 21 10 12
Display () : 11->22->21->10->12
Delete() : 10
Display() : 11->22->21->12


Thanks
Mukesh Rajput
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput