Linked List in C Programming

From the name, you can easily say that it is used for linking lists together. But to put it in a nice way, you can say that a linked list is the sequence of linked lists which are connected with each other through links. Linked list in C is a linear data structure where the data is stored at different locations and they are linked using pointers. You have to use pointers to implement the linked list data structure.

What is a linked list in C?

A linked list can be defined as a collection of connected nodes. It is a linear data structure. A linked list contains two parts such as:-

• Data Part:- Contains the data of the user.
• Pointer Part:- It points to the next member of the linked list.

In the above image, Head contains the address of the first node. And the last node in the linked list points to NULL.
Nodes are stored at different locations.

Types of Linked List in C:-

There are 3 types of linked list such as:-

• Singly Linked List
• Doubly Linked List
• Circular Linked List

Singly Linked List:-

Singly linked list is the most common linked list among the others. The singly linked list can be traversed only in one direction. It is a collection of ordered sets of elements. In singly linked list, Each node has a data and a pointer to the next node.

Syntax:-

struct node{
    int data;
    struct node *next;
}

Below, we have created a singly linked list of three members.

// Node Initializing!
struct node *HEAD;
struct node *ONE = NULL;
struct node *TWO = NULL;
struct node *THREE = NULL;

// Allocating memory!
ONE = malloc(sizeof(struct node));
TWO = malloc(sizeof(struct node));
THREE = malloc(sizeof(struct node));

// Assigning the values of data!
ONE->data = 23;
TWO->data = 34;
THREE->data = 90;

// Connecting nodes with each other!
ONE->next = TWO;
TWO->next = THREE;
THREE->next = NULL;

// Saving the address of first node
HEAD = ONE;

Doubly Linked List in C:-

In the doubly linked list, we add a pointer to the previous node and also to the next node. The Doubly linked list can be traversed in two directions such as forward and backward.

Syntax:-

struct node {
    int data;
    struct node *next_node;
    struct node *previous_node;
}

Below, We created a doubly-linked list of three members.

// Node Initializing!
struct node *HEAD;
struct node *ONE = NULL;
struct node *TWO = NULL;
struct node *THREE = NULL;

// Allocating memory!
ONE = malloc(sizeof(struct node));
TWO = malloc(sizeof(struct node));
THREE = malloc(sizeof(struct node));

// Assigning the values of data!
ONE->data = 2;
TWO->data = 4;
THREE->data = 9;

// Connecting nodes with each other!
ONE->next_node = TWO;
ONE->previous_node = NULL;
TWO->next_node = THREE;
TWO->previous_node = ONE;
THREE->next_node = NULL;
THREE->previous_node = TWO;

// Saving the address of first node
HEAD = ONE;

Circular Linked List in C:-

In a circular linked list, the last element of the list points to the first element of the list. That’s why it is called a circular linked list.

You can create a circular linked list with the help of a singly or doubly linked list. Below, we created a circular linked list of three members.

// Node Initializing!
struct node *HEAD;
struct node *ONE = NULL;
struct node *TWO = NULL;
struct node *THREE = NULL;

// Allocating memory!
ONE = malloc(sizeof(struct node));
TWO = malloc(sizeof(struct node));
THREE = malloc(sizeof(struct node));

// Assigning the values of data!
ONE->data = 1;
TWO->data = 2;
THREE->data = 3;

// Connecting nodes with each other!
ONE->next = TWO;
TWO->next = THREE;
THREE->next = ONE;

// Saving the address of first node
HEAD = ONE;

Reasons to use linked list over array:-

There are several advantages and disadvantages while using an array. But with a linked list, you can overcome the problems while using an array.
If you use array in the program code then you will find these following limitations:-

• You have to know the size of the array before using it in the program code.
• The elements of the array are stored in contiguous memory locations.
• You cannot increase the size of the array at run time.
  To prevent the above limitations, you can make use of Linked List.
• In the linked list, we do not have to define the size during declaration.
• Linked list dynamically allocates the memory. It is not like an array. The nodes are stored at non-contiguous memory locations.

Uses of Linked List in C:-

