Singly Linked List

A linked list is a way to store a collection of elements. Like an array, these can be character or integers. Each element in a linked list is stored in the form of a node.

Declaring a Single Linked list

In C language, a linked list can be implemented using structure and pointers.

struct slink
{
  int data;
  struct slink *next;
};
typedef struct slink LINK;

LINK*head=NULL; //Define node(head) as pointer of data type struct LinkedList

The above definition is used to create every node in the list. The data field stores the element and the next is a pointer to store the address of the next node.

In place of a data type, struct LinkedList is written before next. That’s because of its a self-referencing pointer. It means a pointer that points to whatever it is a part of. Here next is a part of a node and it will point to the next node.typedef is used to define a data type in C.

Creating a node (new Link)

void createlink()
{
  char ch;
  int value;
  LINK*th,*th1;
  if(head==NULL)
  {
    head=(LINK*)malloc(sizeof(LINK)); 
    printf("\nEnter a value: ");
    scanf("%d",&value);
    head->data=value;
    head->next=NULL;
    printf("\nDo You want to continue Y? :);
    fflush(stdin);
    ch=getchar();
    if(ch!='Y'||ch!='y')
     return;
  }
  th=head;
  while(th->next!=NULL)
  th=th->next;
  do
  {
     th1=(LINK*)malloc(sizeof(LINK));
     th->next=th1;
     th=th->next;
     printf("\nEnter a value: ");
     scanf("%d",&value);
     th->data=value;
     th->next=NULL;
     printf("\nDo You want to continue Y? : ");
     fflush(stdin);
     ch=getchar();
  }while(ch=='Y'||ch=='y');
  th=th1=NULL;
  return;
}

Here if HEAD is NULL then always it creates a node at head position. Otherwise, the new node will always be added after the last node. This is known as inserting a node at the rear end.

Single Lined List traversal

void displaylink()
{
   LINK *th;
   if(head==NULL)
   {
     printf("\nLIST IS EMPTY");
     return;
   }
   th=head;
   while(th!=NULL)
   {
     printf("\nData: %d",th->data);
     th=th->next;
   }

   return;   
}

Here is HEAD is NULL it indicates list is empty else travel from beginning to end of list and display all the data.

Finding the Number of Nodes

int linkcount()
{
   LINK *th;
   int count=0;
   if(head==NULL)
     return 0; 

   th=head;
   while(th!=NULL)
   {
     ++count;
     th=th->next;
   }

   return count;
}

Single Lined List Insert Operation

Insertion can be performed on any position, the fallwong code can insert a new node at all possible positions 

void insertlink()
{
   int lp,nl,i;
   LINK *th,*th1;
   int value;
   if(head==NULL) //if list is empty insert at head position
   {
     head=(LINK*)malloc(sizeof(LINK));
     printf("\nEnter a value: ");
     scanf("%d",&value);
     head->data=value;
     head->next=NULL;
     return;
   }
   printf("\nEnter Link position: ");
   scanf("%d",&lp);
   nl=linkcount();
   if(lp<1||lp>nl+1) //validation 
   {
     printf("\ninvalid link position");
     return;
   }
   if(lp==1) // if link position is 1
   {
     th=(LINK*)malloc(sizeof(LINK));
     printf("\nEnter a value: ");
     scanf("%d",&value); 
     th->data=value;
     th->next=head;
     head=th;
     th=NULL;
     return;
   }
   th=head;       //travel to specific position i.e. just before link position
   for(i=1; i<lp-1; i++)
     th=th->next;
   
   th1=(LINK*)malloc(sizeof(LINK));
   printf("\nEnter a value: ");
   scanf("%d",&value);
   th1->data=value;
   th1->next=th->next;
   th->next=th1;
   th1=th=NULL;
   return;
}

Single Lined List Deletion Operation

void deletelink()
{
   int lp,nl,i;
   LINK *th,*th1;
   if(head==NULL)
   {
     printf("\nLIST IS EMPTY");
     return;
   }
   printf("\nEnter Link position for delete: ");
   scanf("%d",&lp);
   nl=linkcount();
   if(lp<1||lp>nl)
   {
     printf("\ninvalid Link position");
     return;
   }
   if(nl==1)
   {
      free(head);
      head=NULL;
      return;
   }
   if(lp==1)
   {
     th=head;
     head=head->next;   //head=th->next;
     th->next=NULL;
     free(th);
     th=NULL;  
     return;
   }
   th=head;
   for(i=1; i<lp-1; i++)
     th=th->next;
   
   th1=th->next;
   th->next=th1->next;
   th1->next=NULL;
   free(th1);
   th1=th=NULL;
   return;
}