Linked Lists Implementation

dass's Avatar author of Linked Lists Implementation
This is an article on Linked Lists Implementation in C.
Rated 5.00 By 4 users
Linked Lists Implementation ...
Code: C
#include<stdio.h>
#include<conio.h>
#include<malloc.h>

void insertafter(struct node ** ,int ,int);
void insertatbeg(struct node ** ,int );
void add(struct node ** ,int);
void search(struct node **,int);
void del(struct node ** ,int);
void count(struct node * );
void display(struct node *);
void auxsearch(struct node ** , int );
void revtraverse(struct node **);

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

void main()
{
    int elmt,choice,pos,num;
    char wish;
    struct node *p;

    p=NULL;
    printf("\t\t\tmenu\n\n");
    printf("1.Add element\n2.Display elements\n3.Count of nodes\n4.Insert at begginning\n5.Insert at middle\n6.Insert at end\n7.Delete the element\n8.Search an element\n9.auxiliary search\n10.reverse list\n");
    do
    {
        printf("\nenter the choice\t");
        scanf("%d",&choice);
       
        switch(choice)
        {
        case 1:
        case 6:
            printf("enter the element \t");
            scanf("%d",&elmt);
            add(&p,elmt);
            break;
        case 2:
            display(p);
            break;
        case 3:
            count(p);
            break;
        case 4:
            printf("\nenter the element to be inserted\t");
            scanf("%d",&num);
            insertatbeg(&p,num);
            break;
        case 5:
            printf("\nenter the position to insert\t");
            scanf("%d",&pos);
            pos--;
            printf("enter the element to insert\t");
            scanf("%d",&num);
            insertafter(&p,pos,num);
            break;
        case 7:
            printf("\nenter the element to be deleted\t");
            scanf("%d",&num);
            del(&p,num);
            break;
        case 8:
            printf("\nenter the element to search\t");
            scanf("%d",&num);
            search(&p,num);
            break;
        case 9:
            printf("\nenter the element to search\t");
            scanf("%d",&num);
            auxsearch(&p,num);
            break;
        case 10:
            printf("\nafter reversing...\n");
            revtraverse(&p);
            display(p);
            break;
        }
        printf("\ndo you want to continue? {y/n} \t");
        wish=getche();
    }while(wish=='y' || wish =='Y');
    getch();
}

void add(struct node **q ,int num)
{
    struct node *temp,*r;
    temp=*q;
    if(*q==NULL)
    {
        temp=(struct node*)malloc(sizeof(struct node));
        temp->data=num;
        temp->link=NULL;
        *q=temp;
    }
    else
    {
        temp=*q;
        while(temp->link!=NULL)
            temp=temp->link;
        r=(struct node*)malloc(sizeof(struct node));
        r->data=num;
        r->link=NULL;
        temp->link=r;
    }
}

void display(struct node *q )
{
    if(q == NULL)
        printf("\nNo elements in the list...");
    else
    {
        printf("\nthe elements in the list are\t");
        while(q!=NULL)
        {
            printf("\n %d",q->data);
            q=q->link;
        }
    }
   
}

void count(struct node *q )
{
    int c=0;
   
    while(q!=NULL)
    {
        q=q->link;
        c++;
    }
    printf("the number of nodes is %d\t",c);
}

void insertafter(struct node**q ,int pos,int num)
{
    struct node *temp,*r;
    int i;
    temp=*q;
    for(i=0;i<pos;i++)
        temp=temp->link;
    if(temp==NULL)
    {
        printf("there are less than %d elements in list\n",pos);
        return;
    }
    r=(struct node*)malloc(sizeof(struct node));
    r->data=num;
    r->link=temp->link;
    temp->link=r;
   
}

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

void del(struct node **q ,int num)
{
    struct node *old,*temp;
    temp=*q;
    while(temp!=NULL)
    {
        if(temp->data == num)
        {
            if(temp==*q)
            {
                *q=temp->link;
                free(temp);
                return;
            }
            else
            {
                old->link=temp->link;
                free(temp);
                return;
            }
        }
        else
        {
            old=temp;
            temp=temp->link;
        }
    }
    printf("\n element not found in list\n");
}

void search(struct node **q,int num)
{
    int flag=0,c=0;
    struct node *temp;
    temp=*q;
   
    while(temp != NULL)
    {
        if(temp->data == num)
            flag=1;
        temp=temp->link;
        c++;
    }
    if(flag)
        printf("\nelement found");
    else
        printf("\nno such element ");
}

