Circular Doubly Linked List - Deletion algorithm

Prev Next

---

Deleting the First Node from a Circular Doubly Linked List Algorithm

Step 1: If the linked list is empthy (START == NULL)

Write "Sorry Buddy there is no node"

Step 2: If the linked list have only one node (START -> NEXT == START -> PREV)

free(START)
START = NULL

Step 3: If the list have more than one node

PTR = START;
while(PTR ->NEXT != START)
{

PTR = PTR ->NEXT

}
PTR -> NEXT = START -> NEXT
PTR -> NEXT -> PREV =PTR
free(START);
START = PTR ->NEXT

Step 4 : EXIT

Deleting the Last Node from a Circular Doubly Linked List Algorithm

Step 1: If the linked list is empthy (START == NULL)

Write "Sorry Buddy there is no node"

Step 2: If the linked list have only one node (START -> NEXT == NULL)

free(START);
START = NULL

Step 3: If the list have more than one node

PTR = START
while(PTR -> NEXT != START)
{
PTR = PTR -> NEXT }
PTR -> PREV -> NEXT = START
START -> PREV = PTR ->PREV
free(PTR)

Step 4 : EXIT

Prev

Next

Circular Doubly Linked List- data Structures

Prev Next

---

A circular doubly linked list is a simple doubly linked list in which prev link of the first node points to the last node and the next link of the last node points back to the start node .

First node have the address of last node and last node have the address of first node.

Real life example is train in which guard have the information of driver and Vice Versa.

Creating a circular doubly linked list with 'N' number of Nodes

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE
NEW_NODE-> NEXT = START
NEW_NODE ->PREV = START

Step 3: If the linked list is not empthy

NEW_NODE ->NEXT = START
NEW_NODE ->PREV = START ->PREV
START -> PREV -> NEXT = NEW_NODE
START -> PREV = NEW_NODE

Step 4 : Repeat Steps 1,2,3 'N' times

Step 5 : EXIT

Inserting a Node at the Beginning of a Circular Doubly Linked List

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE
NEW_NODE-> NEXT = START
NEW_NODE ->PREV = START

Step 3: If the linked list is not empthy

NEW_NODE ->PREV = START -> PREV
NEW_NODE -> NEXT = START
START -> PREV -> NEXT = NEW_NODE
START -> PREV = NEW_NODE
START = NEW_NODE

Step 4 : EXIT

Inserting a NEW Node at the End of a Circular Doubly Linked List

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE
NEW_NODE-> NEXT = START
NEW_NODE ->PREV = START

Step 3: If the linked list is not empthy

NEW_NODE -> PREV = START ->PREV
NEW_NODE -> NEXT = START
START -> PREV -> NEXT = NEW_NODE
START -> PREV = NEW_NODE

Step 4 : EXIT

Prev

Next

Doubly Linked List | Insertion Algorithm | Data Structures & Algorithm

Prev Next

---

Inserting a NEW Node at the Beginning of a Doubly Linked List

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

NEW_NODE -> NEXT =START
START -> PREV = NEW_NODE
START = NEW_NODE

Step 4 : EXIT

Inserting a new node at the end of a Doubly Linked List

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

PTR = START
while(PTR -> NEXT != NULL)
{
PTR = PTR -> NEXT
}
PTR -> NEXT = NEW_NODE
NEW_NODE ->PREV = PTR

Step 4 : EXIT

Inserting a node at a specific position in a Doubly linked list

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: Enter the position where u want to insert the node & count total no of node

totalnode = countnode(START)

Step 3: Ensure that enter postion is in between first and last node

IF( POS > 1 && POS < totalnode)

Step 4: Store the starting address in PTR & move the PTR pointer upto specified position .

PTR = START;
MOVE = 1;
while(MOVE< POS-1)
{
PTR = PTR->NEXT;
MOVE++;
}
NEW_NODE -> NEXT = PTR -> NEXT;
NEW_NODE -> PREV = PTR
PTR -> NEXT -> PREV = NEW_NODE
PTR -> NEXT = NEW_NODE
[END OF IF]

