-
Notifications
You must be signed in to change notification settings - Fork 0
/
Delete a node at given position - Linkrd List.txt
94 lines (64 loc) · 2.45 KB
/
Delete a node at given position - Linkrd List.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
Algorithm for how to delete a node before specified position in singly linked list
If the head is NULL, return.
Create a node temp and make it point to the head.
If the position is 0, it means that we have to delete the head of the list. We can easily do that by head = temp → next and free(temp). As temp was pointing to the head, we have incremented the head and freed temp.
If the position is not 0, we will proceed. Now, we will write a loop with i = 0 to i < (position -1). As we have discussed, to delete a node, we need a pointer to its previous node. So while traversing the loop, we will increment temp.
Now, after the loop ends, if the temp is NULL or temp → next is NULL, we will simply return as the position is more than the number of nodes in the linked list.
If the above condition fails, we will have temp pointing to the (position – 1)th node. Now, we simply have to change the required pointers.
We will save the temp → next → next in a new node next1. Now, we will free temp → next, as it is the node at the given position. In the end, temp → next = next1. – In this way, there is no unnecessary memory leak and the node at the given position is getting deleted successfully.
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void deleteNode(Node **head_ref, int position)
{
if (*head_ref == NULL)
return;
Node* temp = *head_ref;
if (position == 0)
{
*head_ref = temp->next;
free(temp);
return;
}
for(int i = 0; temp != NULL && i < position - 1; i++)
temp = temp->next;
if (temp == NULL || temp->next == NULL)
return;
Node *next1 = temp->next->next;
free(temp->next);
temp->next = next1;
}
void printList( Node *node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
int main()
{
Node* head = NULL;
push(&head, 7);
push(&head, 2);
push(&head, 5);
push(&head, 1);
cout << "Created Linked List: ";
printList(head);
deleteNode(&head, 2);
cout << "\nLinked List after Deletion at position 2: ";
printList(head);
return 0;
}