Let's see deletion in simple linked list
In the previous post we saw insertion in simple linked list in this post we will be looking at :
1. Deletion at head
2. Deletion in between
2a. By index
2b. By value of data
2c. By address of node
3. Deletion at the end
Let's look at each one by one, starting with deletion at head. Before making function lets understand the logic, how we will be implementing this.
We want to delete the head node so,
>>> We can also say that we want to make the send node as the head node, because if we call second node to be the head node then our linked list will start from this new head and
>>> Our old first node is excluded from the linked list. So we can say that its automatically deleted.
>>> For this we use the statement
head = head -> nextAdd;
>>> Now being a good developer it's our duty to free up the allocated memory in heap once we are not using it. This makes our program very efficient in using memory. So to free up memory we write this simple statement
free(pointer);
>>> But before this and in fact before redefining new head we need to assign value of old head to this pointer.
So finally we write :
struct Node *pointer = head;
head = head -> nextAdd;
free(pointer);
return head;
>>> we return the head and yes we are done with deletion of head now, here is the function for it :
// deletion of head node
// by linking second node as head
struct Node * deleteAtHead(struct Node *head){
struct Node *point = head; // pointing at old head
head = head -> nextAdd; // pointing head to next address of old head
free(point);
return head;
}
Now let's look at the third type of deletion first because its simpler...
To delete at the end we do not know the address of the last node, right ? So as we did in insertion
>>> We will make a runner pointer and start it from head and move ahead till we find the last node.
Now after this step, I have two sets of method both are equally cost efficient in terms of time & space complexity , I will be explaining both and you can use any of these methods according to your convenience :
Method 1 :
>>> once we are done with creating 1st runner, we need the address of node just before the last node tp re define the nextAdd = NULL, and free up our previous last node... But we have no track of node before last node....
>>> In such case we create a runner2 and start it from head. Now when we are moving the first runner to last node, we also count the number of times we have moved the runner, suppose we moved the 1st runner 5 times. So its obvious that we need to move runner2 4 times to reach the node just before last node.
>>> Now, we have runner at last node and runner2 at node just before the last node, we need to simple redefine
runner2 -> nextAdd = NULL;
Thus second last node pointed by runner2 becomes our last node as it's next is NULL. We have no use of the old last node so we free up memory and return head.
free(runner);
return(head);
Here is the function for this method :
// deletion of last node
// by linking next address of pen-ultimate node
// as NULL
struct Node * deleteLastNode(struct Node *head){
struct Node *point1 = head; // pointing at head
int index = 0;
while (point1 -> nextAdd != NULL){
point1 = point1 -> nextAdd;
index++;
}
struct Node *point2 = head;
int i = 0;
while (i != index - 1){
point2 = point2 -> nextAdd;
i++;
}
point2 -> nextAdd = NULL; // pointing head to next address of old head
free(point1);
return head;
}
Method 2 :
>>> The first step is the same, creating runner, and moving it ahead starting from head to the last node.
>>> here we will also keep track of the node just before the runner.
>>> we will create a pointer
struct Node *prevOfRunner;
It will store the address of node just before runner, by assigning to it the current value of runner and moving the runner to next address, till runner reaches the last Node. We will do this in a while loop
while(runner -> nextAdd != NULL){
prevOfRunner = runner;
runner = runner -> nextAdd;
}
>>> So when runner reaches last node prevOfRunner will be just before last node as name suggests.
>>> Again the proccess is same as 1st method.
prevOfRunner -> nextAdd = NULL;
free(runner);
return head;
>>> Here is the function for 2nd method ( Note : code for 1st method is commented on here)
// deletion of last node
// by linking next address of pen-ultimate node
// as NULL
struct Node * deleteLastNode(struct Node *head){
/*struct Node *point1 = head; // pointing at head
int index = 0;
while (point1 -> nextAdd != NULL){
point1 = point1 -> nextAdd;
index++;
}
struct Node *point2 = head;
int i = 0;
while (i != index - 1){
point2 = point2 -> nextAdd;
i++;
}
point2 -> nextAdd = NULL; // pointing head to next address of old head
free(point1);
return head;*/
struct Node *runner = head; // pointing at head
struct Node *prevOfRunner = runner;
while(runner -> nextAdd != NULL){
prevOfRunner = runner;
runner = runner -> nextAdd;
}
prevAdd -> nextAdd = NULL;
free(runner);
return head;
}
Now let's discuss deletion in between:
1. Deletion By index :
1. Deletion By index :
>>> Here we already know the index, so using this value we can directly decide how many times do we have move the runner1, as we have to stop at one node previous to deletion node,
>>> We move runner index - 1 times, after deletion we will have to free up the memory so we create runner2, which will already store next address of runner1, before deletion takes place.
>>> Moral of the story : runner2 is at node to be deleted and runner1 is at node just before runner2, so far you might have observed that deletion of node is just excuding the deletion node out of linked list.
We will re-defined
runner1->nextAdd = runner2->nextAdd ;
(see the image to understand better)
Now,
free(runner2);
return(head);
// deletion of a node by its index
struct Node * deleteByIndex(struct Node *head, int index){
struct Node *runner1 = head;
struct Node *runner2;
int i = 0;
while(i != index -1){
runner1 = runner1 -> nextAdd;
i++;
}
runner2 = runner1 -> nextAdd;
runner1 -> nextAdd = runner2 -> nextAdd;
free(runner2);
return head;
}
2. Next we will discuss deletion by value of data :
>>> again have runner1 = head & runner2 = runner1 -> nextAdd;
>>> We check data to be deleted with data in runner2, which will be later pointing to deletion node and runner1 will be just before it
while( runner2->data != value to be delted)
{
Move runner2 ahead.
}
>>> Then delete the required node by same steps
runner1 -> nextAdd = runner2 -> nextAdd;
free(runner2);
return head;
Here is the function for this :
// deletion of a node by a value
struct Node * deleteByValue(struct Node *head, int delValue){
int index = 0;
struct Node *runner1 = head;
struct Node *runner2 = runner1 -> nextAdd;
while (runner2 -> data != delValue)
{
if(runner2 -> nextAdd == NULL) // reached last node and couldnt find data to be deleted !!!
{
printf("Alert !!! Data %d absent\nreached last node and couldn't find data to be deleted !!!\nDeletion faied !!!\n",delValue);
return head;
}
runner2 = runner2 -> nextAdd;
runner1 = runner1 -> nextAdd;
}
if (runner2 -> data == delValue){
runner1 -> nextAdd = runner2 -> nextAdd;
free(runner2);
}
return head;
}
Here is the complete code where we have both insertion and deletion in simple linked list
#include <stdio.h>
#include <stdlib.h>
//Compiler version gcc 6.3.0
/*
SAMPLE LINKED LIST :
egAddr. 101 285 121 662 358
|2|285| -> |8|121| -> |3|662| -> |6|358| -> |10|NULL| -> NULL
names head one two three four
*/
struct Node{
int data;
struct Node *nextAdd;
};
// traversing through linked list
void traverse(struct Node *pointer){
printf(" head\n ↓\n ");
while(pointer != NULL){
printf("[%d] -> ",pointer -> data);
pointer = pointer -> nextAdd;
}
printf("NULL");
}
// various ways of insertion
// case 1
// insertAtFirst function
// to insert at index 0
struct Node * insertAtFirst(struct Node *head, int newData){
struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
newNode -> nextAdd = head;
newNode -> data = newData;
head = newNode;
return head;
}
// case 2
// insertAtIndex function
// to insert from index 0 to last
struct Node * insertAtIndex(struct Node *head, int newData, int index){
if(index == 0){
struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
newNode -> nextAdd = head;
newNode -> data = newData;
head = newNode;
return head;
}
else{
struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
newNode -> data = newData;
struct Node * runner = head;
int i = 0;
while (i != index - 1){
runner = runner -> nextAdd;
i++;
}
newNode -> nextAdd = runner -> nextAdd;
runner -> nextAdd = newNode;
return head;
}
}
// case 3
// insertAtEnd function
// to insert at last index
struct Node * insertAtEnd(struct Node *head, int newData){
struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
newNode -> data = newData;
struct Node * runner = head;
// int i = 0;
while (runner -> nextAdd != NULL){
runner = runner -> nextAdd;
//i++;
}
newNode -> nextAdd = runner -> nextAdd;
runner -> nextAdd = newNode;
return head;
}
// various ways of deletion
// case 1
// deletion of head node
// by linking second node as head
struct Node * deleteAtHead(struct Node *head){
struct Node *pointer = head; // pointing at old head
head = head -> nextAdd; // pointing head to next address of old head
free(pointer);
return head;
}
// case 2
// deletion of last node
// by linking next address of pen-ultimate node
// as NULL
struct Node * deleteLastNode(struct Node *head){
/*struct Node *point1 = head; // pointing at head
int index = 0;
while (point1 -> nextAdd != NULL){
point1 = point1 -> nextAdd;
index++;
}
struct Node *point2 = head;
int i = 0;
while (i != index - 1){
point2 = point2 -> nextAdd;
i++;
}
point2 -> nextAdd = NULL; // pointing head to next address of old head
free(point1);
return head;*/
struct Node *runner = head; // pointing at head
struct Node *prevOfRunner = runner;
while(runner -> nextAdd != NULL){
prevOfRunner = runner;
runner = runner -> nextAdd;
}
prevOfRunner -> nextAdd = NULL;
free(runner);
return head;
}
// case 3
// deletion of a node by its index
struct Node * deleteByIndex(struct Node *head, int index){
struct Node *runner1 = head;
struct Node *runner2;
int i = 0;
while(i != index -1){
runner1 = runner1 -> nextAdd;
i++;
}
runner2 = runner1 -> nextAdd;
runner1 -> nextAdd = runner2 -> nextAdd;
free(runner2);
return head;
}
// case 4
// deletion of a node by a value
struct Node * deleteByValue(struct Node *head, int delValue){
int index = 0;
struct Node *runner1 = head;
struct Node *runner2 = runner1 -> nextAdd;
while (runner2 -> data != delValue)
{
if(runner2 -> nextAdd == NULL) // reached last node and couldnt find data to be deleted !!!
{
printf("Alert !!! Data %d absent\nreached last node and couldn't find data to be deleted !!!\nDeletion faied !!!\n",delValue);
return head;
}
runner2 = runner2 -> nextAdd;
runner1 = runner1 -> nextAdd;
}
if (runner2 -> data == delValue){
runner1 -> nextAdd = runner2 -> nextAdd;
free(runner2);
}
return head;
}
int main()
{
// creating node varianles of Node data type
struct Node *head; // head => zero position
struct Node *one;
struct Node *two;
struct Node *three;
struct Node *four; // last node
// allocating dynamic memory to nodes in heap
head = (struct Node*) malloc(sizeof(struct Node));
one = (struct Node*) malloc(sizeof(struct Node));
two = (struct Node*) malloc(sizeof(struct Node));
three = (struct Node*) malloc(sizeof(struct Node));
four = (struct Node*) malloc(sizeof(struct Node));
// setting values and linking them
head -> data = 2;
head -> nextAdd = one;
one -> data = 8;
one -> nextAdd = two;
two -> data = 3;
two -> nextAdd = three;
three -> data = 6;
three -> nextAdd = four;
four -> data = 10;
four -> nextAdd = NULL;
traverse(head);
printf("\n\ninserted 22 at first\n\n");
//inserted 22 at first
head = insertAtFirst(head, 22);
traverse(head);
printf("\n\ninserted 55 at index 3\n\n");
head = insertAtIndex(head, 55, 3);
traverse(head);
printf("\n\ninserted 23 at index 0\n\n");
head = insertAtIndex(head, 23, 0);
traverse(head);
printf("\n\ninserted 111 at last index\n\n");
head = insertAtEnd(head, 111);
traverse(head);
printf("\n\ndelete the old head \n\n");
head = deleteAtHead(head);
traverse(head);
printf("\n\ndelete the last node \n\n");
head = deleteLastNode(head);
traverse(head);
printf("\n\ndelete the node at index 2 \n\n");
head = deleteByIndex(head,2);
traverse(head);
printf("\n\ndelete the node at index 4 \n\n");
head = deleteByIndex(head,4);
traverse(head);
printf("\n\ndelete the node having value 10\n\n");
head = deleteByValue(head, 10);
traverse(head);
printf("\n\ndelete the node having value 15 \n\n");
head = deleteByValue(head, 15);
traverse(head);
return 0;
}
0 Comments