ELSE
Write "Position is invalid "

Step 5 : EXIT

Prev

Next

Doubly Linked List - data structures and algorithm

Prev Next

---

A double linked list is a two-way list in which all nodes will have two links - one to the next node and another to the previous node.

Each node consists of three parts

1. A pointer to the previous Node ( PREV )
2. Data
3. A pointer to the next Node ( NEXT )

The PREV field is uses to store the address of the predecessor node, which enables us to traverse the list in the backward direction. The NEXT field is uses to store the address of the successor node , which enables us to traverse the list in the forward direction.

The PREV field of the first node and the NEXT field of the last node will contain NULL

The main advantage of using a doubly linked list is that it makes searching twice as efficient and provides bi-directional traversing.

Structure of a doubly linked list

struct DLL
{

struct DLL *prev;
int data;
struct DLL *next;

};
typedef struct DLL node;
node *start = NULL;

Creating a node for Double Linked List

node* createnode()

{

node* newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter the data: ");
scanf("%d", &newnode -> data);
newnode -> prev = NULL;
newnode -> next = NULL;
return newnode;

}

Creating a Double Linked List with 'N' number of nodes

Step 1: CREATE THE NEW NODE USING createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

PTR = START
while(PTR -> NEXT != NULL)
{
PTR = PTR -> NEXT
}
PTR -> NEXT = NEW_NODE
NEW_NODE -> PREV = PTR

Step 4 : Repeat Steps 1,2,3 'N' times.

Step 5 : EXIT

Prev Next

Circular Linked List -Deletion Algorithm & Program

Circular Linked List -Deletion

Prev Next

---

Now we will see how a new node is deleted from an already existing circular linked list. It can be performed in two ways. They are as follows...

1. Deleting the first node
2. Deleting the last node

Rest of the cases are similar to Singly Linked List deletion operation

Deleting the First Node from a Circular Linked List

Step 1: If the linked list is empthy (START == NULL)

Write "Sorry Buddy list is Empthy"

Step 2: If the linked list have only one node (START == START -> NEXT)

free(START)
START = NULL

Step 3: If the list have more than one node

PTR = START
while(PTR -> NEXT != START)
{

PTR = PTR -> NEXT

}
PTR -> NEXT = START -> NEXT
free(START)
START = PTR -> NEXT

Step 4 : EXIT

Deleting the Last Node from a Circular Linked List

Step 1: If the linked list is empthy (START == NULL)

Write "Sorry Buddy linked list is Empthy"

Step 2: If the linked list have only one node (START == START -> NEXT)

free(START)
START = NULL

Step 3: If the list have more than one node

PTR = START
while(PTR -> NEXT -> NEXT!= START)
{

PTR = PTR -> NEXT

}
TEMP = PTR -> NEXT
PTR -> NEXT = START
free(TEMP)

Step 4 : EXIT

Display the Nodes of the Circular Single Linked List

Step 1: If the linked list is empthy (START == NULL)

Write "Sorry Buddy there is no node

Step 2: If the linked list is not Empthy

PTR = START;
do
{

printf("%d-->", PTR -> DATA);
PTR = PTR -> NEXT;

} while(PTR != START);

Step 3: EXIT

C Program to Implement Circular Linked List

#include <stdio.h>
#include<conio.h>
#include <malloc.h>
#include <stdlib.h.h>
struct Circular_Linked_List
{
   int data;
   struct Circular_Linked_List *next;
};

typedef struct Circular_Linked_List node;
node *start = NULL;

node* createnode()
{
   node * newnode;
   newnode = (node *) malloc(sizeof(node));
   printf("\n Enter the  data : ");
   scanf("%d", &newnode -> data);
   newnode -> next = NULL;
   return newnode;
}

