Page 126 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES
P. 126
Unit 8: Operations on Linked List
temp = *head; Notes
while ( (k < position — 1) && temp—>next!=NULL){
temp = temp—>next;
k++;
}
if( temp—>next== NULL) //Insertion at the end
newNode —>next = temp—>next;
newNode—>prev = temp;
temp—>next = newNode;
}
else { //Insertion in the middle
newNode—>next = temp—>next;
newNode—>prev = temp;
temp—>next—>prev = newNode;
temp—>next = newNode;
}
return;
}
8.2.2 Doubly Linked List Deletion
As similar to singly linked list deletion, here also we have three cases:
Deleting the first node
Deleting the last node
Deleting an intermediate node
Deleting the First Node in Doubly Linked List
In this case, first node (current head node) is removed from the list. It can be done in two steps.
Example: The example given below shows the steps for deleting the First Node in
Doubly Linked List.
Create a temporary node which will point to same node as that of head.
Figure 8.19: Create a Temporary Node
Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf
Now, move the head nodes pointer to the next node and change the heads left pointer to
NULL. Then, dispose the temporary node.
LOVELY PROFESSIONAL UNIVERSITY 119
