Geekers Point

C program for inserting elements in circular Linkedlist

#include <stdio.h>
#include <stdlib.h>

//structure of node 
struct node{
int data;
struct node *link;
};

 //prototype declaration
void insert(struct node **,struct node **,int );
void display(struct node *);

int main(){
struct node *front;
struct node *rear;
front=rear=NULL;
insert(&front,&rear,10);
insert(&front,&rear,32);
insert(&front,&rear,30);
insert(&front,&rear,50);
insert(&front,&rear,42);
insert(&front,&rear,60);

display(front);
return 0;
}

//inserting elements in the circular linked list 
void insert(struct node **f,struct node **r,int num){
struct node *temp;

//allocating memory for the temp pointer
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;

if((*f)==NULL){
*f=temp;
}
else
(*r)->link=temp;

//last element that is rear sholud point to the front element that is front ,point it's link to front *r=temp;
(*r)->link=*f;

}

//display the elements from front
void display(struct node *f){
struct node *p,*q;
p=NULL;
//q pointer points to the first element that is front
q=f;
while(q!=p){
printf("%d ",q->data);
q=q->link;

p=f;
}
}

 C program to sort  elements in Linkedlist

//we are going to sort the elements in the linkedlist using selection sort having efficiency O(n).
#include <stdio.h>
#include <stdlib.h>

struct node{
    struct node *link;
    int data;
    };
  
    void insert(struct node **,int);
    void display(struct node *);
    int count(struct node *);
    void sort(struct node *);
   
    int main(){
        struct node *s;
        s=NULL;
        insert(&s,70);
        insert(&s,20);
        insert(&s,40);
        insert(&s,50);

        display(s);
        sort(s);
        display(s);
      
        count(s);
        return 0;
    }
  
    void insert(struct node **s,int num){
        struct node *temp;
        temp=(struct node*)malloc(sizeof(struct node));
        temp->data=num;
        temp->link=*s;
        *s=temp;
    }
    void display(struct node *s){
   
        while(s!=NULL){
            printf("%d \n",s->data);
            s=s->link;
        }
        printf("\n");
    }

int count(struct node *s){
        int i;
        i=0;
        while(s!=NULL){
          
            s=s->link;
            i++;
        }
        printf("%d",i);
    }
//Selection sort 
void sort(struct node *s){
   struct node *p,*q;
   int temp;
   p=s;
   while(p!=NULL){
       q=p->link;
       while(q!=NULL){
           if(p->data < q->data){
               temp=p->data;
               p->data=q->data;
               q->data=temp;
               
           }
           q=q->link;
           
       }p=p->link;
   }
   }
 Executing the program....
$demo

50 
40 
20 
70 
After sort
70 
50 
40 
20 

4

  

C PROGRAM FOR TREE (PREORDER TRAVERSAL)

The binary tree is a fundamental data structure used in computer science. The binary tree is a useful data structure for rapidly storing sorted data and rapidly retrieving stored data.

A binary tree is composed of parent nodes, or leaves, each of which stores data and also links to up to two other child nodes (leaves) which can be visualized spatially as below the first node with one placed to the left and with one placed to the right. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure.

The typical graphical representation of a binary tree is essentially that of an upside down tree. It begins with a root node, which contains the original key value. The root node has two child nodes; each child node might have its own child nodes. Ideally, the tree would be structured so that it is a perfectly balanced tree, with each node having the same number of child nodes to its left and to its right.


#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *left;
    struct node *right;
    
};

void insert(struct node **,int);
void preorder(struct node *);
void postorder(struct node *);
int main(){
    struct node *s;
    s=NULL;
    insert(&s,10);
    insert(&s,5);
    insert(&s,12);
    preorder(s);
    postorder(s);
  
    return 0;
}

