. . .

What is a link list? Describe it with a C program?

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

A linked list is a data structure used to maintain a dynamic series of data. Think of a linked list as a line of bogies of the train where each bogie is connected on to the next bogie. If you know where the first bogie is, you can follow its link to the next one. By following links, you can find any bogie of the train. When you get to a bogie that isn’t holding (linked) on to another bogie, you know you are at the end.

Linked lists work in the same way, except programmers usually refer to nodes instead of bogies. A single node is defined in the same way as any other user-defined type or object, except that it also contains a pointer to a variable of the same type as itself.

Figure 3.1: A Singly linked list

We will be seeing how the linked list is stored in the memory of the computer. In the following Figure 3.1, we can see that start is a pointer which is pointing to the node.

Now, we will see a single link list program with a pointer function

#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;
   
   while(1) {
      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;
}



/*insert_at_begin function*/

void insert_at_begin(int x) {
      struct node *t;    ///t used for new node

   t = (struct node*)malloc(sizeof(struct node));   
   count++;    

   if (start == NULL) {     // checking if there is no node in the linked list
      start = t;            // assigning the start/head with a new node
      start->data = x;      
      start->next = NULL;   
      return;               
   }

   t->data = x;        // assigning the new node with the inputted number
   t->next = start;    
   start = t;            // making the new node start/head
}


/*end of insert_at_begin function*/


/*insert_at_end function*/

void insert_at_end(int x) {
   struct node *t, *temp;    

   t = (struct node*)malloc(sizeof(struct node));   // creating node
   count++;     //incrementing number of node in the linked list

   if (start == NULL) {     
      start = t;            // assigning the start/head with a new node
      start->data = x;      // assigning first node's data with the inputed number
      start->next = NULL;  
      return;               // exiting the function to avoid next lines
   }

   temp = start;            

   while (temp->next != NULL)  //    searching for the last node
      temp = temp->next;       // moving to the next node

   temp->next = t;    //  adding a node at the end (on the last node's link)
   t->data    = x;       //  assigning the last node's data with number
   t->next    = NULL;  
}

/*end of insert_at_end function*/


/*traverse function*/

void traverse() {
   struct node *t;       // it is used for assinging the new node

   t = start;            // assigning the start/head with a new node
   
   if (t == NULL) {  // if that node is null print that linked list is empty
      printf("Linked list is empty.\n");
      return;             // return the value of linked list
   }
   
   printf("There are %d elements in linked list.\n", count); 

   while (t->next != NULL) {    
      printf("%d\n", t->data);  // print the colected data from node
      t = t->next;              // moves to the next data
   }
   printf("%d\n", t->data);      // prints the collected data
}

/*end of traverse function*/


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);
}
OUTPUT
Please share the article

Leave a Reply

Your email address will not be published. Required fields are marked *

nine + fifteen =