Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Linked Lists Implementation (http://www.go4expert.com/articles/linked-lists-implementation-t6130/)

dass 31Aug2007 17:58

Linked Lists Implementation
 
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 3Sep2007 09:13

Re: Linked Lists Implementation
 
We have quite a few Linked List code in the forum.

h.senan 17Apr2009 07:56

Re: Linked Lists Implementation
 
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 19Apr2009 12:53

Re: Linked Lists Implementation
 
Quote:

Originally Posted by h.senan (Post 45787)
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 19Apr2009 13:17

Re: Linked Lists Implementation
 
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 19Apr2009 13:26

Re: Linked Lists Implementation
 
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 18Jul2009 10:34

Re: Linked Lists Implementation
 
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 18Jul2009 11:06

Re: Linked Lists Implementation
 
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 22Sep2009 11:49

Re: Linked Lists Implementation
 
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 24Sep2009 20:41

Re: Linked Lists Implementation
 
keep it up my dear


All times are GMT +5.5. The time now is 12:32.