Codewhoop

# Linked list insert node beginning or end

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

  • Beginning:

    1. Create a new Node.
    2. Make link part of the newly created node equal to head pointer & adjust the head pointer to point to the newly created node.

  • End

    1. Create a new Node.
    2. Traverse the Linked list to reach the last Node & point the link part of the last Node to newly created Node.
    3. Make the link part of newly created Node equal to NULL.
    4. Special Case: If list is empty, create a new node and point head pointer to it.

# 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 insert at the beginning of linked list
void insertBeg (int d)
{
 Node *ptr = new Node();
 ptr->data=d;
 ptr->link=head;
 head=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 list is empty
  if(head==NULL)
  head=ptr;
  //else list is not empty
  else
  {
   Node *temp = head;
   while(temp->link != NULL)
   {
    temp=temp->link;
   }
   temp->link=ptr;

  }

}
//Function to display linked list
void dispLink()
{
 Node *temp=head;
 while(temp!=NULL)
 {
  cout<<temp->data<<" ";
  temp=temp->link;
 }
 cout<<"\n";
}
//Main Function
int main()
{
 insertBeg(2);
 insertBeg(1);
 insertEnd(3);
 dispLink();
 return 0;
}

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