void insert(struct node **s,int num){
    if((*s)==0){
        (*s)=(struct node *)malloc(sizeof(struct node));
        (*s)->left=0;
        (*s)->data=num;
        
        (*s)->right=0;
    }
    
    else if(num<((*s)->data)){
        insert(&((*s)->left),num);
    }
    
    else if(num>((*s)->data)){
        insert(&((*s)->right),num);
    }

        
}
 void preorder(struct node *s){
     
     if(s!=NULL){
            printf("%d ",s->data);
            preorder(s->left);
            preorder(s->right);
        }else
        return;
     }

 void postorder(struct node *s){

     

     if(s!=NULL){

          

            postorder(s->left);

            postorder(s->right);

          printf("%d ",s->data);

        }else

        return;

     }

OUTPUT
Executing the program....
$demo

preorder:  10 5 12 

postorder:  12 10 5 

Simple  Program to Reverse a LinkedList

#include <stdio.h>
#include <stdlib.h>

struct node{
    struct node *link;
    int data;
    };
 
    void insert(struct node **,int);
    void display(struct node *);
    int count(struct node *);

    void delete(struct node **,int);
    void append(struct node **,int);
     void reverse(struct node **);
    int main(){
        struct node *s;
        s=NULL;
      
    
        insert(&s,10);
        insert(&s,20);
        insert(&s,40);
        insert(&s,50);

        reverse(&s);
  
        display(s);
      
        return 0;
    }
 
    void insert(struct node **s,int num){
        struct node *temp;
        temp=(struct node*)malloc(sizeof(struct node));
        temp->data=num;
        temp->link=*s;
        *s=temp;
    }
    void display(struct node *s){
 
        while(s!=NULL){
            printf("%d \n",s->data);
            s=s->link;
        }
        printf("\n");
    }

int count(struct node *s){
        int i;
        i=0;
        while(s!=NULL){
          
            s=s->link;
            i++;
        }
        printf("%d",i);
    }

void delete(struct node **s,int num){
    struct node *temp,*old;
    temp=(struct node *)malloc(sizeof(struct node));
       temp->data=num;
      temp->link=*s;
      *s=temp;
      
       free(temp);
       
   }

void append(struct node **s,int num){
    struct node *temp;
    temp=(struct node *)malloc(sizeof(struct node));
    temp->data=num;
    temp->link=NULL;
    *s=temp;
}


void reverse(struct node **s)  {

 struct node *a = NULL;
 struct node *b = NULL;
 struct node *c = NULL;
 a = *s, b = NULL;

 while(a != NULL) {
  c = b, b = a, a = a->link;
  b->link = c;
 }

 *s = b;
}
output:

Simple LinkedList Program(LIFO)

Singly linked list is the most basic linked data structure. In this the elements can be placed anywhere in the heap memory unlike array which uses contiguous locations. Nodes in a linked list are linked together using a next field, which stores the address of the next node in the next field of the previous node i.e. each node of the list refers to its successor and the last node contains the NULL reference. It has a dynamic size, which can be determined only at run time.

Single Linked List

A self referential data structure. A list of elements, with a head and a tail; each element points to another of its own kind.

Double Linked List

A self referential data structure. A list of elements, with a head and a tail; each element points to another of its own kind in front of it, as well as another of its own kind, which happens to be behind it in the sequence.

Circular Linked List

Linked list with no head and tail - elements point to each other in a circular fashion.

Basic operations of a singly-linked list are:

Insert – Inserts a new element at the end of the list.

Delete – Deletes any node from the list.

Find – Finds any node in the list.

Print – Prints the list.

#include <stdio.h>
#include <stdlib.h>

struct node{
    struct node *link;
    int data;
    };
  
    void insert(struct node **,int);
    void display(struct node *);
    int count(struct node *);
  
    int main(){
        struct node *s;
        s=NULL;
        insert(&s,10);
        insert(&s,20);
        insert(&s,40);
        insert(&s,50);

        display(s);
        count(s);
        return 0;
    }
  
    void insert(struct node **s,int num){
        struct node *temp;
        temp=(struct node*)malloc(sizeof(struct node));
        temp->data=num;
        temp->link=*s;
        *s=temp;
    }
    void display(struct node *s){
  
        while(s!=NULL){
            printf("%d \n",s->data);
            s=s->link;
        }
        printf("\n");
    }