• Each and every node must have data stored into it.
• You don’t have to declare the size during declaration. It is limited to memory size.
• In a singly linked list, you can store the values of primitive types or objects.

Complexity of Linked List:-

Linked List Time Complexity:-

Linked List Space Complexity:-

Space Complexity of Linked List:- O(n)

Performing operations on Singly Linked List:-

Below is a list of operations which you can perform upon a Singly Linked List.

1. Creating Nodes in Linked List

struct node   
{  
int data;   
struct node *next;  
};  
struct node *HEAD, *point;   
point = (struct node *)malloc(sizeof(struct node *));

2. Insertion in Linked list

In a Singly linked list, you can perform insertion at different locations.

3. Deletion, Traversing and Searching in Linked List

In a singly linked list, you can perform deletion at different locations.

4. Iterating over a list:-

Below I have added a function which will print all the items on a list through iterating. First, we have to set a pointer that will keep track of the nodes which we are about to print.

void list_printing(node_exist * HEAD) {
    node_exist * ptr = HEAD;

    while (ptr != NULL) {
        printf("%d\n", ptr->value);
        ptr = ptr->next;
    }
}

5. Inserting Item at the end of the Linked list:-

In the above section, we learnt how to iterate over a list. You can also add an item at the end of the list.

void add(node_exist * HEAD, int value) {
    node_exist * ptr = HEAD;
    while (ptr->next != NULL) {
        ptr = ptr->next;
    }

    // adding a new variable!
    ptr->next = (node_exist *) malloc(sizeof(node_exist));
    ptr->next->value = value;
    ptr->next->next = NULL;
}

6. Adding an item to the beginning of a linked list:-

You have to follow the below guides to add an item to the beginning of a linked list:-

• First, you have to create a new item and set the value of the item.
• Then, you have to point the new item to the head of the list.
• And then, you have to set the new item as the head of the list.

We have to add a double pointer so that we can change the pointer itself.
Code:-

void add_to_beginning(node_exist ** HEAD, int value) {
    node_exist * new_node_create;
    new_node_create = (node_exist *) malloc(sizeof(node_exist));

    new_node_create->value = value;
    new_node_create->next = *HEAD;
    *HEAD = new_node_create;
}

7. Remove the first item from the linked list:-

To remove the first item from a list, do the following:-

• First, take the next item which head points to and save it.
• Then, free the head.
• And, then you set the head item to be the next item which we have stored.

Code:-

int remove_first(node_exist ** HEAD) {
    int ret = -1;
    node_exist * next_node = NULL;

    if (*HEAD == NULL) {
        return -1;
    }

    next_node = (*HEAD)->next;
    ret = (*HEAD)->value;
    free(*HEAD);
    *HEAD = next_node;

    return ret;
}

8. Remove the last item from the linked list:-

You can also remove the last item from a linked list. It is very similar to adding an item at the beginning of a linked list.
Code:-

int remove_last_item(node_exist * HEAD) {
    int ret = 0;
    if (HEAD->next == NULL) {
        ret = HEAD->val;
        free(HEAD);
        return ret;
    }

    // second last of the linked list!
    node_exist * ptr = HEAD;
    while (ptr->next->next != NULL) {
        ptr = ptr->next;
    }

    // ptr pointer points to the second last of the linked list, so doing the remove!
    ret = ptr->next->value;
    free(ptr->next);
    ptr->next = NULL;
    return ret;
}

9. Popping out a specific item from the list:-

You have to follow the below algorithm to remove a specific item from the linked list:-

• First, iterate over the node before the node you want to delete.
• Then, save the node which you want to delete on a temporary pointer.
• Next, you have to set the previous node’s next pointer point to the node after the node which you want to delete.
• Then, you can delete the node using the temporary pointer.

Code:-

int remove_specific(node_exist ** HEAD, int a) {
    int i = 0;
    int ret = -1;
    node_exist * ptr = *HEAD;
    node_exist * temporary_node = NULL;

    if (a == 0) {
        return remove_first(HEAD);
    }

    for (i = 0; i < a-1; i++) {
        if (ptr->next == NULL) {
            return -1;
        }
        ptr = ptr->next;
    }

    temporary_node = ptr->next;
    ret = temporary_node->value;
    ptr->next = temporary_node->next;
    free(temporary_node);

    return ret;

}

