Thread: sorting a double linked list using an iterator

Hi i am having problems sorting my linked list using my iterator.Its meant to get an item to add to a linked list and check if its less than any of the items already in the list.

Code:

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


/*
 *
 */






struct node{
    int key;
    struct node *next;
    struct node *previous;


};


struct listset{
    int length;
    struct node *head;
    struct node * tail;
    struct node *iterator;
};
struct listset * listset_new(){
    struct listset *p =(struct listset*) malloc(sizeof(*p));
    p->head=NULL;
    p->tail=NULL;
    p->iterator=NULL;
    p->iterator=NULL;
    return p;


}


//checking if a list is empty
int isEmpty(struct listset *p){


    if(p->head==NULL)
        return 1;


    else
        return 0;
}
/* check has the iterator moved past last item in list;
   always true if list is empty */


int list_at_end(struct listset * p){
    if( (p->iterator==NULL &&  !isEmpty(p) )){
        return 1;
    //printf("at end of list");
    }
    else {
      //  printf(" notat end of list");
        return 0;}


}
/* add new item before current iterator item. if the iterator ia at end of the
   list then add item to end of list */
void list_add_before_current(struct listset * p,char item){




  struct node * temp = (struct node*)malloc(sizeof (*temp));
      //at end of list
    if(list_at_end(p)){


   // if(p->iterator->previous!=NULL&& p->iterator->next==NULL){
        temp->next=NULL;
        p->tail->next=temp;


        temp->key=item;
        temp->previous=p->tail;
        p->tail=temp;




  //  }
    }
    //if only one element in the list
    else if(p->iterator->previous==NULL && p->iterator!=NULL){
        p->head=temp;
        temp->key=item;
        temp->next=p->iterator;
    }


    //anywhere in the list
    else
    {


        temp->key=item;
        p->iterator->previous->next=temp;  //pointing my former previous node next  to my new node
        p->iterator->previous=temp; //iterator previous now points to my new node
        temp->previous=p->iterator->previous; // new node previous  points tom my currents iterator previous
        temp->next=p->iterator; //new node next points to my iterator


    }


}




void listset_add(struct listset * t, char item){
    struct listset *a=t;
    int found=0;
    struct node *temp= (struct node*)malloc(sizeof(*temp));
    if(t->head==NULL)
    {


    a->head=temp;
    a->tail=temp;
    temp->key=item;
    temp->previous=NULL;
    temp->next=NULL;
    a->iterator=temp; //when first element is added .iterator becomes my temp


    }
    else {
        while(a->iterator!=NULL ||found!=1){




            if(item< (a->iterator->key)){
                list_add_before_current(a, item);
            found=1;
            }


            else
                a->iterator=a->iterator->next;


  
        }//iner while


        if(list_at_end(a))
             list_add_before_current(a, item);
    }//else
}


//removing an item from the end of the list
void list_popBack(struct listset *p){
    if(p->tail->previous==NULL)
{
    free(p->tail);
    p->head=NULL;
}
else {
    p->tail->previous->next=NULL;
    free(p->tail);
      }


}

You should find a good debugger tutorial and run your program through a debugger.

Code:

while (a->iterator != NULL || found != 1)

This line is a problem. If a->iterator is NULL, the first half of the OR evaluates to false, meaning it checks the second half. found != 1 is true, so the while loop does another iteration. That means when you get to this line:

Code:

if (item < (a->iterator->key))

The a->iterator is NULL, and a->iterator->key causes your program to crash. You should use && instead of ||.

Originally Posted by anduril462

You should find a good debugger tutorial and run your program through a debugger.

Code:

while (a->iterator != NULL || found != 1)

This line is a problem. If a->iterator is NULL, the first half of the OR evaluates to false, meaning it checks the second half. found != 1 is true, so the while loop does another iteration. That means when you get to this line:

Code:

if (item < (a->iterator->key))

The a->iterator is NULL, and a->iterator->key causes your program to crash. You should use && instead of ||.

i used a || so that if the item is found it can exist the while loop without waiting for the iterator to become null

Originally Posted by sigur47

i used a || so that if the item is found it can exist the while loop without waiting for the iterator to become null

It doesn't do that though.

Code:

while (a->iterator != NULL || found != 1)

Suppose found==1, and a->iterator is not NULL.

It's then:

Code:

while (<notnullvalue> != NULL || 1 != 1)

so

Code:

while (true || false)

Because the iterator is NULL, that part evaluates to true, so the loop continues to execute, which isn't what you wanted.

You really do want &&. You only want to loop if *both* iterator isn't NULL and found isn't 1.