I am unable to implement the deletion of the node from the end, as well as deletion of the node from middle
Please implement the deleteTail() function
and deleteAtMiddle() function
Below is the code, taught to me by the Prateek Sir.
#include
#include
using namespace std;
class node
{
public:
int data;
// one pointer to the next node
node *next;
// parameterized constructor for taking data stored
node (int d)
{
data = d;
next = NULL;
}
};
// function for insert node at head
// accept the head pointer, and accept the int data
// Pass by reference to make changes reflect on the node
// Now, I have access to the actual HEAD
void
InsertAtHead (node * &head, int d)
{
// if head is null means
// we are going to insert 1st node in the linked List
if (head == NULL)
{
// you create a new node and put the data and you return it
// head ke pass, new node ka address aa jae
// head initially NULL --> now it will point to new node value 3
head = new node (d);
// new --> return the address of memory allocated dynamically
return;
// when you create a new node, next field automatically will be NULL
}
// if head is not NULL
// you will create a new node say node* n
node *n = new node (d);
// say n is pointing to value 2 (in main function) whose address say 200,
// and value stored in node in 2 value is 300
// to access data member of pointer, two ways
// 1) dereference and dot operator (*n). next = head;
// 2) arrow operator n -> next = head;
// then update the head jisse head jo hai vo new node ko point krega
// head = n
// mtlb new node ke next meh purane head ka address aa jae
// head meh new node ka address aa jae
n->next = head;
head = n;
}
// function to print the linked list
void
print (node * head)
{
while (head != NULL)
{
cout << head->data << " --> ";
// update head jab tak NULL na aa jae
head = head->next;
}
cout << “NULL” << endl;
}
// same pass by reference
// 2nd parameter is data stored, 3rd is the position
/*
eg 0 --> 1 --> 2 --> 4
d = 3 and p = 2 means data value is 3 and insert after 2 position
after insert
0 --> 1 --> 3 --> 2 --> 4
means, p =2, after 2 nodes, insert in linked list
if p = 0, insert at head
if p > length, insert at tail
you are standing at 0 value node
need to reach node value 1 as 1
0 --> 1 --> 2 --> 4
need --> (p - 1) jumps ( 0 se 1 aa gya in 1 jump)
head = head -> next; is one jump
rest explained in page 77 of notes
*/
int length(node* head)
{
int count = 0;
while(head != NULL)
{
count++;
head = head -> next;
}
return count;
}
void InsertAtTail(node*& head, int data)
{
// if this function runs without node so handle case
if(head == NULL)
{
head = new node(data);
return;
}
// otherwise find a tail pointer
// by iterating over the linked list
// initially starting from the head
node* tail = head;
// while tail -> next is not NULL
// mtlb 0 --> 1 --> 2 --> 4
// 4 tak na aa jae, last node tak na aa jae
while(tail -> next != NULL)
{
tail = tail -> next;
}
// if simply used tail not NULL --> toh loop over hote hi tail NULL ho jaata
// and once you reach the last node
// you update the address of last node with the address of new node,
// jisse insert at tail ho pae
tail -> next = new node(data);
return;
}
void InsertInMiddle (node * &head, int d, int p)
{
// handle the corner case
if (head == NULL || p == 0)
{
// linked list is not present
// simply insert at the head
InsertAtHead(head, d);
return;
}
// we will create length function above
else if(p > length(head))
{
// we will create this function above
// taking head node and the data
InsertAtTail(head, d);
}
else
// insert at middle
{
// you need to reach the temp node by taking (p-1) jumps
int jump = 1;
// starting the jump from head
node* temp = head;
while(jump <= (p-1))
{
// temp ke paas next node ka address aa jaega means jump
temp = temp -> next;
jump++;
}
// you are standing at node jaha insert karna hai
// create a new node
node* n = new node(d);
// where the value of 4 will come in new node
// from the temp node --> value 2 vaali node se
n -> next = temp -> next;
// value 2 vaali node, pointer uska new node (value 3)
// ki position/ address store krega to make a link
temp -> next = n;
}
}
// to delete the node which is at the head
// pass by reference, becoz modifying the head
void deleteHead(node*& head)
{
if(head == NULL)
{
// no element, so just return
return;
}
// if head is not NULL
// store the address holded earlier by head
// to the new node
node* temp = head -> next;
// otherwise you delete the node pointed by the head
// by doing this, we will lose the address of next node
// becoz head hi delete kar diya humne
// so doing this, firstly, store the address in a node, fir delete krro
delete head;
// still head main meh rhega becoz main meh head hai humara
head = temp;
// temp is local variable, so it will get destroyed after function call
}
int main ()
{
// head pointing to the 1st node of Linked List
// head stores the address of the 1st node
node *head = NULL;
// take the head, and insert 3 into it and so on
InsertAtHead (head, 5);
InsertAtHead (head, 2);
InsertAtHead (head, 1);
InsertAtHead (head, 0);
cout << "Before Inserting: "<< endl;
print (head);
// insert value 4, after 3 nodes
InsertInMiddle(head, 4, 3);
InsertAtTail(head, 7);
cout << "After inserting: " << endl;
print (head);
cout << "After deleting the head: " << endl;
deleteHead(head);
print(head);
return 0;
}