[go: up one dir, main page]
Scribd
Upload
319 views14 pages

Advanced Data Structures: Different Operations On Doubly Linked List

This document discusses operations on doubly linked lists. It provides examples of deleting elements from the beginning, end, and specified positions of a doubly linked list. C code routines are given for each deletion operation as well as for traversing the list in the forward and backward directions. Advantages of doubly linked lists over singly linked lists include ability to traverse in both directions, easier deletion of nodes, and easier memory allocation. Disadvantages are use of extra memory and sequential access only. Applications mentioned include navigation systems, text editors, and playlists.

Uploaded by

Pushpa Latha M
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
319 views14 pages

Advanced Data Structures: Different Operations On Doubly Linked List

This document discusses operations on doubly linked lists. It provides examples of deleting elements from the beginning, end, and specified positions of a doubly linked list. C code routines are given for each deletion operation as well as for traversing the list in the forward and backward directions. Advantages of doubly linked lists over singly linked lists include ability to traverse in both directions, easier deletion of nodes, and easier memory allocation. Disadvantages are use of extra memory and sequential access only. Applications mentioned include navigation systems, text editors, and playlists.

Uploaded by

Pushpa Latha M
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 14

Advanced Data Structures

Different Operations On Doubly Linked List

M.Jeevana Sujitha
Asst Professor

Department of Computer science and Engineering


SRKR Engineering College, Bhimavaram, AP-534204
Objectives

 To implement different operations on doubly linked list


Array implementation

 To understand the pros and cons of doubly linked list when compared to
singly linked list

 To explore various applications of doubly linked list


Deleting an element from the beginning of
the linked list

 Copy the head node in some temporary node.


 Make the second node as the head node.
 The prev pointer of the head node is referenced to NULL.
 Delete the temporary node.
“C” routine for deleting an element from the beginning of the linked list

struct node * temp;


temp = head;
Storing head in temp variable
head = head -> next;
and assigning head->next as head
head -> prev = NULL; and deallocating the memory of
free(temp); previous head node
Deleting an element from the end of the
linked list

 Copy the last node to a temporary node.


 Shift the last node to the second last position.
 Make the last node's next pointer as NULL.
 Delete the temporary node.
“C” routine for deleting an element from the end of the linked list

temp = head;
while(temp != NULL)
traversing to the end of the
{
linked list
temp = temp->next;
}

temp = last; Storing the last node in a


last = last->prev; temporary variable and making
the previous node as a late node
if (last != NULL) and update last node’s next
last->next = NULL; pointer as null and deallocate
free(temp); the memory of deleted node
Deleting an element from the specified a position of a linked list

 Suppose you want to delete the second node from the list.
 Start traversing the linked list from the head until the position = 2 of the
node to be deleted.
 Let the node at the position 2 of the list be temp.
 Assign the next pointer of temp to temp's previous node's next pointer.
 Assign the temp's prev pointer to temp's next node's prev pointer.
 Delete the temp node.
“C” Routine for deleting an element from
the specified position of a linked list

temp = head;
for(i=0; i<position ; i++) Finding the node position
{ which want to delete
temp = temp->next;
}

if(temp != NULL)
Assign the next pointer of node to be
{
deleted to its previous node's prev pointer
temp->prev->next = temp->next; and Assign the prev pointer of the node to
temp->next->prev = temp->prev; be deleted to its next node's next pointer
free(temp);
}
“C” routine for displaying the data in
forward direction

struct Node* temp = root;


printf("Forward: ");
while(temp != NULL)
{
printf("%d ",temp->data);
temp = temp->next;
}
“C” routine for displaying the data in
backward direction

struct Node* temp = root;


while(temp->next != NULL)
{
temp = temp->next;
}
printf("Reverse: ");
while(temp != NULL)
{
printf("%d ",temp->data);
temp = temp->prev;
}
Advantages of Doubly Linked List over
Singly Linked List
 Allows traversal of nodes in both direction which is not possible in singly
linked list

 Deletion of nodes is easy when compared to singly linked list

 Can allocate or de-allocate memory easily when required during its


execution

 It is one of most efficient data structure to implement when traversing in


both direction is required
Disadvantages of Doubly Linked List over
Singly Linked List
 It uses extra memory when compared to singly linked list

 Since elements in memory are stored randomly, hence elements are


accessed sequentially no direct access is allowed
Applications of Doubly Linked List

 Doubly linked list can be used in navigation system where both front and
back navigations are required

 Undo and redo operation in text editor

 Doubly linked link is used to implement rewind and forward operations in


a playlist
Thank you

You might also like