Example:- Performing Operations on Singly Linked List

#include<stdio.h>  
#include<stdlib.h>  
struct node   
{  
  int data;  
  struct node *next;   
};  
struct node *HEAD;  
 
void insert_at_begin();   
void insert_at_last();  
void insert_random();  
void delete_at_begin();  
void delete_at_last();  
void delete_random();  
void print();  
void searching();  
void main()  
{  
  int your_choice=0;  
  while(your_choice != 9)   
  {
    	printf("\n**************************************\n");
    	printf("\n\nTechVidvan Tutorial: Performing operations on Singly Linked List!\n\n");
    	printf("Choose an option from the below list!\n");  
    	printf("\n**************************************\n");  
    	printf("1.Do insertion at beginning of the list!\n2.Do insertion at last!\n3.Do insertion at random location!\n4.Do deletion from the beginning of the list!\n5.Do deletion at the last of the list!\n6.Do deletion of a node after a specified node!\n7.Perform a searching operation for an element!\n8.Display!\n9.Exit!\n");  
    	printf("\nEnter your choice?\n");    	 
    	scanf("\n%d",&your_choice);  
    	switch(your_choice)  
    	{  
        	case 1:  
        	insert_at_begin(); 	 
        	break;  
        	case 2:  
        	insert_at_last();    	 
        	break;  
        	case 3:  
        	insert_at_last();  	 
        	break;  
        	case 4:  
        	delete_at_begin();  	 
        	break;  
        	case 5:  
        	delete_at_last();   	 
        	break;  
        	case 6:  
        	delete_random();     	 
        	break;  
        	case 7:  
        	searching();    	 
        	break;  
        	case 8:  
        	print();   	 
        	break;  
        	case 9:  
        	exit(0);  
        	break;  
        	default:  
        	printf("Please enter a choice from the following list!");  
    	}  
  }  
}  
void insert_at_begin()  
{  
  struct node *point;  
  int value;  
  point = (struct node *) malloc(sizeof(struct node *));  
  if(point == NULL)  
  {  
    	printf("\nInvalid!!");  
  }  
  else  
  {  
    	printf("\nEnter the value: \n");    
    	scanf("%d",&value);    
    	point->data = value;  
    	point->next = HEAD;  
    	HEAD = point;  
    	printf("\nNice, The Node is inserted at the beginning!");  
  }  
 	 
}  
void insert_at_last()  
{  
  struct node *point,*tmp;  
  int value;	 
  point = (struct node*)malloc(sizeof(struct node)); 	 
  if(point == NULL)  
  {  
    	printf("\nInvalid!!");	 
  }  
  else  
  {  
    	printf("\nEnter the value: \n");  
    	scanf("%d",&value);  
    	point->data = value;  
    	if(HEAD == NULL)  
    	{  
        	point -> next = NULL;  
        	HEAD = point;  
        	printf("\nNice, The Node is inserted!");  
    	}  
    	else  
    	{  
        	tmp = HEAD;  
        	while (tmp -> next != NULL)  
        	{  
            	tmp = tmp -> next;  
        	}  
        	tmp->next = point;  
        	point->next = NULL;  
        	printf("\nNice, The Node is inserted!");  
     	 
    	}  
  }  
}  
void insert_random()  
{  
  int a,pos,value;   
  struct node *point, *tmp;  
  point = (struct node *) malloc (sizeof(struct node));  
  if(point == NULL)  
  {  
    	printf("\nInvalid!!");  
  }  
  else  
  {  
    	printf("\nEnter the value of element: ");  
    	scanf("%d",&value);  
    	point->data = value;  
    	printf("\nEnter the position where you want to insert: ");  
    	scanf("\n%d",&pos);  
    	tmp=HEAD;  
    	for(a=0;a<pos;a++)  
    	{  
        	tmp = tmp->next;  
        	if(tmp == NULL)  
        	{  
            	printf("\nSorry, but you cannot insert!\n");  
            	return;  
        	}  
     	 
    	}  
    	point ->next = tmp ->next;   
    	tmp ->next = point;   
    	printf("\nNice, The Node is inserted at your given location!");  
  }  
}  
void delete_at_begin()  
{  
  struct node *point;  
  if(HEAD == NULL)  
  {  
    	printf("\nThe List is empty!\n");  
  }  
  else   
  {  
    	point = HEAD;  
    	HEAD = point->next;  
    	free(point);  
    	printf("\nThe node is deleted from the beginning!\n");  
  }  
}  
void delete_at_last()  
{  
  struct node *point,*point1;  
  if(HEAD == NULL)  
  {  
    	printf("\nThe List is empty!");  
  }  
  else if(HEAD -> next == NULL)  
  {  
    	HEAD = NULL;  
    	free(HEAD);  
    	printf("\nOne node is deleted from the list!\n");  
  }  
  else  
  {  
    	point = HEAD;   
    	while(point->next != NULL)  
    	{  
        	point1 = point;  
        	point = point ->next;  
    	}  
    	point1->next = NULL;  
    	free(point);  
    	printf("\nThe Node is deleted from the last of the node!\n");  
  }	 
}  
void delete_random()  
{  
  struct node *point,*point1;  
  int pos,a;    
  printf("\nEnter the position of the node after which you want to delete!\n");  
  scanf("%d",&pos);  
  point=HEAD;  
  for(a=0;a<pos;a++)  
  {  
    	point1 = point;  	 
    	point = point->next;  
         	 
    	if(point == NULL)  
    	{  
        	printf("\nSorry, but you cannot delete!");  
        	return;  
    	}  
  }  
  point1 ->next = point ->next;  
  free(point);  
  printf("\nThe Node is deleted at location: %d",pos+1);  
}  
void searching()  
{  
  struct node *point;  
  int value,a=0,count;  
  point = HEAD;   
  if(point == NULL)  
  {  
    	printf("\nSorry, but the list is empty!\n");  
  }  
  else  
  {   
    	printf("\nEnter the value which you want to search: \n");   
    	scanf("%d",&value);  
    	while (point!=NULL)  
    	{  
        	if(point->data == value)  
        	{  
            	printf("The value which you searched for, found at: %d ",a+1);  
            	count=0;  
        	}   
        	else  
        	{  
            	count=1;  
        	}  
        	a++;  
        	point = point -> next;  
    	}  
  if(count==1)  
  {  
    	printf("Sorry, the value is not found!\n");  
  }  
  }	 
     	 
}  
 
