Doubly Linked List

Doubly Linked List

AU: Dec.-15, May-16, Marks 16

• Definition: The doubly linked list has two link fields. One link field is previous pointer and the other link field is that next pointer.

• The typical structure of each node in doubly linked list is like this.

• C Structure

'C' structure of doubly linked list is as follows -

typedef struct node

{

int data;

struct node *prev;

struct node *next;

}dnode;

• Representation

The linked representation of a doubly linked list is

Thus the doubly linked list can traverse in both the directions, forward as well as backwards.

Now, there may be one question in your mind that how do the empty doubly circular linked lists look ? Here is the representation.

That means the prev and next pointers are pointing to the self node.

 

Ex. 3.7.1: Implementation of doubly linked list

/************************************************

Program to perform various operations

such as creation, insertion, deletion, search and display on doubly link lists.

******************************************/

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

typedef struct DLL

{

int data;

struct DLL *next;

struct DLL *prev;

}node;

node *create();

/*

The main function

*/

void main()

{

/* Local declarations */

int choice, val;

char ans;

'node *head;

void display(node *);

node *search(node *,int);

node *insert(node *);

void dele(node **);

head = NULL;

do

{

clrscr();

printf("\nProgram to Perform Various operations on Linked List");

printf("\n1.Create");

printf("\n2.Display");

printf("\n3.Search for an item");

printf("\n4.Insert an element t in a list");

printf("\n5.Delete an element from list");

printf("\n6.Quit");

printf("\nEnter Your Choice ( 1–6) ");

scanf("%d", &choice);

switch( choice)

{

case 1:head = create();

break;

case 2:display(head);

break;

case 3:printf("Enter the element you want to search");

scanf("%d", &val);

search(head, val);

break;

case 4:head-insert(head);

break;

case 5:dele(&head);

break;

case 6:exit(0);

default:clrscr();

printf("Invalid Choice, Try again");

getch();

} while(choice != 6);

}

/*

The create function

*/

node* create()

{

node *temp, *New, *head;

int val, flag;

char ans='y';

node *get_node();

temp = NULL;

flag=TRUE; /* flag to indicate whether a new node is created for the first time or not */

do

{

printf("\nEnter the Element :");

scanf("%d", &val);

/* allocate new node */

New = get_node();

if (New == NULL)

gell edt to

printf("\nMemory is not allocated");

New → data = val;

if (flag==TRUE) /* Executed only for the first time */

{

head=New;

temp=head; /*head is a first node in the DLL*/

flag = FALSE;

}

Else

 {

/* temp keeps track of the most recently created node */

temp→next = New;

New→prev=temp;

temp = New;

}

printf("\n Do you Want to enter more elements? (y/n)"); med

ans=getche();

} while(ans=='y');

printf("\nThe Doubly Linked List is created\n");

getch();

clrscr();

return head;

}

node *get_node()

{

node *temp;

temp=(node *) malloc(sizeof(node) );

temp→next = NULL;

temp→prev=NULL;

return temp;

}

/*

The display function

Input:Address of the first node of the list

Output:Displays the Linked List

Parameter Passing Method : call by value

 Called by main

*/

void display(node *head)

 {

node *temp;

temp=head;

if (temp==NULL)

{

printf("\nThe list is empty\n");

getch();

clrscr();

return;

}

printf("\n List in Forward direction is ...\n");

while (temp != NULL)

{

printf("%d → ", temp→data );

 temp= temp→next;

}

printf("NULL");

temp=head;

while(temp→next!= NULL)

temp-temp→next;//reaching at the last node

printf("\n List in Reverse direction is ...\n");

while (temp != NULL)

{

printf("%d→", temp→data );

 temp=temp → prev;

}

printf("NULL");

getch();

clrscr();

}

/*

The search function

*/

node *search(node *head, int key)

{

node *temp;

int found;

temp = head;

if (temp==NULL)

{

printf("The Linked List is empty\n");

getch();

clrscr();

return NULL;

}

found=FALSE;

while (temp != NULL && found == FALSE)

{

if (temp→data != key)

temp=temp→next;

else

found = TRUE;

}

if (found ==TRUE)

printf("\nThe Element is present in the list\n");

getch();

return temp;

}

else

{

printf("The Element is not present in the list\n");

getch();

return NULL;

}

}

/*

The insert function

Input:Address of starting node of the list

Output:inserts an element into the list

*/

node *insert(node *head)

{

int choice;

node *insert_head(node *);

void insert_after(node *);

void insert_last(node *);

printf("\n 1. Insert a node as a head node");

printf("\n 2. Insert a node as a last node");

printf("\n 3. Insert a node at intermediate position in the linked list");

printf("\n Enter the your choice for insertion of node");

 scanf("%d", &choice);

switch(choice)

{

case 1:head-insert head(head);

break;

case 2:insert_last(head);

break;

case 3:insert_after(head);

break;

}

return head;

}

/* Insertion of node at first position*/

node *insert head(node *head)

{

node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert");

scanf("%d", &New→data);

if(head= NULL)

head=New;

else

{

temp=head;

New→next=temp;

temp→prev=New;

head=New;

}

return head;

}

/*Insertion of node at last position*/

void insert_last (node *head)

{

node *New,*temp;

New=get_node();

printf("\n Enter The element which you want to insert");

scanf("%d", &New→data);

if(head == NULL)

head=New;

else

{

temp=head;

while(temp→next!= NULL)

temp=temp→next;

temp→next=New;

New→prev=temp;

New→next = NULL;

}

}