void create_Circular_Linked_List(int n)
{
   int i;
   node *newnode , *ptr;
   
   for(i = 0; i < n; i++)
    {
       newnode = createnode();
        if(start == NULL)
         {
           start = newnode;
         }
        else
        {
          ptr = start;
          while(ptr -> next != NULL)
          {
            ptr = ptr -> next;
    }
    ptr -> next = newnode;
     }
    }
    newnode ->next = start;
}

void insert_beg()
{
  node *newnode ,*ptr;
  newnode = createnode();
  if(start == NULL)
   {
       start = newnode;
       newnode -> next = start;
   }
  else
   {
     ptr = start;
     while(ptr -> next != start)
     {
        ptr = ptr -> next;
     }
     ptr -> next = newnode;
     newnode -> next =start;
     start = newnode;
   }
     
}

void insert_end()
{
   node *newnode, *ptr;
   newnode = createnode();
   if(start == NULL)
   {
       start = newnode;
       newnode -> next = start;
   }
   else
   {
      ptr = start;
      while(ptr -> next != start)
      {
      ptr = ptr -> next;
      }
      ptr -> next = newnode;
      newnode -> next = start;
   }
}

int countnode(node *ptr)
{ 
  int num_of_node=0;
  if (start != NULL)
  {
    do
  {
       num_of_node++;
       ptr = ptr -> next;
     }while(ptr != start);
 }
  return (num_of_node);
}

void insert_mid()
{
  node *newnode, *ptr, *preptr;
  int pos, totalnode, move = 1;
  printf("\n Enter the position where u want to insert the node : ");
  scanf("%d", &pos);
  totalnode = countnode(start);
  if(pos > 1 && pos < totalnode)
  {
     newnode = createnode();
  ptr = start;
     while(move < pos-1)
     {
       ptr = ptr -> next;
       move++;
     }
     newnode -> next = ptr -> next ;
     ptr -> next = newnode;
     ;
  }
  else
    printf("\n\t position %d is not a middle position", pos);
}

void delete_beg()
{
   node *ptr;
   if(start == NULL)
   {
      printf("\n Sorry Buddy there is no node... List is Empty");
      return ;
   }
   else
   {
      ptr = start;
      while(ptr -> next != start)
      {
      ptr = ptr -> next;
      }
      ptr -> next = start -> next;
      free(start);
      start = ptr -> next ;
      printf("\n Node deleted successfuly... ");
   }
}

void delete_last()
{
  node *ptr, *temp;
  if(start == NULL)
  {
    printf("\n Sorry Buddy there is no node ...List is Empty");
    return ;
  }

  else if(start ==start->next)
  {
   free(start);
   start=NULL;
  }
  else
  {
    ptr = start;
    while(ptr -> next  -> next != start)
    {
       ptr = ptr -> next;
    }
    temp = ptr -> next;
    ptr->next =start;
    free(temp);
  }
}

void delete_mid()
{
  node *ptr, *preptr;
  int pos, totalnode, move = 1;
  if(start == NULL)
   {
      printf("\n Sorry Buddy there is no node... List is Empty");
      return ;
   }
  else
   {
      printf("\n Enter position of node u want to delete: ");
      scanf("%d", &pos);
      totalnode = countnode(start);
      if(pos > totalnode)
      {
        printf("\n There is no such node  found in the list!");
      }
      if(pos > 1 && pos < totalnode)
      {
        ptr = preptr = start;
        while(move < pos)
        {
            preptr = ptr;
            ptr = ptr -> next;
            move ++;
        }
        preptr -> next = ptr -> next;
        free(ptr);
        printf("\n Node deleted successfuly...");
      }
     else
      {
        printf("\n Position is invalid...  ");
        getch();
      }
   }
}

