Insert Function for an ordered linked list 
Author Message
 Insert Function for an ordered linked list

Once again I have found myself in a tangle and would appreciate
any comments/pointers on the function below (which compiles but
returns with a segmentation fault).

The insert function should insert the next item entered by the
user into the ordered list.

typedef struct intList* link_t;
struct intList
{
   int item;
   link_t next;

Quote:
};

typedef struct intList IntList;

int ListInsert(IntList * head, int anInt)
{
   link_t tmp, scanp1, scanp2;

   tmp = malloc(sizeof(IntList));
   if(tmp == NULL)
   {
      fprintf(stderr, "\nmalloc() failed\n");
      return FAILURE;
   }

   tmp->item = anInt;

   scanp1 = head;

   while((scanp1 != NULL) && (scanp1->item < anInt))
   {
      scanp2 = scanp1;
      scanp1 = scanp1->next;
   }

   if(scanp1 == head->next)
   {
      tmp->next = head->next;
      head->next = tmp;
   }

   else if(scanp1 == NULL)
   {
      tmp->next = NULL;
      scanp1->next = tmp;
   }

   else
   {
      tmp->next = scanp2->next;
      scanp2->next = tmp;
   }

   return SUCCESS;

Quote:
}

With thanks,

Christina



Sat, 14 Jul 2001 03:00:00 GMT  
 Insert Function for an ordered linked list
Error :

   else if(scanp1 == NULL)
   {
      tmp->next = NULL;
      scanp1->next = tmp;   /* scanp1 == NULL, ie ERROR*/
   }

Correction :

   else if(scanp1 == NULL)
   {
      tmp->next = NULL;
      scanp2->next = tmp;   /* you commited a typo error here */
   }

Chye :)



Sat, 14 Jul 2001 03:00:00 GMT  
 Insert Function for an ordered linked list

Quote:

>The insert function should insert the next item entered by the
>user into the ordered list.

You don't show how you start. If head is NULL (empty list), then the body of
the while loop will never be executed, and when doing
if(scanp1 == head->next)
your are dereferencing a NULL pointer.

You can't change head inside the routine as head is called by value. The
simplest solution is to start with a list with one element. If you know all
entries are non-negative, initialize the first item to -1. In that case you
can simplify your program to just

   while((scanp1 != NULL) && (scanp1->item < anInt))
   {
      scanp2 = scanp1;
      scanp1 = scanp1->next;
   }

   {
      tmp->next = scanp2->next;
      scanp2->next = tmp;
   }

If such an element (-1) is not possible, you could still have such a dummy
element in your list. You would have to modify the setup before doing the
while loop.

Suggestion. Write a print_list routine to print out the entire list after
each insertion.

Carsten Hansen



Sat, 14 Jul 2001 03:00:00 GMT  
 Insert Function for an ordered linked list
apart from the typo causing a NULL pointer dereference, I think you also
need to correct code handling instertion to the head of the list.

Quote:
> typedef struct intList* link_t;
> struct intList
> {
>    int item;
>    link_t next;
> };

> typedef struct intList IntList;

> int ListInsert(IntList * head, int anInt)
> {
>    link_t tmp, scanp1, scanp2;

>    tmp = malloc(sizeof(IntList));
>    if(tmp == NULL)
>    {
>       fprintf(stderr, "\nmalloc() failed\n");
>       return FAILURE;
>    }

>    tmp->item = anInt;

>    scanp1 = head;

>    while((scanp1 != NULL) && (scanp1->item < anInt))
>    {
>       scanp2 = scanp1;
>       scanp1 = scanp1->next;
>    }

are you using head as an IntList where the next pointer points to the real
list head and the item field is unused ? If this is the case that scanp1
should be initialised to head->next rather than head.

If you are not using head this was and it is actually the first IntList in
the list, then how do you pass back the the caller a new list head pointer
after insertion to the head of the list ?

Quote:
>    if(scanp1 == head->next)
>    {
>       tmp->next = head->next;
>       head->next = tmp;
>    }

>    else if(scanp1 == NULL)
>    {
>       tmp->next = NULL;
>       scanp1->next = tmp;
>    }

chnage to
   else if(scanp1 == NULL)
   {
      tmp->next = NULL;
      scanp2->next = tmp;
   }

Quote:

>    else
>    {
>       tmp->next = scanp2->next;
>       scanp2->next = tmp;
>    }

I think this last else should be changed to
   else
   {
       tmp->next = scanp1->next;
       scanp2->next = tmp;
   }

I hope these comments make sense
Rob.



Sat, 14 Jul 2001 03:00:00 GMT  
 Insert Function for an ordered linked list
: Once again I have found myself in a tangle and would appreciate
: any comments/pointers on the function below (which compiles but
: returns with a segmentation fault).

It depends on what you're actually feeding the function, but you're
passing it a 'pointer to record' as the head of the list, which means
you can't update the first element in the list.  This may be part of
your problem; you also dereference the NULL pointer scanp1 at one
point, which isn't especially cool.   I've stuck a revised version of
the code at the end of this post - note that I _haven't_ compiled it,
so treat it with caution, and note the different calling convention.

: The insert function should insert the next item entered by the
: user into the ordered list.

: typedef struct intList* link_t;
: struct intList
: {
:    int item;
:    link_t next;
: };
: typedef struct intList IntList;

: int ListInsert(IntList * head, int anInt)
: {
:    link_t tmp, scanp1, scanp2;

:    tmp = malloc(sizeof(IntList));
:    if(tmp == NULL)
:    {
:       fprintf(stderr, "\nmalloc() failed\n");
:       return FAILURE;
:    }
:    tmp->item = anInt;
:    scanp1 = head;
:    while((scanp1 != NULL) && (scanp1->item < anInt))
:    {
:       scanp2 = scanp1;
:       scanp1 = scanp1->next;
:    }
:    if(scanp1 == head->next)
:    {
:       tmp->next = head->next;
:       head->next = tmp;
:    }
:    else if(scanp1 == NULL)
:    {
:       tmp->next = NULL;
:       scanp1->next = tmp;
:    }
:    else
:    {
:       tmp->next = scanp2->next;
:       scanp2->next = tmp;
:    }
:    return SUCCESS;
: }

int ListInsert(IntList **phead, int anInt)
{
  link_t tmp, prev, this;

  if ((tmp = malloc(sizeof(IntList)) == NULL) {
        fprintf(stderr, "malloc() failed\n");
        return FAILURE;
  }
  tmp->item = anInt;

  for (prev = this = *phead ; this && this->item < anInt ; this = this->next)
        prev = this;

  if (prev == this) {           /* insert at start of list */
        *phead = tmp;
        tmp->next = prev;
  }
  else {                        /* insert in middle or at end of list */
        prev->next = tmp;
        tmp->next = this;
  }

  return SUCCESS;

Quote:
}

Will



Sat, 14 Jul 2001 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Problem with ordered insert into linear list -part 2-

2. link list of a linked list (chained links?)

3. Problem of insert and sort of Linked list

4. Insert in a linked list

5. Ordered list and function pointers

6. Load order and DLL entry order of implicitly linked DLLs, Environment variables

7. sorted list of emails -- Insert function

8. Incompatible NULL Assignments || Linked List inside Linked List

9. Clearing Memory || Linked List INSIDE of a Linked List

10. Freeing a Linked List inside of a Linked List

11. Linked List of Linked Lists

12. Define a linked list of a linked list

 

 
Powered by phpBB® Forum Software