Hot Topics
Data Structure
Operations on singular linked list
1. Insert First
Algorithm
We are assuming that there already exist atleast one node and a head pointer is pointing to it.
Create a new node and attach that node to the head of the linked list.
Reassign the head to the newly added node
Code:
void insertFirst(Node *&head, int d)
{
// creating a new node
Node *temp = new Node(d);
// connecting the next of new node to the head of linked
// list
temp->next = head;
// reassigning the head to the newly added node
head = temp;
}
2. Insert Last
Algorithm
We are assuming that one node is present and the tail pointer is pointing to that node.
Insert last means we have to add new node after the given node.
Reassign tail to the newly added node.
void insertLast(Node *&tail, int d)
{
// creating a new node
Node *temp = new Node(d);
// connecting the tail of the given node to the new node
tail->next = temp;
// reassigning tail to the new node
temp = tail;
}
3. Delete First
Algorithm
Check if the list is empty
If the list is not empty take a pointer on head and move the head to the next node of head
delete the pointer which stored the value of head
void deleteFirst(Node *&head)
{
// list is empty
if (head == NULL)
{
std::cout << "The list is empty and nothing can be
deleted "<next;
temp->next = NULL;
std::cout << "Deleted from first " <data << std::endl;
delete temp;
Return;
}
4. Delete Last
Algorithm
If list empty we cannot delete anything from list
When only one node is present take delete it,list will become empty
Traverse till the second last node,the next of second last node will give the last node.
Delete the last node
void deleteLast(Node *&head)
{
// list is empty
if (head == NULL)
{
std::cout << "List is empty" <next == NULL)
{
std::cout << "Only one node was present and it is deleted "<data<next->next != NULL)
secondlast = secondlast->next;
Node *lastNode = secondlast->next;
secondlast->next = NULL;
std::cout <data << " is deleted from last "<<std::endl;
delete lastNode;
}
}
5. Insert After a Value
Algorithm
Get a value after which you need to attach the node and traverse the list to check if value is present
If value is not present print value is not present in list
If value is present store the data you want to insert in a new node
Point the next of new node to the next node in which value is stored and reassign the next of the node in which value is stored to new node
void insertAfterValue(Node *&head)
{
// attaching a pointer to the head to traverse the list
Node *temp = head;
// num-the value after which new node to be inserted
// val-the value which is to be inserted
int num, val;
std::cout << "Enter the value after which new node is to be inserted : "<>num;
// traversing the list until we find the value after which we
// want to insert new node or else
while ((temp->data != num) && (temp->next != NULL))
temp = temp->next;
if (temp == NULL)
{
std::cout << "Value is not present in list" << std::endl;
}
else
{
std::cout << "Enter the value to be inserted " <> val;
Node *newNode = new Node(val);
newNode->next = temp->next;
temp->next = newNode;
}
}
6. Insert Before a Value
Algorithm
Get a value before which you need to attach the node and traverse the list to check if value is present
If value is not present print value is not present in list
If value is present take two pointers one pointing to head which will be used to find the node before which we want to insert new node and another pointing to NULL which will be used to keep a track of the node after which we will insert the new node.
void insertBeforeValue(Node *&head)
{
// attaching a pointer to the head to traverse the list
Node *temp = head;
// pointer used to keep a track of previous node
Node *prevNode = NULL;
// num-the value after which new node to be inserted
// val-the value which is to be inserted
int num, val;
std::cout << "Enter the value before which new node is to be inserted : "<>num;
// traversing the list until we find the value after which we
// want to insert new node or else
while ((temp->data != num) && (temp->next != NULL))
{
prevNode = temp;
temp = temp->next;
}
// value not found
if (temp->data != num)
{
std::cout << "Value is not present in list" <data == num)
{
std::cout << "Enter the value to be inserted " <> val;
Node *newNode = new Node(val);
newNode->next = head;
head = newNode;
}
// value found not in head
else
{
std::cout << "Enter the value to be inserted " <> val;
Node *newNode = new Node(val);
prevNode->next = newNode;
newNode->next = temp;
}
}
7. Insert After a Position
Algorithm
Take a variable to count the number of nodes we traversed.
Check if the given position is valid
If the position is valid then create a new node with the value you want to insert
If the given position is 0 that means we have to add before head of the list
If the position>0 keep decreasing the position value and at the same time traverse the node.This way when the position will be equal to 0 we will stand in our desired node after which we have to add our node.
void insertAfterPosition(Node *&head)
{
Node *temp = head;
/*count-to track the number of nodes we have traversed
pos-to get the position after which we need to insert node
val-the value we want to insert.*/
int count = 0, pos = 0, val;
// counting number of nodes
while (temp != NULL)
{
count++;
temp = temp->next;
}
std::cout << "Enter the position after which you want to insert value "<>pos;
/*checking if the position does not falls in the length of
given list*/
if ((pos count))
{
std::cout << "Invalid position!Please enter valid position."<<std::endl;
}
// the position does fall in the length of given list
else
{
std::cout << "Enter the value you want to insert "<>val;
Node *newNode = new Node(val);
// inserting first node in list
if (pos == 0)
{
newNode->next = head;
head = newNode;
}
/*inserting at any position of list except in the first
position*/
else
{
temp = head;
pos -= 1;
/*getting the node at the position after which
we will add new node*/
while (pos != 0)
{
--pos;
temp = temp->next;
}
// connecting new node to the list
newNode->next = temp->next;
temp->next = newNode;
}
}
}
8. Insert Before a Position
Algorithm
Take a variable to count the number of nodes we traversed.
Check if the given position is valid
If the position is valid then create a new node with the value you want to insert
If the given position is 1 that means we have to add before head of the list
If the position>2 keep decreasing the position value and at the same time traverse the node.This way when the position will be equal to 0 we will stand in our desired node after which we have to add our node.
void insertBeforePosition(Node *&head)
{
Node *temp = head;
/*count-to track the number of nodes we have traversed
pos-to get the position after which we need to insert node
val-the value we want to insert.*/
int count = 0, pos, val;
// counting number of nodes
while (temp != NULL)
{
count++;
temp = temp->next;
}
std::cout << "Enter the position before which you want to insert value" <> pos;
/*checking if the position does not falls in the length of given list*/
if ((pos count))
{
std::cout << "Invalid position!Please enter valid position." << std::endl;
}
// the position does fall in the length of given list
else
{
std::cout << "Enter the value you want to insert" <> val;
Node *newNode = new Node(val);
// inserting first node in list
if (pos == 1)
{
newNode->next = head;
head = newNode;
}
/*inserting at any position of list except in the first position*/
else
{
temp = head;
/*getting the node at the position after which we will add new node*/
while (pos > 2)
{
--pos;
temp = temp->next;
}
// connecting new node to the list
newNode->next = temp->next;
temp->next = newNode;
}
}
}
9. Delete After a Value
Algorithm
Take two pointers one pointing the current node we are in and another pointing the previous node of the current node
Take the value after which you want to insert new node
If the list is not empty traverse the list until we find the value after which we need to insert the new node and reach the last node of list
If the value is found remove the node from the list using the curr and prev pointers
void deleteAfterValue(Node *&head)
{
/*Taking two pointers and attaching one to head and another to NULL*/
Node *curr = head;
Node *prev = NULL;
/*
num-after which value we want to insert new node
val-the value you want to insert
*/
int num, val;
std::cout << "Enter the value after which you want to delete" <> num;
// list empty
if (head == NULL)
std::cout << "List is empty" <data != num) && (curr->next != NULL))
{
prev = curr;
curr = curr->next;
}
if (curr == NULL)
{
std::cout << "Value is not present in list" <next;
curr->next = prev->next;
std::cout <data << " is deleted" << std::endl;
delete prev;
}
return;
}
}
10. Delete Before a Value
Algorithm
Check if the value input is present in list.If not present or if the list is empty or the list contains only a single node then we can’t delete any value.
If the value is present and the list has more than one node then we will assign three pointers.
curr pointer will determine the node in which value is present.
prev1 pointer will determine the before node of curr node and prev2 will determine the second previous node.This way we can remove a node before a value.
void deleteBeforeValue(Node *&head)
{
Node *curr = head;
Node *prev1 = NULL;
Node *prev2 = NULL;
int num, val;
std::cout << "Enter the value before which you want to delete" <> num;
if (head == NULL)
std::cout << "The list is empty" <data != num) && (curr->next != NULL))
{
prev1 = curr;
curr = curr->next;
}
if (curr == NULL)
std::cout << "The value is not present in list" << std::endl;
// single node present
else if (curr == head)
std::cout << "No value can be deleted" <next->data == num)
{
head = curr;
std::cout <data << " is deleted" <data != prev1->data)
{
prev2 = curr;
curr = curr->next;
}
prev2->next = curr->next;
std::cout <data << " is deleted" << std::endl;
delete curr;
}
}
}
}
11. Delete Position
Algorithm
Take two pointers initialize curr to head and prev to NULL
Count the total number of nodes present in list and if the position given is not present in between 0 and the number of nodes then deletion won’t be possible
To remove head node we have to reassign head to immediate next node present
If the position is greater than 1 then keep on decreasing the value of position and traverse the list using the two pointers.This way you can point the curr pointer to the exact position which you want to delete.
void deletePosition(Node *&head)
{
Node *curr = head;
Node *prev = NULL;
int pos, count = 0;
//*counting number of nodes present in list*/
while (curr != NULL)
{
count++;
curr = curr->next;
}
// list not present or empty
if (count == 0)
std::cout << "List is empty" << std::endl;
/*checking for the position*/
else
{
std::cout << "Enter the position which you want to delete" <> pos;
curr = head;
/*given position not inside the length of list*/
if ((pos count))
std::cout << "Deletion is not possible" <next;
std::cout <data << " is deleted" <next;
}
prev->next = curr->next;
std::cout <data << " is deleted" << std::endl;
delete curr;
}
}
}
}
12. Display
Algorithm
If the list is empty we can’t display anything
Take a pointer at the head of list and using it traverse the list until the pointer reaches NULL
void display(Node *&head)
{
if (head == NULL)
{
std::cout << "List is empty " << std::endl;
return;
}
Node *temp = head;
/*traversing list using a pointer*/
while (temp != NULL)
{
std::cout <data <next;
}
std::cout << std::endl;
}
13. Reverse Display
Algorithm
Traverse the list until head reaches NULL and when head reaches NULL start printing it
void reverseDisplay(Node* &head)
{
if(head==NULL)
return;
reverseDisplay(head->next);
std::cout<data<<" ";
}
14. Physically Reverse Display
Algorithm
Take three pointers pointing the current node,the next node and the previous node.
Run a loop until the pointer pointing to current node reaches NULL
With every iteration point the next node of current node to previous node of current node and keep on moving all the three pointers one step ahead.
void physicallyReverseDisplay(Node *&head)
{
Node *curr = head;
Node *forward = NULL;
Node *prev = NULL;
/*list is empty or has only one node*/
if (head == NULL || head->next == NULL)
{
std::cout <data << std::endl;
}
std::cout << "Reverse Display" <next;
curr->next = prev;
prev = curr;
curr = forward;
}
head = prev;
display(head);
}
15. Free All Nodes
Algorithm
Take two pointers denoting the current node and previous node
Traverse through the list until the pointer pointing the current node reaches NULL.
While traversing keep on increasing both the pointers and delete element which is pointed by the previous pointer.
void freeAllNodes(Node *&head)
{
Node *curr = head;
Node *prev = NULL;
if (curr == NULL)
{
std::cout << "List is empty" <next;
delete prev;
}
}
head = NULL;
std::cout << "All elements are deleted" << std::endl;
}
16.Count Nodes
Algorithm
Attach a pointer to the head node of list and keep a counter variable
Using the pointer traverse through the list until the pointer reaches NULL and keep on increasing the counter variable with each iteration.
void countNodes(Node* &head)
{
Node* temp=head;
int count=0;
/*traversing through the list*/
while(temp!=0){
/*increasing counter variable to count the nodes*/
count++;
/*shifting pointer from one node to another node with every iteration*/
temp=temp->next;
}
std::cout<<"Total number of nodes is "<<count<<std::endl;
}
17. Delete First nth Nodes
Algorithm
Take two pointers curr and prev,attach curr to the head and prev to NULL at first
Take a variable to count the number of nodes in the list
If the list is not empty and the given value of n lies inside the range of list then traverse the value of n reaches 0.
With every iteration keep pointing the prev pointer to the next of curr pointer and keep on deletint the value pointed by curr.
void deleteFirstnNodes(Node *&head)
{
/*taking two pointer*/
Node *curr = head;
Node *prev = NULL;
int n, count = 0, temp;
/*counting the total number of nodes present in list*/
while (curr != NULL)
{
count++;
curr = curr->next;
}
if (count == 0)
{
std::cout << "List is empty and deletion is not possible" << std::endl;
}
else
{
std::cout << "Enter the number of nodes you want to delete from first" <> n;
temp = n;
/*range doesn't lay in the range of list*/
if ((n count))
{
std::cout << "Invalid input" <next;
delete curr;
n--;
curr = prev;
}
head = prev;
std::cout << "First n nodes are deleted" << std::endl;
}
}
}
18. Delete Last n Nodes
Algorithm
Take two pointers,temp pointing to NULL and curr pointing to the current node at first.
Take a counter variable to count the total number of nodes present in list.
Take the number of nodes you want to delete and check if that number is lesser than equal to the total number of nodes present in list.
If the number lies in range then we can have two cases
Case 1: The number of nodes you want to delete is equal to the total number of nodes present in list.In that case start deleting each node with each iteration until the curr pointer reaches NULL.
Case 2: The number of nodes you want to delete is less than the total number of nodes.In this case first get the number of nodes we have to keep in list and iterate through list until the number of nodes you want to keep becomes 0.This way we can set the pointers at the end of number of nodes we have to keep.
Delete all the nodes until the pointer reaches NULL
void deleteLastnNodes(Node* &head){
Node* curr=head;
Node* temp=NULL;
int n,count=0,tempo;
/*counting number of nodes in list*/
while(curr!=NULL){
count++;
curr=curr->next;
}
if(count==0)
std::cout<<"List is empty"<<std::endl;
else{
std::cout<<"Enter the number of nodes you want to delete from last"<>n;
tempo=n;
if((ncount)){
std::cout<<"Invalid input"<next;
delete temp;
}
head=NULL;
std::cout<<"Last nodes are deleted"<next;
n--;
}
/*deleting last n nodes*/
while(curr!=NULL){
temp->next=curr->next;
delete curr;
curr=temp->next;
}
std::cout<<"Last nodes are deleted"<<std::endl;
}
}
}
Popular Category
Hot Topics
Go through our study material. Your Job is awaiting.