Doubly linked list

Doubly linked list is a complex type of linked list in which a

node contains a pointer to the previous as well as the next
node in the sequence. Therefore, in a doubly linked list, a node
consists of three parts: node data, pointer to the next node in
sequence (next pointer) , pointer to the previous node
(previous pointer). A sample node in a doubly linked list is
shown in the figure.

A doubly linked list containing three nodes having numbers

from 1 to 3 in their data part, is shown in the following image.

In C, structure of a node in doubly linked list can be given as :

1. struct node
2. {
3. struct node *prev;
4. int data;
 5. struct node *next;
6. } ;

The prev part of the first node and the next part of the last
node will always contain null indicating end in each direction.

In a singly linked list, we could traverse only in one direction,

because each node contains address of the next node and it
doesn't have any record of its previous nodes. However, doubly
linked list overcome this limitation of singly linked list.

Due to the fact that, each node of the list contains the address
of its previous node, we can find all the details about the
previous node as well by using the previous address stored
inside the previous part of each node.

Operations on doubly linked list

Node Creation

1. struct node
2. {
3. struct node *prev;
4. int data;
5. struct node *next;
6. };
7. struct node *head, *last;
head=last=NULL;

All the remaining operations regarding doubly linked list are

described in the following table.

S Operation Description
N

1 Insertion at Adding the node into the linked list at beginning.

beginning

2 Insertion at end Adding the node into the linked list to the end.
3 Insertion after Adding the node into the linked list after the specifi
specified node node.

4 Deletion at Removing the node from beginning of the list

beginning

5 Deletion at the end Removing the node from end of the list.

6 Deletion of the node Removing the node which is present just after the n
having given data containing the given data.

7 Searching Comparing each node data with the item to be sear

and return the location of the item in the list if the i
found else return null.

8 Traversing Visiting each node of the list at least once in order t

perform some specific operation like searching, sor
display, etc.
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.
3) We can quickly insert a new node before a given node.
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.

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.
Doubly Linked List : Traverse Bi-directional

1. In Doubly Linked List , each node contain two address

fields .
2. One address field for storing address of next node to be
followed and second address field contain address
of previous node linked to it.
3. So Two way access is possible i.e We can start
accessing nodes from start as well as from last .
4. Like Singly Linked List also only Linear but
Bidirectional Sequential movement is possible.
5. Elements are accessed sequentially , no direct access is
allowed.

Explanation :

1. Doubly Linked List is most useful type of Linked List.

2. In DLL we have facility to access both next as well as
previous data using “next link” and “previous link“.
3. In the above diagram , suppose we are currently on 2nd
node i.e at 4 then we can access next and previous data
using –
 To Access Next Data : curr_node->next->data
To Access Previous Data : curr_node->previous->data

4. We have to always maintain start node , because it is the

only node that is used to keep track of complete linked
list.

Insertion in doubly linked list at beginning

As in doubly linked list, each node of the list contain double

pointers therefore we have to maintain more number of
pointers in doubly linked list as compare to singly linked list.

There are two scenarios of inserting any element into doubly

linked list. Either the list is empty or it contains at least one
element. Perform the following steps to insert a node in doubly
linked list at beginning.

o Allocate the space for the new node in the memory. This
will be done by using the following statement.

1. ptr = (struct node *)malloc(sizeof(struct node));

o Check whether the list is empty or not. The list is empty if
the condition head == NULL holds. In that case, the node
will be inserted as the only node of the list and therefore
the prev and the next pointer of the node will point to
NULL and the head pointer will point to this node.

1. ptr->next = NULL;
2. ptr->prev=NULL;
3. ptr->data=item;
4. head=ptr;
o In the second scenario, the condition head ==
NULL become false and the node will be inserted in
beginning. The next pointer of the node will point to the
existing head pointer of the node. The prev pointer of the
existing head will point to the new node being inserted.
 o This will be done by using the following statements.

1. ptr->next = head;
2. head→prev=ptr;

Since, the node being inserted is the first node of the list and
therefore it must contain NULL in its prev pointer. Hence assign
null to its previous part and make the head point to this node.

1. ptr→prev =NULL
2. head = ptr
3. tail = ptr

Algorithm :

o Step 1: IF ptr = NULL

Write OVERFLOW
Go to Step 9
[END OF IF]

o Step 2: SET NEW_NODE = ptr

o Step 3: SET ptr = ptr -> NEXT
o Step 4: SET NEW_NODE -> DATA = VAL
o Step 5: SET NEW_NODE -> PREV = NULL
o Step 6: SET NEW_NODE -> NEXT = START
o Step 7: SET head -> PREV = NEW_NODE
o Step 8: SET head = NEW_NODE
o Step 10: EXIT
 C Function