void print()  
{  
  struct node *point;  
  point = HEAD;   
  if(point == NULL)  
  {  
    	printf("Please enter something to print!");  
  }  
  else  
  {  
    	printf("\nPrinting the values!\n");   
    	while (point!=NULL)  
    	{  
        	printf("\n%d",point->data);  
        	point = point -> next;  
    	}  
  }  
}

Output:-

Applications of Linked List in C:-

• You can use linked lists on graphs and hash tables.
• In stack and queue, you can implement linked lists.
• With the help of linked lists, you can do dynamic memory allocation.
• With a linked list, you can perform arithmetic operations on long integers.

Advantages of Linked List in C:-

• It is a dynamic data structure.
• You can decrease and increase the size of the linked list at run time.
• In the linked list, you can easily insert and delete a node.
• It’s access time is very fast.
• In the linked list, memory is well utilized.

Disadvantages of Linked List in C:-

• It requires more memory than an array.
• It is difficult to traverse the nodes in a linked list.
• Reverse traversing is very difficult to implement in a linked list.

Difference between Linked List and Array:-

Summary:-

In this tutorial, we learnt about linked lists in C in depth. We discussed what is a linked list and what are the types of linked list in C. We also discussed different operations you can perform on a linked list in C in detail. Then we talked about the advantages, disadvantages, applications and usage of Linked Lis in Ct. We also discussed the difference between an array and a linked list and what is the benefit of using linked lists over an array. We also wrote a code which will perform different operations on a linked list.