int count(struct node *s){
        int i;
        i=0;
        while(s!=NULL){
            
            s=s->link;
            i++;
        }
        printf("%d",i);
    }


output:
Executing the program....
$demo

50 
40 
20 
10 

4

// C implementation of above program. #include <stdio.h> #include <stdlib.h> // A nexted list node struct node {     int data;     struct node *next; };  /* Function to insert a node at the beginning */ void push(struct node ** head_ref, int new_data) {     struct node* new_node = (struct node*) malloc(sizeof(struct node));     new_node->data  = new_data;     new_node->next = (*head_ref);     (*head_ref)  = new_node; } /* Utility function to print a singly linked list */ void printList(struct node *head) {     struct node *temp = head;     while (temp != NULL)     {         printf("%d ", temp->data);         temp = temp->next;     }     printf("\n"); } // Main function that inserts nodes of linked list q into p at alternate // positions. Since head of first list never changes and head of second list // may change, we need single pointer for first list and double pointer for // second list. void merge(struct node *p, struct node **q) {      struct node *p_curr = p, *q_curr = *q;      struct node *p_next, *q_next;      // While therre are avialable positions in p      while (p_curr != NULL && q_curr != NULL)      {          // Save next pointers          p_next = p_curr->next;          q_next = q_curr->next;          // Make q_curr as next of p_curr          q_curr->next = p_next;  // Change next pointer of q_curr          p_curr->next = q_curr;  // Change next pointer of p_curr          // Update current pointers for next iteration          p_curr = p_next;          q_curr = q_next;     }     *q = q_curr; // Update head pointer of second list } // Driver program to test above functions int main() {      struct node *p = NULL, *q = NULL;      push(&p, 3);      push(&p, 2);      push(&p, 1);      printf("First Linked List:\n");      printList(p);      push(&q, 8);      push(&q, 7);      push(&q, 6);      push(&q, 5);      push(&q, 4);      printf("Second Linked List:\n");      printList(q);      merge(p, &q);      printf("Modified First Linked List:\n");      printList(p);      printf("Modified Second Linked List:\n");      printList(q);      getchar();      return 0; }

// C program to delete N nodes after M nodes of a linked list #include <stdio.h> #include <stdlib.h> // A linked list node struct node {     int data;     struct node *next; }; /* Function to insert a node at the beginning */ void push(struct node ** head_ref, int new_data) {     /* allocate node */     struct node* new_node = (struct node*) malloc(sizeof(struct node));     /* put in the data  */     new_node->data  = new_data;     /* link the old list off the new node */     new_node->next = (*head_ref);     /* move the head to point to the new node */     (*head_ref)  = new_node; } /* Function to print linked list */ void printList(struct node *head) {     struct node *temp = head;     while (temp != NULL)     {         printf("%d ", temp->data);         temp = temp->next;     }     printf("\n"); } // Function to skip M nodes and then delete N nodes of the linked list. void skipMdeleteN(struct node  *head, int M, int N) {     struct node *curr = head, *t;     int count;     // The main loop that traverses through the whole list     while (curr)     {         // Skip M nodes         for (count = 1; count<M && curr!= NULL; count++)             curr = curr->next;         // If we reached end of list, then return         if (curr == NULL)             return;         // Start from next node and delete N nodes         t = curr->next;         for (count = 1; count<=N && t!= NULL; count++)         {             struct node *temp = t;             t = t->next;             free(temp);         }         curr->next = t; // Link the previous list with remaining nodes         // Set current pointer for next iteration         curr = t;     } } // Driver program to test above functions int main() {     /* Create following linked list       1->2->3->4->5->6->7->8->9->10 */     struct node* head = NULL;     int M=2, N=3;     push(&head, 10);     push(&head, 9);     push(&head, 8);     push(&head, 7);     push(&head, 6);     push(&head, 5);     push(&head, 4);     push(&head, 3);     push(&head, 2);     push(&head, 1);     printf("M = %d, N = %d \nGiven Linked list is :\n", M, N);     printList(head);     skipMdeleteN(head, M, N);     printf("\nLinked list after deletion is :\n");     printList(head);     return 0; }