You are here

Linked list in c

Linked list in c: Linked list data structure is very useful and has many advantages. New element can be inserted at beginning or end in a constant time (in doubly linked lists). Memory is utilized efficiently as it is allocated when we add new element to list and we can increase list size as desired till all of computer memory is exhausted. Linked lists are useful when size of list is unknown and changes frequenly. Linked list data structure uses node which is represented below. It contains data to be stored and pointer to next node.

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

There are many variants of linked lists such as circular linked list in which last node contains address of first node, doubly linked lists in which every node contains pointers to previous and next nodes and circular doubly linked lists which is a circular doubly linked lists.

C program to implement linked list using pointers

#include <stdio.h>
#include <stdlib.h>
 
struct node {
   int data;
   struct node *next;
};
 
struct node *start = NULL;
void insert_at_begin(int);
void insert_at_end(int);
void traverse();
void delete_from_begin();
void delete_from_end();
int count = 0;
 
int main () {
   int input, data;
 
   for (;;) {
      printf("1. Insert an element at beginning of linked list.\n");
      printf("2. Insert an element at end of linked list.\n");
      printf("3. Traverse linked list.\n");
      printf("4. Delete element from beginning.\n");
      printf("5. Delete element from end.\n");
      printf("6. Exit\n");
 
      scanf("%d", &input);
 
      if (input == 1) {
         printf("Enter value of element\n");
         scanf("%d", &data);
         insert_at_begin(data);
      }
      else if (input == 2) {
         printf("Enter value of element\n");
         scanf("%d", &data);
         insert_at_end(data);
      }
      else if (input == 3)
         traverse();
      else if (input == 4)
         delete_from_begin();   
      else if (input == 5)
         delete_from_end();
      else if (input == 6)
         break;
      else
         printf("Please enter valid input.\n");      
   }
 
   return 0;
}
 
void insert_at_begin(int x) {
   struct node *t;
 
   t = (struct node*)malloc(sizeof(struct node));
   count++;
 
   if (start == NULL) {
      start = t;
      start->data = x;
      start->next = NULL;
      return;
   }
 
   t->data = x;
   t->next = start;
   start = t;
}
 
void insert_at_end(int x) {
   struct node *t, *temp;
 
   t = (struct node*)malloc(sizeof(struct node));
   count++;
 
   if (start == NULL) {
      start = t;
      start->data = x;
      start->next = NULL;
      return;
   }
 
   temp = start;
 
   while (temp->next != NULL)
      temp = temp->next;   
 
   temp->next = t;
   t->data    = x;
   t->next    = NULL;
}
 
void traverse() {
   struct node *t;
 
   t = start;
 
   if (t == NULL) {
      printf("Linked list is empty.\n");
      return;
   }
 
   printf("There are %d elements in linked list.\n", count);
 
   while (t->next != NULL) {
      printf("%d\n", t->data);
      t = t->next;
   }
   printf("%d\n", t->data);
}
 
void delete_from_begin() {
   struct node *t;
   int n;
 
   if (start == NULL) {
      printf("Linked list is already empty.\n");
      return;
   }
 
   n = start->data;
   t = start->next;
   free(start);
   start = t;
   count--;
 
   printf("%d deleted from beginning successfully.\n", n);
}
 
void delete_from_end() {
   struct node *t, *u;
   int n;
 
   if (start == NULL) {
      printf("Linked list is already empty.\n");
      return;
   }
 
   count--;
 
   if (start->next == NULL) {
      n = start->data;
      free(start);
      start = NULL;
      printf("%d deleted from end successfully.\n", n);
      return;
   }
 
   t = start;
 
   while (t->next != NULL) {
      u = t;
      t = t->next;
   }
 
   n = t->data;
   u->next = NULL;
   free(t);
 
   printf("%d deleted from end successfully.\n", n);
}

Arrays should be used when size of data to be stored is known in advance and does not changes frequently. Disadvantage of linked list is that we can not access every element in constant time as in array. Understanding linked lists will help you to learn tree data structure.