Linked list deletion algorithm
Table of Contents
A singly linked list is the most simple type of linked list, with each node containing some data as well as a pointer to the next node. That is a singly linked list allows traversal of data only in one way. There are several linked list operations that allow us to perform different tasks. Show
The basic linked list operations are:
Traverse a Linked ListAccessing the nodes of a linked list in order to process it is called traversing a linked list. Normally we use the traverse operation to display the contents or to search for an element in the linked list. The algorithm for traversing a linked list is given below. Algorithm: TraverseStep 1: [INITIALIZE] SET PTR = HEAD Step 2: Repeat Steps 3 and 4 while PTR != NULL Step 3: Apply process to PTR -> DATA Step 4: SET PTR = PTR->NEXT [END OF LOOP] Step 5: EXIT
The following block of code prints all elements in a linked list in C. struct node *ptr = head; printf("Elements in the linked list are : "); while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; }Inserting Elements to a Linked ListWe will see how a new node can be added to an existing linked list in the following cases.
Insert a Node at the beginning of a Linked listConsider the linked list shown in the figure. Suppose we want to create a new node with data 24 and add it as the first node of the list. The linked list will be modified as follows.
Algorithm: InsertAtBeginningStep 1: IF AVAIL = NULL Write OVERFLOW Go to Step 7 [END OF IF] Step 2: SET NEW_NODE = AVAIL Step 3: SET AVAIL = AVAIL -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET NEW_NODE -> NEXT = HEAD Step 6: SET HEAD = NEW_NODE Step 7: EXITNote that the first step of the algorithm checks if there is enough memory available to create a new node. The second, and third steps allocate memory for the new node. This algorithm can be implemented in C as follows: struct node *new_node; new_node = (struct node*) malloc(sizeof(struct node)); new_node->data = 24; new_node->next = head; head = new_node;Insert a Node at the end of a Linked listTake a look at the linked list in the figure. Suppose we want to add a new node with data 24 as the last node of the list. Then the linked list will be modified as follows.
Algorithm: InsertAtEndStep 1: IF AVAIL = NULL Write OVERFLOW Go to Step 10 [END OF IF] Step 2: SET NEW_NODE = AVAIL Step 3: SET AVAIL = AVAIL -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET NEW_NODE -> NEXT = NULL Step 6: SET PTR = HEAD Step 7: Repeat Step 8 while PTR -> NEXT != NULL Step 8: SET PTR = PTR -> NEXT [END OF LOOP] Step 9: SET PTR -> NEXT = NEW_NODE Step 10: EXITThis can be implemented in C as follows, Insert a Node after a given Node in a Linked listThe last case is when we want to add a new node after a given node. Suppose we want to add a new node with value 24 after the node having data 9. These changes will be done in the linked list.
Algorithm: InsertAfterAnElementStep 1: IF AVAIL = NULL Write OVERFLOW Go to Step 12 [END OF IF] Step 2: SET NEW_NODE = AVAIL Step 3: SET AVAIL = AVAIL -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET PTR = HEAD Step 6: SET PREPTR = PTR Step 7: Repeat Steps 8 and 9 while PREPTR -> DATA != NUM Step 8: SET PREPTR = PTR Step 9: SET PTR = PTR -> NEXT [END OF LOOP] Step 1 : PREPTR -> NEXT = NEW_NODE Step 11: SET NEW_NODE -> NEXT = PTR Step 12: EXITDeleting Elements from a Linked ListLets discuss how a node can be deleted from a linked listed in the following cases.
Delete a Node from the beginning of a Linked listSuppose we want to delete a node from the beginning of the linked list. The list has to be modified as follows:
Algorithm: DeleteFromBeginningStep 1: IF HEAD = NULL Write UNDERFLOW Go to Step 5 [END OF IF] Step 2: SET PTR = HEAD Step 3: SET HEAD = HEAD -> NEXT Step 4: FREE PTR Step 5: EXITThis can be implemented in C as follows, if(head == NULL) { printf("Underflow"); } else { ptr = head; head = head -> next; free(ptr); }Delete last Node from a Linked listSuppose we want to delete the last node from the linked list. The linked list has to be modified as follows:
Algorithm: DeleteFromEndStep 1: IF HEAD = NULL Write UNDERFLOW Go to Step 8 [END OF IF] Step 2: SET PTR = HEAD Step 3: Repeat Steps 4 and 5 while PTR -> NEXT != NULL Step 4: SET PREPTR = PTR Step 5: SET PTR = PTR -> NEXT [END OF LOOP] Step 6: SET PREPTR -> NEXT = NULL Step 7: FREE PTR Step 8: EXITHere we use two pointers PTR and PREPTR to access the last node and the second last node. This can be implemented in C as follows, if(head == NULL) { printf("Underflow"); } else { struct node* ptr = head; struct node* preptr = NULL; while(ptr->next!=NULL){ preptr = ptr; ptr = ptr->next; } preptr->next = NULL; free(ptr); }Delete the Node after a given Node in a Linked listSuppose we want to delete the that comes after the node which contains data 9.
Algorithm: DeleteAfterANodeStep 1: IF HEAD = NULL Write UNDERFLOW Go to Step 10 [END OF IF] Step 2: SET PTR = HEAD Step 3: SET PREPTR = PTR Step 4: Repeat Steps 5 and 6 while PREPTR -> DATA != NUM Step 5: SET PREPTR = PTR Step 6: SET PTR = PTR -> NEXT [END OF LOOP] Step 7: SET TEMP = PTR Step 8: SET PREPTR -> NEXT = PTR -> NEXT Step 9: FREE TEMP Step 10 : EXITImplementation in C takes the following form: if(head == NULL) { printf("Underflow"); } else { struct node* ptr = head; struct node* preptr = ptr; while(ptr->data!=num){ preptr = ptr; ptr = ptr->next; } struct node* temp = ptr; preptr -> next = ptr -> next; free(temp); }SearchFinding an element is similar to a traversal operation. Instead of displaying data, we have to check whether the data matches with the item to find.
Algorithm: SearchStep 1: [INITIALIZE] SET PTR = HEAD Step 2: Repeat Steps 3 and 4 while PTR != NULL Step 3: If ITEM = PTR -> DATA SET POS = PTR Go To Step 5 ELSE SET PTR = PTR -> NEXT [END OF IF] [END OF LOOP] Step 4: SET POS = NULL Step 5: EXITSearch operation can be implemented in C as follows: struct node* ptr = head; struct node* pos = NULL; while (ptr != NULL) { if (ptr->data == item) pos = ptr printf("Element Found"); break; else ptr = ptr -> next; }Advertisements |