/*Insertion of node at intermediate position*/

void insert_after(node *head)

{

int key;

node *New,*temp;

New= get_node();

printf("\n Enter The element which you want to insert"); (b-wal

scanf("%d", &New→data);

if(head == NULL)

{

head=New;

}

else

{

printf("\n Enter The element after which you want to insert the node");

scanf("%d", &key);

temp=head;

do

{

if(temp→data==key)

{

New→next=temp→next;

(temp→next)→prev=New;

temp→next=New;

New→prev=temp;

return;

}

else

temp=temp→next;

} while(temp!= NULL);

}

}

*/

The dele function

Input:Address of the starting node of the list

 Output:deletes the desired element from the list

Parameter Passing Method: call by value

void dele(node **head)

{

node *temp, *prev_node;

int key;

temp = *head;

if (temp==NULL)

{

printf("\nThe list is empty\n");

getch();

clrscr();

return;

}

clrscr();

printf("\nEnter the Element you want to delete: ");

scanf("%d", &key);

temp = search(*head,key);

if (temp!= NULL)

{

prev_node = temp->prev;

if (prev_node != NULL)

{

prev_node->next = temp->next;

(temp->next)->prev = prev_node;

free (temp);

}

else

{

*head = temp->next;

(*head)->prev=NULL;

free(temp);

}

printf("\nThe Element is deleted\n");

getch();

clrscr();

}

}

Output

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 1

Enter the Element :10

Do you Want to enter more elements?(y/n)y

Enter the Element :20

Do you Want to enter more elements?(y/n)y

Enter the Element :30

Do you Want to enter more elements?(y/n)y

Enter the Element :40

Do you Want to enter more elements?(y/n)n-

The Doubly Linked List is created

Program to Perform Various operations on Linked List

1. Create

2. Display

3. Search for an item

4. Insert an element in a list

5. Delete an element from list 6. Quit

Enter Your Choice (1-6) 2

List in Forward direction is ...

10-> 20 -> 30 -> 40-> NULL

List in Reverse direction is ...

40-> 30-> 20 -> 10-> NULL

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 3

Enter the element you want to search 30

The Element is present in the list

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 4

1. Insert a node as a head node

2. Insert a node as a last node

3. Insert a node at intermediate position in the linked list

Enter the your choice for insertion of node 1

Enter The element which you want to insert 9

Program to Perform Various operations on Linked List

1.Create

2.Display

3.Search for an item

4.Insert an element in a list

5.Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

List in Forward direction is ...

9-> 10 -> 20 -> 30-> 40 -> NULL

List in Reverse direction is ...

40 -> 30-> 20 -> 10 -> 9-> NULL

Program to Perform Various operations on Linked Lists at

1. Create

2. Display

3.Search for an item

4. Insert an element in a list

5. Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

Enter the Element you want to delete: 20

The Element is present in the list

The Element is deleted

Program to Perform Various operations on Linked List

1.Create

2. Display

3. Search for an item

4. Insert an element in a list

5. Delete an element from list

6. Quit

Enter Your Choice (1-6) 2

List in Forward direction is ...

 9-> 10 -> 30 -> 40 -> NULL

List in Reverse direction is ...

40 -> 30 -> 10 -> 9-> NULL

Logic explanation of DLL program

1. Creation of doubly linked list

Step 1: Initially one variable flag is taken whose value is initialized to TRUE. The purpose of this flag is for making a check on creation of first node. After creating first node reset flag (i.e. assign FALSE to flag)

Now, set flag = FALSE;

Step 2: If head node is created, we can further create a linked list by attaching the subsequent nodes. Suppose, we want to insert a node with value 20 then

Step 3: If user wants to insert a node with a value say 30 then -

Continuing in this fashion doubly linked can be created.

2. Display of DLL

As each of DLL contains two link fields -

Previous link and next link. Hence we can display DLL in forward as well as in reverse direction.

Suppose we have created a DLL as

As now temp becomes NULL, we will come out of the while loop. Hence as a result forward display will be

10->20->30->40

Reverse Display

First of all we must reach at the last node by using while statement.

Finally temp will represent the last node

Now if we set temp = temp → prev, then temp becomes NULL, hence we will come out of while loop. Hence we get the display as

40→30→20→10

3. Insertion of a node in DLL

There are three cases for insertion of a node

1)Insertion of a node at the beginning.

2) Insertion of a node at the end.

3) Insertion of a node at intermediate position.

Case 1: Inserting a node at the beginning

Suppose we want to insert a node with value 9 then

Case 2: Insertion of a node at the end suppose we want to insert a node with value 40 then, first move temp pointer to the last node

Case 3: Inserting a node at the intermediate position

Suppose, we want to insert a node with value 22 after node with value 20, then first search the node with value 20

4. Deletion of node

Suppose we want to delete a node with a value 20 then, first search this node, call it as temp.

After setting these links, free (temp) in order to delete this node physically no thus we get

 

1. Singly and Doubly Linked List Comparison

Review Questions

1. What is meant by doubly linked list? Write the functions to perform the following operations in a doubly linked list.

i) Insert after a specified node ii) Delete the node at a given position iii) Display-from the beginning to end.AU: Dec.-15, Marks 16

2. Illustrate the algorithms to implement the doubly linked list and perform all the operations on the created list.AU May-16, Marks 16