Linked Lists – Implementation in C

QuantumO0O

Linked Lists – Implementation in C

The Linked list is a chain of structures in which each structure consists of data as well as the pointer, which stores the address (link) of the next logical structure in the list.

 
We will be seeing how the linked list is stored in the memory of the computer.  We can assume that start is a pointer that is pointing to the node which contains data as Madan and the node Madan is pointing to the node Mohan and the last node babu is not pointing to any node. 1000, 1050, 1200 are memory addresses.

 


 typedef struct
{
  int count;
  int entry[100];
} list;

Once you define a list node, you can create a list by simply using the pointer to the first element that is “head”.

list *head


We can see if the list is empty, see the following example

 #include <stdio.h>

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

int main() {
   list * head = NULL; /* initialize list head to NULL */
   if (head == NULL) {
      printf("The list is empty!\n");
   }
}


Creation of a linked list

Now, we look to the process of the addition of a new node to the list with the function create.

#include<stdio.h>
#include<stdlib.h>
#define NULL 0

typedef struct linked_list list;

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

//definition of create function
void create(list * start) {
      printf("inputthe element -1111 for coming oout of the loop\n");
      scanf("%d", & start -> data);

      if (start -> data == -1111)
         start -> next = NULL;
      else {
         //memory allocation of next node
         start -> next = (list * ) malloc(sizeof(list));
         create(start -> next);
      }
   }
    ........


void main() {
    ........
   void create(list * );
   //call create function
   create(head);
    ........

}


Traverse of a linked list

Now, we look at the process of the traverse of the list with the function traverse.


#include<stdio.h>
#include<stdlib.h>
#define NULL 0

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

//defination of traverse function
void traverse(list * start) {
   /*check the endpoint. In our list only -1111(terminating point) have NULL value in the start->next*/
   if (start -> next != NULL) {
      //print current node data
      printf("%d --> ", start -> data);
      //call traverse function with next node location to print next node element 
      traverse(start -> next);
   }
}

    …….…….

void main() {
   …….…….
   void traverse(list * );
   //call transverse function
   traverse(head);
   …….…….
}


Find the key or element of a linked list

Now, we look to the process of the find the node in the list with function find.


#include<stdio.h>
#include<stdlib.h>
#define NULL 0

struct linked_list {
   int data;
   struct linked_list * next;
};
……………..

/*definition of find function */
list * find(list * start, int key) {
   //check the in next node element is == key 
   if (start -> next -> data == key)
      // return the locate of just privious node from insertion or deletion point node
      return (start);
   //check is this list end?
   if (start -> next -> next == NULL)
      return (NULL);
   else
      //if list not end move next node and again call find function again
      find(start -> next, key);
} 
……..……..


Insert the Node or element of a linked list

Now, we look to the process to Insert the node in the list with the function Insert.


……..……..

list * insert_list(list * );
/*definition of insert function */
list * insert_list(list * start) {
   list * n, * f;
   /*"key" is element of node data or element of list, just before that where new element will add*/
   int key, element;
   printf("enter value of new element");
   scanf("%d", & element);
   printf("eneter value of key element");
   scanf("%d", & key);
   if (start -> data == key) {
      //memory allocation of new node
      n = (list * ) malloc(sizeof(list));
      n -> data = element;
      //copy the address of next node in inserted node from privious node
      n -> next = start;
      //copy the address of inserted node in privious node
      start = n;
   } else {
      // call the find function for locate the just previous node from insertion point node
      f = find(start, key);

      if (f == NULL)
         printf("\n key is not found \n");
      else {
         //memory allocation of new node
         n = (list * ) malloc(sizeof(list));
         n -> data = element;
         //copy the address of next node in inserted node from previous node
         n -> next = f -> next;
         //copy the address of inserted node in previous node
         f -> next = n;
      }
   }
   return (start);
}

void main() {
 …….…….
   head = insert_list(head);
   printf(" \n traversing the list after insert \n");
   traverse(head);
   …….…….
}



Delete the Node or element of a linked list

Now, we look to the process to Delete the node in the list with the function Delete.


……..…….
/* prototype of delete_function */
list * delete_list(list * );

/*definition of delete_list */
list * delete_list(list * start) {
   //"key" is element of node data which need to delete 
   int key;
   list * f, * temp;
   printf("\n enter the value of element to be deleted \n");
   scanf("%d", & key);

   //if element to be deleted is first node
   if (start -> data == key) {
      //copy second node address in temp
      temp = start -> next;
      //free the current node
      free(start);
      //make second node starting of the list
      start = temp;
   } else {
      /*if element to be deleted is not first node, we need to find
      locate of just privious node from deletion  node*/
      f = find(start, key);

      if (f == NULL)
         printf("“\n key not fund”");
      else {
         //copy next node address of delete node in temp   
         temp = f -> next -> next;
         //free the addree of deletion node in privious node,
         free(f -> next);
         //copy the next node address from deletion node into the privious node 
         f -> next = temp;
      }
   }
   return (start);
}

void main() {
   …….…….
   head = delete_list(head);
   printf("“ \n traversing the list after delete_list \n”");
   traverse(head);
   …….…….
}

 

Count the Node or element of a linked list

Now, we look to the process to count the node in the list with function count.

 

…… …...
//count the number of list
int count(list * start) {
/*check the endpoint, In our list only 
    -1111(terminating point) have NULL value in the start->next*/
    if (start -> next == NULL)
        return 0;
    else
    //return until endpoint with 1 increament everytime
        return (1 + count(start -> next));
}

……. ……

 

Create, Insert & Delete in the Link List

 Now, we look to the process to Create, Insert & Delete the node in the list 

#include <stdio.h>
#include <stdlib.h>
#define NULL 0

struct linked_list {
   int data;
   struct linked_list * next;
};
typedef struct linked_list list;

// definition of create function
void create(list * start) {
   printf("inputthe element -1111 for coming oout of the loop\n");
   scanf("%d", & start -> data);
   /*if element vulue is -1111 than list will terminat*/
   if (start -> data == -1111)
      start -> next = NULL;
   else {
      // memory allocation of next node
      start -> next = (list * ) malloc(sizeof(list));
      // call the create function with memory allocation of next node
      create(start -> next);
   }
}

// defination of traverse function
void traverse(list * start) {
   /*check the endpoint, In our list only
   -1111(terminating point) have NULL value in the start->next*/
   if (start -> next != NULL) {
      // print current node data
      printf("%d --> ", start -> data);
      // call traverse function with next node location
      traverse(start -> next);
   }
}

// count the number of list
int count(list * start) {
   /*check the endpoint, In our list only
       -1111(terminating point) have NULL value in the start->next*/
   if (start -> next == NULL)
      return 0;
   else
      // return until endpoint with 1 increament everytime
      return (1 + count(start -> next));
}

/*prototypes of insert and find functions */
list * insert_list(list * );
list * find(list * , int);

/*definition of insert function */
list * insert_list(list * start) {
   list * n, * f;
   //"key" is element of node data or element of list, just before that where new
   // element will add
   int key, element;
   printf("enter value of new element");
   scanf("%d", & element);
   printf("eneter value of key element");
   scanf("%d", & key);
   if (start -> data == key) {
      // memory allocation of new node
      n = (list * ) malloc(sizeof(list));
      n -> data = element;
      // copy the address of next node in inserted node from privious node
      n -> next = start;
      // copy the address of inserted node in privious node
      start = n;
   } else {
      // call the find function for locate the just privious node from insertion
      // point node
      f = find(start, key);

      if (f == NULL)
         printf("\n key is not found \n");
      else {
         // memory allocation of new node
         n = (list * ) malloc(sizeof(list));
         n -> data = element;
         // copy the address of next node in inserted node from privious node
         n -> next = f -> next;
         // copy the address of inserted node in privious node
         f -> next = n;
      }
   }

   return (start);
}

/*definition of find function */
list * find(list * start, int key) {
   // check the in next node element is == key
   if (start -> next -> data == key)
      // return the locate of just privious node from insertion point node
      return (start);
   // check is this list end?
   if (start -> next -> next == NULL)
      return (NULL);
   else
      // if list not end move next node and again call find function
      find(start -> next, key);
}

/*prototype of delete_function */
list * delete_list(list * );

/*definition of delete_list */
list * delete_list(list * start) {
   //"key" is element of node data which need to delete
   int key;
   list * f, * temp;
   printf("\n enter the value of element to be deleted \n");
   scanf("%d", & key);

   // if element to be deleted is first node
   if (start -> data == key) {
      // copy second node address in temp
      temp = start -> next;
      // free the current node
      free(start);
      // make second node starting of the list
      start = temp;
   } else {
      /*if element to be deleted is not first node, we need to find
      locate of just privious node from deletion  node*/
      f = find(start, key);

      if (f == NULL)
         printf("“\n key not fund”");
      else {
         // copy next node address of delete node in temp
         temp = f -> next -> next;
         // free the addree of deletion node in privious node,
         free(f -> next);
         // copy the next node address from deletion node into the privious node
         f -> next = temp;
      }
   }

   return (start);
}

void main() {
   list * head;
   // prototypes of functions
   void create(list * );
   int count(list * );
   void traverse(list * );
   head = (list * ) malloc(sizeof(list));
   // call create function
   create(head);
   printf(" \n traversing the list \n");
   // call transverse function
   traverse(head);
   printf("\n number of elements in the list %d \n", count(head));
   head = insert_list(head);
   printf(" \n traversing the list after insert \n");
   traverse(head);
   head = delete_list(head);
   printf("\n traversing the list after delete_list \n");
   traverse(head);
}


  
#IGNOU

0 Comments