circular linked list

shogun1234 · 07-31-2007, 04:15 AM

I try to write a simple circular linked list programme for the purpose of practising C programming.

I create two structures. The first struct contain a struct of itself and a second struct. The seconds struct contain some information required during programme running.

Code:

struct c_list{
   int id;
   struct time_stamp *stamp;
   struct c_list next;
};
struct time_stamp{
 ...
};

The problem I encounter is if I want to print the value stored in the stamp struct it would cause segment fault.

The way how I create nodes is to append the new node to the last node. the code snippet is as below:

Code:

        struct c_list *node; // the last object in the list
        struct c_list *tmp;

        length++;
        node = malloc(sizeof(struct c_list));
        node->id = size();

        node->stamp = data; // data is the struct of time_stamp
        node->next = head;

        if(head->next == head){
                /* init state */
                head->next = node;
        }else{
                /* has siblings */
                tmp = head->next;
                while(tmp->next != head){
                        tmp = tmp->next;
                }
                tmp->next = node;
        }

The way how I print the list is

Code:

void
print_list(struct c_list *head)
{
        struct c_list *node;
        struct time_stamp *t;
        node = head;
        while(node){//not the last one
                printf("node id: %d\n", node->id);
/* BEG
                t = node->stamp;
                printf("offset_from_master_seconds: %d\n", (t->offset_from_master).seconds);
                printf("offset_from_master_nanoseconds: %d\n", (t->offset_from_master).nanoseconds);
                printf("observed_drift: %d\n", t->observed_drift);
                printf("sys_clock_seconds: %d\n", (t->current_sys_clock).seconds);
                printf("sys_clock_nanoseconds: %d\n", (t->current_sys_clock).nanoseconds);
END */
                node = node->next;
                if(node == head) break;
        }
}

The print_list can run and print the id correctly if the code between BEG and END are marked. Otherwise, it cause segment fault.

After using gdb, it says "Cannot access memory at address 0x0." I can't figure out why the inner variable time_stamp would be at the address 0x0. Would any please tell me where did I do it wrong?

I appreciate any advice,

Thank you very much.

bigearsbilly · 07-31-2007, 05:32 AM

well, for safety you should always check a structure pointer before dereferencing it,
like

Code:

   if (thing && thing->next)
      x = thing->next;

if you compile with CFLAGS = -g
then when you get a core, do:
gdb progname core
type where and it will show where it blew up

dmail · 07-31-2007, 08:12 AM

I am all for programmers learning data structures, many learners of C++ are lazy and use the template library without any real idea how to implement them.

Your implementation has a floor which I think I should bring to your attention. To insert a new node in list requires you traverse the whole data structure which is a O(n) operation (where n equals the numbers of current element in the structure). I would recommend that you include a new node called tail which points the last element in the list, so the following code:

Code:

        struct c_list *node; // the last object in the list
        struct c_list *tmp;

        length++;
        node = malloc(sizeof(struct c_list));
        node->id = size();

        node->stamp = data; // data is the struct of time_stamp
        node->next = head;

        if(head->next == head){
                /* init state */
                head->next = node;
        }else{/* the following is what we want to avoid */
                /* has siblings */
                tmp = head->next;
                while(tmp->next != head){
                        tmp = tmp->next;
                }
                tmp->next = node;
        }

would become something like the following.

Code:

        struct c_list *node; /* the new node */
        /*struct c_list *tail; declared elsewhere */
        
        length++;
        node = malloc(sizeof(struct c_list));
        assert(node);
        node->id = size();
        node->stamp = data; // data is the struct of time_stamp
        node->next = head;

        tail->next = node;/*current last node's next will become the new node */
        tail = node;/*set tail to point to the new node */

pros : insertion is constant time
cons : carry another pointer around. NOTE: If you use tail and tail's next points to the start then you do not carry an extra pointer as tail next is always the head.