void display_List()
{
  node *ptr;
  ptr = start;
  printf("\n The contents of Circular_Linked_List : \n");
  if(start == NULL)
  {
    printf("\n Sorry Buddy there is no node... List is Empty");
    return;
  }
  else
  {  do
       {
          printf("\t %d -->", ptr -> data);
          ptr = ptr -> next;
       } while(ptr != start);
       printf(" X ");
  }
}
  
  
int menu()
{
  int choice;
  printf("\n --------Circular Linked List -------\n");
  printf("\n 1. Create a list ");
  printf("\n 2. Display the list");
  printf("\n----------------------------------");
  printf("\n 3.Insert a new node at beginning ");
  printf("\n 4.Insert a new node at end");
  printf("\n 5.Insert a new node at middle");
  printf("\n---------------------------------");
  printf("\n 6.Delete a node from the beginning");
  printf("\n 7.Delete a node from the Last");
  printf("\n 8.Delete a node from the Middle");
  printf("\n-----------------------------------");
  printf("\n 9. Count total no of nodes ");
  printf("\n 10. Exit ");
  printf("\n\n Enter your choice : ");
  scanf("%d",&choice);
  return choice;
}


 
int main()
{
  int choice, n;

  while(1)
  {
      choice = menu();
      switch(choice)
      {
        case 1:  if(start == NULL)
                 {
                   printf("\n Enter number of nodes you want to create: ");
                   scanf("%d", &n);
                   create_Circular_Linked_List(n);
                   printf("\n List created successfuly..");
                 }
                 else
                 printf("\n List is already created..");
                break;
        
        case 2: display_List();    break;
        
  case 3: insert_beg();      break;
        
  case 4: insert_end();      break;
        
  case 5: insert_mid();      break;
      
     case 6: delete_beg();      break;

        case 7:  delete_last();    break;

        case 8: delete_mid();      break;
        
  case 9: printf("\n Total number of nodes : %d ", countnode(start));
                 break;
       
      case 10 : exit(0);
      }
     getch();
   }
}

Prev Next

Circular Singly Linked List | Insertion Algorithm | Data Structures

Prev Next

---

A circular linked list is a simple linked list in which last node contain the address of first node. It has no beginning and no end means we can begin at any node and traverse the list in any direction, forward or backward, until we reach the same node where we started.

A single linked list can be made a circular linked list by simply storing address of the very first node in the next field of the last node.

Creating a Circular Single Linked List with 'N' number of Nodes

Step 1: Create a new node using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

PTR = START
while (PTR -> NEXT != NULL)
{
PTR = PTR -> NEXT
}
PTR -> NEXT = NEW_NODE

Step 4 : Repeat Steps 1,2,3 'N' times.

Step 5 : NEW_NODE ->NEXT = START

Step 6 : EXIT

Circular Singly Linked List - Inserting a New Node

Now we will see how a new node is added into an already existing circular linked list. It can be performed in two ways. They are as follows...

1. Inserting at Beginning of the list

2. Inserting at End of the list

Rest of the cases are similar to Singly Linked List insert operation.

Inserting a new node at the Beginning of a Circular Linked List

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE
NEW_NODE -> NEXT = START

Step 3: If the linked list is not empthy

PTR = START
while(PTR -> NEXT != START)
{

PTR = PTR -> NEXT

}
PTR -> NEXT = NEW_NODE
NEW_NODE -> NEXT =START
START = NEWNODE

Step 4 : EXIT

Inserting a new node at the End of a Circular Linked List

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE
NEW_NODE -> NEXT = START

Step 3: If the linked list is not empthy

PTR = START
while(PTR -> NEXT!=START)
{
PTR = PTR -> NEXT
}
PTR -> NEXT = NEW_NODE
NEW_NODE -> NEXT =START

Step 4 : EXIT

Prev Next

singly linked list deletion algorithm

Singly Linked List - deletion of a node

Prev Next

---

Now we will see how a node is deleted form an already existing linked list. In a single linked list, the deletion operation can be performed in three ways. They are as follows...

1. Deleting the first node of the list
2. Deleting the last node of the list
3. Deleting a Specific Node

Algorithm to delete first node in singly linked list

Step 1: If linked list is empthy (START == NULL)

Write "Sorry Buddy there is no node "

Step 2: If linked list have only one node (START -> NEXT== NULL)

