Logical error for linked list in C

Question

#include <stdio.h>
#include <stdlib.h>
#define UINT unsigned int

struct item
{
UINT   time ;           // time in tics which is used to order the list.
UINT   id ;             // penguin id number.
UINT   event ;          // event this item describes.
struct item  *next ;    // pointer to next item in list.
};

struct item *head=NULL;
struct item *trail=NULL;


void link_list(UINT time, UINT id, UINT event)
{
struct item *t=NULL;
static int i=0;
if(i==0)
{
    head->time=time;
    head->id=id;
    head->event=event;
    trail=head;
    trail->next=NULL;
    i++;
    printf("Hello Word\n");
}
t=malloc(sizeof(struct item));
trail->next=t;
trail->time=time;
trail->id=id;
trail->event=event;
trail=t;
trail->next=NULL;
if(i!=0)
    printf("I am \n");

}

int main(int argc, char *argv[])
{
UINT x[3]={4,5,7}, y[3]={40,50,60}, z[3]={100,900,500};
int i=0;
head=malloc(sizeof(struct item));

trail=head;
link_list(x[0], y[0], z[0]);
link_list(x[1], y[1], z[1]);
link_list(x[2], y[2], z[2]);


struct item *f=NULL;
f=head;
do
{
    printf("trail: %d %d %d\n", f->time, f->id, f->event);
    f=f->next;
}
while(f!=NULL);

return 0;
}  

Good day,

I'm currently having a logical problem with my code implementation of my linked list logically. This code is the framework I am using to integrate it into a larger program which will use linked list so I need to get this right.

Basically what is happening is when I finally reach the do while loop which I use as a debugging line to see the contents of a linked list I will get this output on my command line:

trail: 4 40 100

trail: 5 50 900

trail: 7 60 500

trail: 0 0 0

I am expecting the output to be like this:

trail: 4 40 100

trail: 5 50 900

trail: 7 60 500

I have excluded the other printf's in my code as they are just used to check if I am indeed going through my functions properly. Also this might be unrelated but is there a better debugger for c under linux? Because the built in debugger goes crazy when it steps into a malloc command so I have to debug all programs inside my head. :(

Answer 1

You're appending a new node to the tail, then writing in your datum to the tail node, then moving the tail pointer to the new node:

t=malloc(sizeof(struct item));
trail->next=t;
trail->time=time;
trail->id=id;
trail->event=event;
trail=t;
trail->next=NULL;

t is set to a new node. the next pointer of the current list tail is set to point to t the time, id, and event fields of the node pointed by tail are written. tail reference is now moved to t, which still contains no data.

There are a plethora of things that can improve this code, starting with using modular design for a "list" management, but this is your immediate problem.

Answer 2

If by built-in debugger you mean gdb, you can tell it to step over malloc(); if your program crashes in malloc, though, you have run into a memory allocation or use bug in your program.

One apparent bug is that you do not initialize "t" correctly in link_list(), and in particular t->next is garbage, and your program will probably crash when it tries to follow it. I think you mean to set t->time, t->id etc., not trail->time.

The best way to append to a linked list is usually to have a separate function that returns a new list item with all the fields initialized, and then in the routine to append, just manipulate pointers. It also helps if your list head is just a pointer, not a struct, but that's a style issue.

Best of all is to use a library that supplies linked lists for you, but that's no good if you are learning about linked lists!