1. struct node
2. {
3. int data;
4. struct node *next;
5. struct node *prev;
6. };
7. struct node *head, *tail;
8. head=NULL;
9. tail=NULL;
10. void insertbeginning(int item)
11. {
12.
13. struct node *ptr = (struct node *)malloc(sizeof(struct n
ode));
14. if(ptr == NULL)
15. {
16. printf("\nOVERFLOW");
17. }
18. else
19. {
20.
21.
22. if(head==NULL)
23. {
24. ptr->next = NULL;
25. ptr->prev=NULL;
26. ptr->data=item;
27. head=ptr;
28. tail=ptr;
29. }
30. else
31. {
32. ptr->data=item;
33. ptr->prev=NULL;
34. ptr->next = head;
35. head->prev=ptr;
36. head=ptr;
37.
38. }
39. }
40.
41. }

Insertion in doubly linked list at the end

In order to insert a node in doubly linked list at the end, we must make sure whether
the list is empty or it contains any element. Use the following steps in order to insert
the node in doubly linked list at the end.

o Allocate the memory for the new node. Make the pointer ptr point to the new
node being inserted.

1. ptr = (struct node *) malloc(sizeof(struct node));

o Check whether the list is empty or not. The list is empty if the condition head
== NULL holds. In that case, the node will be inserted as the only node of the
list and therefore the prev and the next pointer of the node will point to NULL
and the head pointer will point to this node.

1. ptr->next = NULL;
2. ptr->prev=NULL;
3. ptr->data=item;
4. head=ptr;
5. tail=ptr;

o In the second scenario, the condition head == NULL become false. The new
node will be inserted as the last node of the list..
o tail->next=ptr;
o ptr->next=NULL;
o ptr->prev=tail;

o tail=ptr;

1. struct node
2. {
3. int data;
4. struct node *next;
5. struct node *prev;
6. };
7. struct node *head,*tail;
8. void insertlast(int item)
9. {
10.
11. struct node *ptr = (struct node *) malloc(sizeof(struct node));
12. struct node *temp;
13. if(ptr == NULL)
14. {
15. printf("\nOVERFLOW");
16.
17. }
18. else
19. {
20.
21. ptr->data=item;
22. if(head == NULL)
23. {
24. ptr->next = NULL;
25. ptr->prev = NULL;
26. head = ptr;
 tail = ptr;
27. }
28. else
29. { tail->next=ptr;
30. ptr->next=NULL;
31. ptr->prev=tail;
32.
33. tail=ptr;
34.
35. }
36.
37. printf("\nNode Inserted\n");
38.
39. }
40. }

41. Traverse to N-1 node in the list. Where N is the position to insert.
Say temp now points to N-1 node.
th
42. Create a newNode that is to be inserted and assign some data to its data field.

43. Connect the next address field of newNode with the node pointed by next
address field of temp node.

44. Connect the previous address field of newNode with the temp node.
45. Check if temp->next is not NULL then, connect the previous address field of
node pointed by temp.next to newNode.

46. Connect the next address field of temp node to newNode i.e. temp->next will
now point to newNode.

47. Final list

Program to insert a new node at the middle of doubly
linked list.

struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head, *last;
head=last=NULL;

void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
if (head==NULL )
 printf("create the list first");

for(i=1;i<=loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next->prev=ptr;

temp->next = ptr;
printf("\nnode inserted\n");
}
}

Deletion at beginning
Deletion in doubly linked list at the beginning is the simplest operation. We just need
to copy the head pointer to pointer ptr and shift the head pointer to its next.

1. Ptr = head;
2. head = head → next;

now make the prev of this new head node point to NULL. This will be done by using
the following statements.

1. head → prev = NULL

Now free the pointer ptr by using the free function.

1. free(ptr)
 Algorithm
o STEP 1: IF HEAD = NULL

WRITE UNDERFLOW
GOTO STEP 6

o STEP 2: SET PTR = HEAD

o STEP 3: SET HEAD = HEAD → NEXT

o STEP 4: SET HEAD → PREV = NULL

o STEP 5: FREE PTR

o STEP 6: EXIT

1. struct node
2. {
3. int data;
4. struct node *next;
5. struct node *prev;
6. };
7. struct node *head, *tail;
8.
9.
10. void beginning_delete()
11. {
12. struct node *ptr;
13. if(head == NULL)
14. {
15. printf("\n UNDERFLOW\n");
16. }
17. else if(head->next == NULL)
18. {
19.
20. free(head);
21. head = NULL;
22. tail=NULL;
23.
24. printf("\nNode Deleted\n");
25. }
26. else
27. {
28. ptr = head; head=head->next;
29. head = head -> next; free(head->prev);
30. head -> prev = NULL; head->prev=NULL;
31. free(ptr);
32. printf("\nNode Deleted\n");
33. }
34. }
 Deletion in doubly linked list at the end