free(START)
START = NULL

Step 3: If the list have more than one node

PTR = START
START = START -> NEXT
free(PTR)

Step 4 : EXIT

Algorithm to delete last node from a singly linked list

Step 1: If linked list is empthy (START == NULL)

Write "Sorry Buddy there is no node "

Step 2: If linked list have only one node (START -> NEXT== NULL)

free(START)
START = NULL

Step 3: If the list have more than one node

PTR = START
while(PTR -> NEXT != NULL)
{
PREPTR = PTR
PTR = PTR -> NEXT
}
PREPTR -> NEXT = NULL
free( PTR )

Step 4 : EXIT

Counting total no of nodes in a singly linked list

int countnode(node *START)
{

if(START == NULL)
return(0);
else
return(1 + count(START-> NEXT));

}

Deleting a Specific Node from the Singly linked list

Step 1: If linked list is empthy (START == NULL)

Write "Sorry Buddy there is no node "

Step 2: Enter the position (POS) of node u want to delete & count total no of node

totalnode = countnode()
if(POS > totalnode )
Write "Given node not found in the list!"

Step 3: Ensure that enter postion is in between first and last node

IF( POS > 1 && POS < totalnode)

Step 4: Store the starting address in PTR & PREPTR & then move the PTR pointer upto specified position

PTR = PREPTR = START;
MOVE = 1;
while(MOVE< POS)
{
PREPTR = PTR
PTR = PTR->NEXT;
MOVE++;
}
PREPTR -> NEXT = PTR -> NEXT;
free(PTR);
Write "Node deleted successfuly..."
[END OF IF]

ELSE
Write "Position is invalid "

Step 5 : EXIT

C Program to Create, Insert ,Delete and Display the Elements in the Singly Linked List.

    
#include<stdio.h>
#include<conio.h>
#include <malloc.h>
#include <stdlib.h>
struct Linked_List
{
   int data;
   struct Linked_List *next;
};

typedef struct Linked_List node;
node *start = NULL;

node* createnode()
{
   node * newnode;
   newnode = (node *) malloc(sizeof(node));
   printf("\n Enter the  data : ");
   scanf("%d", &newnode -> data);getchar();
   newnode -> next = NULL;
   return newnode;
}

void create_Linked_List(int n)
{
   int i;
   node *newnode , *ptr;
   
   for(i = 0; i < n; i++)
    {
       newnode = createnode();
        if(start == NULL)
         {
           start = newnode;
         }
        else
        {
          ptr = start;
          while(ptr -> next != NULL)
          {
            ptr = ptr -> next;
    }
    ptr -> next = newnode;
     }
    }
}

void insert_beg()
{
  node *newnode;
  newnode = createnode();
  if(start == NULL)
   {
       start = newnode;
   }
  else
   {
      newnode -> next = start;
      start = newnode;
   }
}

void insert_end()
{
   node *newnode, *ptr;
   newnode = createnode();
   if(start == NULL)
   {
      start = newnode;
   }
   else
   {
      ptr = start;
      while(ptr -> next != NULL)
      {
      ptr = ptr -> next;
      }
      ptr -> next = newnode;
   }
}

int countnode(node *ptr)
{
  int num_of_node=0;
  while(ptr != NULL)
  {
    num_of_node++;
    ptr = ptr -> next;
  }
  return (num_of_node);
}

void insert_mid()
{
  node *newnode, *ptr, *preptr;
  int pos, totalnode, move = 1;
  printf("\n Enter the position where u want to insert the node : ");
  scanf("%d", &pos);
  totalnode = countnode(start);
  if(pos > 1 && pos < totalnode)
  {
     newnode = createnode();
  ptr = start;
     while(move < pos-1)
     {
       ptr = ptr -> next;
       move++;
     }
     newnode -> next = ptr -> next ;
     ptr -> next = newnode;
     ;
  }
  else
    printf("\n\t position %d is not a middle position", pos);
}

