Codewhoop

# Linked list delete node from beginning or end

  • We can delete a node at the beginning or at the end of the linked list.

  • Firstly check if the list is empty ot not.

  • Beginning:

    1. Create a temporary pointer (ptr) & equate it to head to point to the first node.
    2. Make the head pointer equal to link part of the first node.
    3. Delete the first node using ptr pointer

  • End:

    1. Create a temporary pointer (ptr)
    2. Check if link part of first node is NULL i.e. Only one node is present. Delete the node and make head equal to NULL.
    3. If more than one nodes, Traverse to the last node using pointer ptr & keep track of second last node using pointer prev.
    4. Make the link part of second last node as NULL using prev & delete last node using ptr.

# Source Code - C++

#include <iostream>
using namespace std;

//Creating Node Structure
struct Node{
 int data;
 Node *link;
};
//creating head pointer and equating to NULL
Node *head=NULL;

//Function to delete node at the beginning
void deleteBeg(){
//if list is empty.
if(head==NULL)
 cout<<"LIST IS EMPTY\n";
else
{
 Node *ptr=head;
 head=head->link;
 free(ptr);

}
}

//Function to delete node at the end
void deleteEnd()
{
 Node *ptr;

 //if list is empty.
 if(head==NULL)
  cout<<"EMPTY LIST\n";
 //if list has only one node.
 if(head->link==NULL)
 {
  ptr=head;
  head=NULL;
  free(ptr);
 }
 //Traversing the list.
 else
 {  Node *prev;
  ptr=head;
  while(ptr->link!=NULL)
  {
   prev=ptr;
   ptr=ptr->link;
  }
  prev->link=NULL;
  free(ptr);

 }

}

//Function to insert at the end of linked list
void insertEnd (int d)
{

 Node *ptr = new Node();
 ptr->data=d;
 ptr->link=NULL;

 if(head==NULL)
 head=ptr;
 else
 {
  Node *temp = head;
  while(temp->link != NULL)
  {
   temp=temp->link;
  }
  temp->link=ptr;

 }

}

// function to display Linked list
void displayList(){
 Node *ptr=head;
 if(head==NULL)
  cout<<"LIST IS EMPTY\n";
 while(ptr!=NULL)
 {
  cout<<ptr->data<<" ";
  ptr=ptr->link;
 }
 cout<<"\n";
}

//Main Function
int main()
{

 insertEnd(1);
 insertEnd(2);
 insertEnd(3);
 insertEnd(4);
 insertEnd(5);
 displayList();

 deleteBeg();
 displayList();
 deleteEnd();
 displayList();
 return 0;
}

Time Complexity - At start: O(1), At End O(n)