1. struct node
2. {
3. int data;
4. struct node *next;
5. struct node *prev;
6. };
7. struct node *head,*tail,*temp;
8. void last_delete()
9. {
10. struct node *ptr;
11. if(head == NULL)
12. {
13. printf("\n UNDERFLOW\n");
14. }
15. else if(head->next == NULL)
16. { free(head);
17. head = NULL;
18. tail=NULL;
19.
20. printf("\nNode Deleted\n");
21. }
22. else
23. {
24. ptr=tail; tail=tail->prev;
25. tail=tail->prev; free(tail->next);
26. tail->next=NULL; tail->next=NULL;
27. free(ptr);
28.
29. printf("\nNode Deleted\n");
30. }
31. }

Deletion at the middle (steps)

Deletion at middle

Steps

 Traverse till the target node

 create a node called the previous storing previous node of the target node

 Assign previous node’s next pointer to the next node of the target node

 For the next node of the target node, its previous pointer is assigned to the targets

node’s previous node’s address

 Free memory of target node

1. void deletion_specified()
2. {
3. struct node *ptr, *temp;
4. int val;
5. printf("\n Enter the data after which the node is to be deleted
: ");
6. scanf("%d", &val);
7. ptr = head;
8. while(ptr -> data != val)
9. ptr = ptr -> next;
10. if(ptr == NULL)
11. {
12. printf("\nCan't delete last node\n");
13. }
14. else
15. {
16. ptr->next->prev=ptr->prev;
17. ptr->prev->next=ptr->next;
18. free(ptr);
19. printf("\nnode deleted\n");
20. }
21. }

Display contents of the doubly linked list

22. void display() [ forward]

23. {
24. struct node *ptr;
25. if (head==NULL)
26. printf(" list is empty");
27. printf("\n printing values...\n");
28. ptr = head;
29. while(ptr != NULL)
30. {
31. printf("%d\n",ptr->data);
32. ptr=ptr->next;
33. }
34. }
35. void display()
36. {
37. struct node *ptr;
38. if (head==NULL)
39. printf(" list is empty");
40. printf("\n printing values...\n");
41. ptr=tail;
42. while(ptr != NULL)
43. {
44. printf("%d\n",ptr->data);
45. ptr=ptr->prev;
46. }
47. }

STACK USING LINKED LIST

The major problem with the stack implemented using an array is, it works only for a

fixed number of data values. That means the amount of data must be specified at

the beginning of the implementation itself. Stack implemented using an array is not

suitable, when we don't know the size of data which we are going to use. A stack

data structure can be implemented by using a linked list data structure. The stack

implemented using linked list can work for an unlimited number of values. That

means, stack implemented using linked list works for the variable size of data. So,

there is no need to fix the size at the beginning of the implementation. The Stack

implemented using linked list can organize as many data values as we want.

In linked list implementation of a stack, every new element is inserted as 'top'

element. That means every newly inserted element is pointed by 'top'. Whenever we

want to remove an element from the stack, simply remove the node which is pointed

by 'top' by moving 'top' to its previous node in the list. The next field of the first

element must be always NULL.

Example

In the above example, the last inserted node is 99 and the first inserted node is 25.

The order of elements inserted is 25, 32,50 and 99.

Stack Operations using Linked List

To implement a stack using a linked list, we need to set the following things before

implementing actual operations.

 Step 1 - Include all the header files which are used in the program. And

declare all the user defined functions.

 Step 2 - Define a 'Node' structure with two members data and next.

 Step 3 - Define a Node pointer 'top' and set it to NULL.

 Step 4 - Implement the main method by displaying Menu with list of

operations and make suitable function calls in the main method.

push(value) - Inserting an element into the Stack

We can use the following steps to insert a new node into the stack...

 Step 1 - Create a newNode with given value.

  Step 2 - Check whether stack is Empty (top == NULL)

 Step 3 - If it is Empty, then set newNode → next = NULL.

 Step 4 - If it is Not Empty, then set newNode → next = top.

 Step 5 - Finally, set top = newNode.

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

 Step 1 - Check whether stack is Empty (top == NULL).

 Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not

possible!!!" and terminate the function

 Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to

'top'.

 Step 4 - Then set 'top = top → next'.

 Step 5 - Finally, delete 'temp'. (free(temp)).

display() - Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...

 Step 1 - Check whether stack is Empty (top == NULL).

 Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the

function.

 Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize

with top.

 Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the

same until temp reaches to the first node in the stack. (temp → next !

= NULL).

 Step 5 - Finally! Display 'temp → data ---> NULL'.

 struct Node
 {
 int data;
 struct Node *next;
 }*top = NULL;
 void push(int value)
 {
 struct Node *newNode;
 newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = value;
 if(top == NULL)
 newNode->next = NULL;

 else
 newNode->next = top;
 top = newNode;
 printf("\nInsertion is Success!!!\n");
 }
 void pop()
 {
 if(top == NULL)
 printf("\nStack is Empty!!!\n");
 else{
 struct Node *temp = top;
 printf("\nDeleted element: %d", temp->data);
 top = top->next;
 free(temp);
 }
 }
 void display()
 {
 if(top == NULL)
 printf("\nStack is Empty!!!\n");
 else{
 struct Node *temp = top;
 while(temp != NULL){
  printf("%d--->",temp->data);
 temp = temp -> next;
 } }

Linked List implementation of Queue

the array implementation can not be used for the large scale applications where the
queues are implemented. One of the alternative of array implementation is linked list
implementation of queue.

The storage requirement of linked representation of a queue with n elements is o(n)

while the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the
link part. Each element of the queue points to its immediate next element in the
memory.

In the linked queue, there are two pointers maintained in the memory i.e. front
pointer and rear pointer. The front pointer contains the address of the starting
element of the queue while the rear pointer contains the address of the last element
of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and
rear both are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

1.

struct node
2. {
3. int data;
4. struct node *next;
5. };
6. struct node *front;
7. struct node *rear;
front=rear=NULL
 Operation on Linked Queue
There are two basic operations which can be implemented on the linked queues. The
operations are Insertion and Deletion.

Insert operation
The insert operation append the queue by adding an element to the end of the
queue. The new element will be the last element of the queue.

Firstly, allocate the memory for the new node ptr by using the following statement.

1. Ptr = (struct node *) malloc (sizeof(struct node));

There can be the two scenario of inserting this new node ptr into the linked queue.

In the first scenario, we insert element into an empty queue. In this case, the
condition front = NULL becomes true. Now, the new element will be added as the
only element of the queue and the next pointer of front and rear pointer both, will
point to NULL.

1. ptr -> data = item;

2. if(front == NULL)
3. {
4. front = ptr;
5. rear = ptr;
6. front -> next = NULL;
7. rear -> next = NULL;
8. }

In the second case, the queue contains more than one element. The condition front
= NULL becomes false. In this scenario, we need to update the end pointer rear so
that the next pointer of rear will point to the new node ptr. Since, this is a linked
queue, hence we also need to make the rear pointer point to the newly added
node ptr. We also need to make the next pointer of rear point to NULL.

1. rear -> next = ptr;

2. rear = ptr;
3. rear->next = NULL;

In this way, the element is inserted into the queue.

Step 1: Allocate the space for the new node PTR

o Step 2: SET PTR -> DATA = VAL

 o Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]

o Step 4: END

Algorithm

1. void insert( int item )

2. {
3. struct node *ptr;
4.
5. ptr = (struct node *) malloc (sizeof(struct node));
6. if(ptr == NULL)
7. {
8. printf("\nOVERFLOW\n");
9. return;
10. }
11. else
12. {
13. ptr -> data = item;
14. if(front == NULL)
15. {
16. front = ptr;
17. rear = ptr;
18.
19. rear -> next = NULL;
20. }
21. else
22. {
23. rear -> next = ptr;
24. rear = ptr;
25. rear->next = NULL;
26. }
27. }
28. }

Deletion
Deletion operation removes the element that is first inserted among all the queue
elements. Firstly, we need to check either the list is empty or not. The condition front
== NULL becomes true if the list is empty, in this case , we simply write underflow
on the console and make exit.

Otherwise, we will delete the element that is pointed by the pointer front. For this
purpose, copy the node pointed by the front pointer into the pointer ptr. Now, shift
the front pointer, point to its next node and free the node pointed by the node ptr.
This is done by using the following statements.

1. ptr = front;
2. front = front -> next;
3. free(ptr);

o Step 1: IF FRONT = NULL

Write " Underflow "
Go to Step 5
[END OF IF]

o Step 2: SET PTR = FRONT

o Step 3: SET FRONT = FRONT -> NEXT

o Step 4: FREE PTR

o Step 5: END

Algorithm

1. void delete ()
2. { struct node *ptr;
3. if(front == NULL)
4. {
5. printf("\nUNDERFLOW\n");
6. return;
7. }
8. else
9. {
10. ptr = front;
11. printf( " the deleted data is %d", front->data);
12. front = front -> next;
13. free(ptr);
14. }
15. }
Algorithm
8. void display()
9. {
10. struct node *ptr;
11. ptr = front;
12. if(front == NULL)
13. {
14. printf("\nEmpty queue\n");
15. }
16. else
17. { printf("\nprinting values .....\n");
18. while(ptr != NULL)
19. {
20. printf("\n%d\n",ptr -> data);
21. ptr = ptr -> next;
22. }
23. }
24. }