Linked Lists Implementation

Discussion in 'C' started by dass, Aug 31, 2007.

  1. dass

    dass New Member

    Joined:
    Aug 31, 2007
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    Linked Lists Implementation ...
    Code:
    #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;
    }
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    We have quite a few Linked List code in the forum.
     
  3. h.senan

    h.senan New Member

    Joined:
    Apr 17, 2009
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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.

    :)
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Which part of the code which you are not able to understand ?
     
  5. h.senan

    h.senan New Member

    Joined:
    Apr 17, 2009
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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 ");}
     
  6. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    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 ​
     
  7. LenoxFinlay

    LenoxFinlay Banned

    Joined:
    Apr 15, 2009
    Messages:
    46
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  8. naimish

    naimish New Member

    Joined:
    Jun 29, 2009
    Messages:
    1,043
    Likes Received:
    18
    Trophy Points:
    0
    Occupation:
    Software Engineer
    Location:
    On Earth
    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 ;)
     
  9. vignesh1988i

    vignesh1988i Banned

    Joined:
    Sep 19, 2009
    Messages:
    72
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    Chennai
    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:):):)
     
  10. skp819

    skp819 New Member

    Joined:
    Dec 8, 2008
    Messages:
    89
    Likes Received:
    3
    Trophy Points:
    0
    keep it up my dear
     
  11. talk2mohdsaif

    talk2mohdsaif New Member

    Joined:
    Mar 8, 2009
    Messages:
    21
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    Hamirpur(hp)
    plz can u explain these cone in more detail...
    like how pointers r implimented....
    plz describe in detail.....
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice