Singly Linked list

Singly Linked list

A singly linked list is a kind of linked list which is unidirectional. If we talk about singly linked list, then we can say it can be traversed in only one direction from head of linked list to the tail of the linked list.

The basic building block of linked list is called node. A single node contains two things, first is data and second is a pointer of the next node which helps us to maintain the structure of the list.

The first node of the linked list is called head; it contains the starting address of the linked list and same as the last node is called as tail, points to NULL, which helps us to determine when the list ends.

Operations on Singly Linked List

• Insert a node in the linked list:

We can insert a node into the linked list at the front, the end or anywhere in the linked list. The time complexity of these operations is as follows:

• If we insert the node at the front of linked list; takes O(1)
• If we insert the node at the end of linked list; takes O(n)
• If we insert the node anywhere in the linked list; takes O(n)

• Remove a node from the linked list:

We can remove a node from the front of the linked list, the end or anywhere of the linked list. The time complexity of these operations is as follows:

• If we remove the node from the front of linked list; takes O(1)
• If we remove the node from the end of linked list; takes O(n)
• If we remove the node from anywhere in the linked list; takes O(n)

• Search a node in the linked list:

Searching a node in the linked list takes O(n) time in the worst case.

Singly Linked List Program in C Language: -

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node *next;
 };
 struct node *start=NULL;
 void begin(int item)
 {
     struct node *p,*t;
     p=start;
     t=(struct node *)malloc(sizeof(struct node ));
     start=t;
     start -> info=item;
     start -> next=p;
     return;
 }
 void Specificposition(int item,int pos)
 {
     int i;
 struct node *t, *p, *temp;
 p=start;
 t=(struct node *)malloc(sizeof(struct node ));
 for(i=1; i<pos-1; i++)
 {
     p=p -> next;
 }
   temp = p -> next;
   t -> next = temp;
   t -> info = item;
   p -> next = t;
 }
 void End(int item)
 {
 struct node *t, *p;
 t=(struct node *)malloc(sizeof(struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node *p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 void delbegin()
 {
     struct node *t,*p;
     p = start;
     t = start -> next;
     start = t;
     free(p);
 }
 void delend()
 {
      struct node *t;
      t = start;
      while(t -> next -> next!=NULL)
      {
          t = t -> next;
      }
      t -> next = NULL;
      return;
 }
 void delspecificposition(int pos)
 {
     int i;
     struct node *t,*p;
     t=start;
    for(i=1;i<pos-1;i++)
    {
        t=t -> next;
    }
    t -> next=t -> next -> next;
     return;
 }
 void traverse(struct node * t)
 {
 if(t==NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next!=NULL)
                                     {
                         printf("%d -> ",t -> info);
                         t=t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 void main()
 {
     int n,pos,item;
 while(1)
 {
 printf(" 1. insert at begin");
 printf("\n 2. insert at specific position");
 printf("\n 3. insert at End");
 printf("\n 4. delete at beginning");
 printf("\n 5. delete specific position");
 printf("\n 6. delete at End");
 printf("\n 7. Traverse the list");
 printf("\n 8.Exit\n");
 printf("Enter the choice:-\n");
 scanf("%d",&n);
 switch(n)
 {
 case 1:
        printf("enter the item do wanna insert:-\n");
        scanf("%d",&item);
        begin(item);
        break;
 case 2:
      printf("enter the position where do wanna insert:-\n");
      scanf("%d",&pos);
      printf("enter the item do wanna insert at position:-\n");
      scanf("%d",&item);
      Specificposition(item,pos);
      break;
 case 3:
        printf("enter the item do wanna insert at end:-\n");
        scanf("%d",&item);
        End(item);
        break;
 case 4:
        delbegin();
        break;
 case 5:
        printf("enter the position which do wanna delete :-\n");
        scanf("%d",&pos);
        delspecificposition(pos);
        break;
 case 6:
       delend();
       break;
 case 7:
        printf("your list is:");
        traverse(start);
        break;
 case 8:
         exit(0);
 }
 }
 } 

Output: -