Linked List in C


In previous tutorial we learned about stuctures in C. In this note we will use structures to create linked list.

What is linked list.

Linked list is a data structure which is used to store similar type of data in memory. Unlike an array, linked list can grow as well as shrink dynamically.

Pictorial representation of linked list

Each element of the linked list is called Node. Each node has 2 parts :

  1. Data Part - where data is stored.
  2. Link part - where the link of next node is stored. (or the address of next node is stored).

How to create a Node

Create a structure which is having an integer to store data and a variable to store the address of next node.

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

 

Allocating memory for a node to work dynamically

  1. Use header file :
    #include<malloc.h>
  2. Use malloc() to allocate memory
    temp = (struct node*) malloc(sizeof(struct node));

We want to append the data at the end of the list. There are two conditions.

  • If linked list is empty
    struct node *temp, *current;
         temp = (struct node*) malloc(sizeof(struct node));
       temp->data = data;
       if(*p == NULL){
       *p = temp;
       }
  • If linked list is non-empty then find the last element. Assigned the link of last element to the new node.
    current = *p;
           while(current ->link !=NULL){
               current = current -> link;
           }
           current->link = temp;

How to display a linked list

Just traverse through the whole list and keep on displaying the data.

 while(p!=NULL){
       printf("%d\n", p->data);
       p = p->link;
   }

 

Combining all things to create, append and display the nodes of a linked list

#include <stdio.h>
#include<malloc.h>
struct node{
    int data;
    struct node *link;
    };
void addnode(struct node**, int);
main()
{
   struct node *p;
   p = NULL;
   addnode(&p, 10);
   addnode(&p, 12);
   addnode(&p, 39);
   while(p!=NULL){
       printf("%d\n", p->data);
       p = p->link;
   }

}
void addnode(struct node** p, int data){
   struct node *temp, *current;
     temp = (struct node*) malloc(sizeof(struct node));
   temp->data = data;
   if(*p == NULL){
 
   *p = temp;
   }else{
       current = *p;
       while(current ->link !=NULL){
           current = current -> link;
       }
       current->link = temp;
   }
}

Output :

In this tutorial we learned about linked lists in C. In the next tutorial we will learn some more operations related to linked list.