void delete_beg()
{
   node *ptr;
   if(start == NULL)
   {
      printf("\n Sorry Buddy there is no node... List is Empty");
      return ;
   }
   else
   {
      ptr = start;
      start = ptr -> next;
      free(ptr);
      printf("\n Node deleted successfuly... ");
   }
}

void delete_last()
{
  node *ptr, *preptr;
  if(start == NULL)
  {
    printf("\n Sorry Buddy there is no node ...List is Empty");
    return ;
  }
  else
  {
    ptr = start;
    preptr = start;
    while(ptr -> next != NULL)
    {
      preptr = ptr;
      ptr = ptr -> next;
    }
    preptr -> next = NULL;
    free(ptr);
    printf("\n Node deleted successfuly... ");
  }
}

void delete_mid()
{
  node *ptr, *preptr;
  int pos, totalnode, move = 1;
  if(start == NULL)
   {
      printf("\n Sorry Buddy there is no node... List is Empty");
      return ;
   }
  else
   {
      printf("\n Enter position of node u want to delete: ");
      scanf("%d", &pos);
      totalnode = countnode(start);
      if(pos > totalnode)
      {
        printf("\n There is no such node  found in the list!");
      }
      if(pos > 1 && pos < totalnode)
      {
        ptr = preptr = start;
        while(move < pos)
        {
            preptr = ptr;
            ptr = ptr -> next;
            move ++;
        }
        preptr -> next = ptr -> next;
        free(ptr);
        printf("\n Node deleted successfuly...");
      }
     else
      {
        printf("\n Position is invalid...  ");
        getch();
      }
   }
}

void display_List()
{
  node *ptr;
  ptr = start;
  printf("\n The contents of Linked_List : \n");
  if(start == NULL)
  {
    printf("\n Empty List");
    return;
  }
  else
  {  printf("\t");
 while(ptr != NULL)
    {
      printf("%d -->", ptr -> data);
      ptr = ptr -> next;
    }
  }
  printf(" X ");
}
int menu()
{
  int choice;
  printf("\n --------Singly Linked List -------\n");
  printf("\n 1. Create a list ");
  printf("\n 2. Display the list");
  printf("\n----------------------------------");
  printf("\n 3.Insert a new node at beginning ");
  printf("\n 4.Insert a new node at end");
  printf("\n 5.Insert a new node at middle");
  printf("\n---------------------------------");
  printf("\n 6.Delete a node from the beginning");
  printf("\n 7.Delete a node from the Last");
  printf("\n 8.Delete a node from the Middle");
  printf("\n-----------------------------------");
  printf("\n 9. Count total no of nodes ");
  printf("\n 10. Exit ");
  printf("\n\n Enter your choice : ");
  scanf("%d",&choice);
  return choice;
}


 
int main()
{
  int choice, n;

  while(1)
  {
      choice = menu();
      switch(choice)
      {
        case 1:  if(start == NULL)
                 {
                   printf("\n Enter number of nodes you want to create: ");
                   scanf("%d", &n);
                   create_Linked_List(n);
                   printf("\n List created successfuly..");
                 }
                 else
                 printf("\n List is already created..");
                break;
        
        case 2: display_List();    break;
        
  case 3: insert_beg();      break;
        
  case 4: insert_end();      break;
        
  case 5: insert_mid();      break;
      
     case 6: delete_beg();      break;

        case 7:  delete_last();    break;

        case 8: delete_mid();      break;
        
  case 9: printf("\n Total number of nodes : %d ", countnode(start));
                 break;
       
      case 10 : exit(0);
      }
     getch();
   }
}

Prev Next

Singly Linked List - Insertion Algorithm - Data Structures

Prev Next

---

In this section, we will see how a new node is added into an already existing linked list. There are five situation for inserting new node. They are as follows...

1. Inserting At Beginning of the list
2. Inserting At End of the list
3. Inserting a node at a specific position
4. Inserting after a given node
5. Inserting before a given node

Inserting a new node in beginning of linked list

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode()

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