void auxsearch(struct node **q , int num)
{
    int flag=0;
    struct node *temp;
    temp=*q;
    while(temp->link != NULL)
    {
        if(temp->link->data == num)
        {
            flag=1;
            printf("\nthe elmt is %d",temp->link->data);
            printf("\nthe prior elmt is %d",temp->data);
            break;
        }
        temp=temp->link;
    }
    if(flag==0)
        printf("\nno such element");
}

void revtraverse(struct node **q)
{
    struct node *r,*temp,*s;
    temp=*q;
    r=NULL;
    while(temp != NULL)
       {
        s=r;
        r=temp;
        temp=temp->link;
        r -> link=s;
       
    }
    *q=r;
}
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
We have quite a few Linked List code in the forum.
h.senan's Avatar, Join Date: Apr 2009
Newbie Member
Hello guys..
first of all.. thanx a lot for the codes.. But would you mind giving me an explination about the above code.
many thanks in advance.

shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by h.senan View Post
Hello guys..
first of all.. thanx a lot for the codes.. But would you mind giving me an explination about the above code.
many thanks in advance.

Which part of the code which you are not able to understand ?
h.senan's Avatar, Join Date: Apr 2009
Newbie Member
Thanks for your reply and Thanks so much in advance for your helping.

1-
Code:
void add(struct node **q ,int num)
{    struct node *temp,*r;    
      temp=*q;    if(*q==NULL)    
    {        temp=(struct node*)malloc(sizeof(struct node));        
             temp->data=num;        
             temp->link=NULL;        
             *q=temp;    
     }    
else
     {       temp=*q;        
              while(temp->link!=NULL)            
              temp=temp->link;        
              r=(struct node*)malloc(sizeof(struct node));        
              r->data=num;        
              r->link=NULL;        
              temp->link=r;    
     }
}
2-
Code:
void insertafter(struct node**q ,int pos,int num)
{    struct node *temp,*r;    
      int i;    
      temp=*q;    
      for(i=0;i<pos;i++)        
      temp=temp->link;    
      if(temp==NULL)    
      {        printf("there are less than %d elements in list\n",pos);        
                return;    
       }    
       r=(struct node*)malloc(sizeof(struct node));     
       r->data=num;    
       r->link=temp->link;    
       temp->link=r;     
       }
3-
Code:
void del(struct node **q ,int num)
{    struct node *old,*temp;    
      temp=*q;    
      while(temp!=NULL)    
      {        
        if(temp->data == num)        
            {            if(temp==*q)            
                 {                *q=temp->link;                
                                    free(temp);                
                                    return;            
                  }            
            else            
                  {                
                          old->link=temp->link;                
                          free(temp);                
                          return;             
                   }        
                }        
            else        
                {            
                          old=temp;            
                          temp=temp->link;        
                 }    
             }    printf("\n element not found in list\n");}
4-
Code:
void search(struct node **q,int num)
{    int flag=0,c=0;    
      struct node *temp;    
      temp=*q;        
      while(temp != NULL)     
      {        if(temp->data == num)            
                flag=1;        
                temp=temp->link;        
                c++;    
       }    
         if(flag)        
         printf("\nelement found");    
         else        
         printf("\nno such element ");}
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
1-
Adds the Node based on the head location.
2-
Searches the node and inserts after a particular node
3-
Searches the data and then deletes it and arranges the pointers.
4-
Searches the particular node by doing a linear travelling
LenoxFinlay's Avatar
Banned
The array implementation of multisets is really only practical if the number of items in the universe, N=|U|, is not too large. If N is large, then it is impractical, or at least extremely inefficient, to use an array of N counters to represent the multiset. This is especially so if the number of elements in the multisets is significantly less than N. If we use a linked list of elements to represent a multiset S, the space required is proportional to the size of the multiset, |S|. When the size of the multiset is significantly less than the size of the universe, tex2html_wrap_inline67534, it is more efficient in terms of both time and space to use a linked list.
naimish's Avatar
Banned
Hey, haven't watched this article, I have also submitted an article on Linked List in C++ just now, please check if it's useful or not, This one is also good. Lets c if I can combine both one and make new simple and easier one
vignesh1988i's Avatar
Banned
your implementation is correct , one small opinion :
As u have declared the structure globally , why are u passing the structure everytime for every function as a argument ..... since ur structure is global , you could have directly access it na.... so readability of your program increases.............

thank u
skp819's Avatar
Contributor
keep it up my dear