NEW_NODE -> NEXT = START
START = NEW_NODE

Step 4 : EXIT

Inserting a node at the end of a linked list

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

PTR = START
while(PTR->NEXT !=NULL)
{
PTR = PTR->NEXT
}
PTR->NEXT = NEW_NODE

Step 4 : EXIT

Counting total no of nodes in a singly linked list

int countnode(node *ptr)
{

int num_of_node=0;
while(ptr != NULL)
{

num_of_node++;
ptr = ptr -> next;

}

return (num_of_node);

}

Inserting a node at a specific position / mid in a linked list

Step 1: Enter the position where u want to insert the node & count total no of node

totalnode = countnode(START)

Step 2: Ensure that enter postion is in between first and last node

IF( POS > 1 && POS < totalnode)

Step 3: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 4: Store the starting address in PTR & move the PTR pointer upto specified position

PTR = START;
MOVE = 1;
while( MOVE < POS-1 )
{
PTR = PTR->NEXT;
MOVE++;
}
NEWNODE -> NEXT = PTR -> NEXT;
PTR -> NEXT = NEWNODE;
[END OF IF]

ELSE
Write "Position is invalid "

Step 5 : EXIT

Algorithm for traversing a singly linked list

Step 1: If linked list is empthy (START == NULL)

Write "Sorry Buddy list is empthy "

Step 2: PTR = START

while ( PTR != NULL )
{

printf("%d-->",PTR -> DATA);
PTR = PTR -> NEXT

}
printf("X");

Step 3: EXIT

NOTE : List must contain more than two node and node after/before which u want to insert must present in the middle of list

Inserting a node after a given node

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode()

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

PTR = START
while(PTR->DATA !=VALUE)
{
PTR = PTR->NEXT
}
NEW_NODE -> NEXT = PTR->NEXT
PTR->NEXT = NEW_NODE

Step 4 : EXIT

Inserting a node before a given node

Step 1: Create the NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

PTR = START
while(PTR->NEXT->DATA !=NUM)
{
PTR = PTR->NEXT }
NEW_NODE -> NEXT = PTR->NEXT
PTR->NEXT = NEW_NODE

Step 4 : EXIT

Prev Next

Singly Linked List - Data Structures

Singly Linked List

Prev Next

---

A single linked list is one in which all nodes are linked together in sequential manner . It is also called as linear linked list.

The beginning of the linked list is stored in a "START" pointer which points to the first node. The first node contains a pointer to the second node. The second node contains a pointer to the third node, ... and so on. The last node in the list has its next field set to NULL to mark the end of the list. You can access any node in the list by starting at the start and following the next pointers.

Next part of the last node must be NULL

Operation

In a singly linked list we perform the following basic operations

1. Creation
2. Insertion
3. Deletion
4. Traversing

Creating a node for Single Linked List:

Creating a singly linked list starts with creating a node. Depending on node declaration sufficient memory is allocated in the heap section using malloc() function. After allocating memory for the structure of type node, read data from the user and assign it to newnode data part and assign newnode next part to NULL.

Structure of a Singly linked list

struct LinkedList

{

int data;

struct LinkedList *next;

};

typedef struct LinkedList node;

node *start = NULL;

Creating a node for Singly Linked List

node* createnode()

{

node* newnode;

newnode = (node *) malloc(sizeof(node));

printf("\n Enter the data: ");

scanf("%d", &newnode -> data);

newnode -> next = NULL;

return newnode;

}

Creating a Singly Linked List with 'N' number of nodes

Step 1: Create THE NEW_NODE using createnode()

NEW_NODE = createnode();

Step 2: If the linked list is empthy (START == NULL)

START = NEW_NODE

Step 3: If the linked list is not empthy

PTR = START
while(PTR -> NEXT!=NULL)
{ PTR = PTR -> NEXT }
PTR -> NEXT = NEW_NODE

Step 4 : Repeat Steps 1,2,3 'N' times.

Step 5 : EXIT

Prev Next