Double linked list; newbie attempt

Question

I've just started out learning C, and (seemingly) so far most stuff is clicking. However, I'm having some trouble tracking down an issue with an attempt at a double linked list. I keep getting a seg-fault when I attempt to build/run this code. I'm compiling with the Cygwin supplied gcc via NetBeans.

I hate to just dump a block of code and say "help", but I don't know what other details are pertinent at this time, so feel free to ask for details if necessary:

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

struct node_t{
    struct node_t *prev;
    struct node_t *next;
};

struct list_t{
    struct node_t *head;
    struct node_t *tail;
    int length;
};

struct node_t *new_node(void);
struct list_t *new_list(void);
int append_list_node(struct list_t *list, struct node_t *node);

int main(void) {

    int i = 0, length = 0;
    struct node_t *node;
    struct list_t *list = new_list();

    for(i = 0; i < 10; i++){
        length = append_list_node(list, new_node());
        printf("%d", length);
    }

    return 0;

}

struct node_t *new_node(void){
    struct node_t *node = malloc(sizeof(struct node_t));
    return node;
}

struct list_t *new_list(void){
    struct list_t *list = malloc(sizeof(struct list_t));
    list->length = 0;
    return list;
}

int append_list_node(struct list_t *list, struct node_t *new_node){
    if(list->head == NULL){
        list->head          = new_node; // edited
        new_node->prev      = NULL;
    }else{
        list->tail->next    = new_node;
        new_node->prev      = list->tail;
    }
    return (++list->length);
}

Thanks for the super quick responses everyone, all the answers are correct. As I was briefly looking over the code between F5-ing, I realized I wasn't setting the tail, so I resolved to change the line marked edited as follows:

list->head = list->tail = new_node;

I'll also resolve to use calloc() however, I've read that frequent use of it can cause considerable costs to execution time since it's clearing and allocating. Thoughts?

Can you run it with GDB and say where the segmentation fault occurs? — Maz, May 05 '11 at 16:12
list->tail->next = new_node; list->tail is uninitialized when this line is executed for the first time — yurib, May 05 '11 at 16:14
**@Maz**: Apparently at the line I've made mention of in my edit. **@yurib**: Thanks, check my edit, hopefully it's a reasonable solution. — Dan Lugg, May 05 '11 at 16:20

score 2 · Answer 1 · answered May 05 '11 at 16:11

2

C doesn't do any initialization for you. So when you do:

struct list_t *new_list(void){
    struct list_t *list = malloc(sizeof(struct list_t));
    list->length = 0;
    return list;
}

list->head can be anything.. and probably won't be NULL.

answered May 05 '11 at 16:11

Claudiu

224,032
165
485
680

Thanks **Claudiu**; I'm updating my code now with explicit initialization. – Dan Lugg May 05 '11 at 16:23

score 2 · Accepted Answer · answered May 05 '11 at 16:13

2

Use calloc() to allocate memory. The malloc() function does not initialize the memory to zeros (so the pointers will be set to NULL). You are making the assumption that the pointers are NULL by default.

answered May 05 '11 at 16:13

Maz

3,375
1
22
27

Thanks **Maz**; In my book *C Programming: A Modern Approach 2nd Ed.* it mentions that `calloc` can be costly for execution time. Is there a benchmark for this? Would a large number of calls in tandem be noticeable? – Dan Lugg May 05 '11 at 16:22
I'm not aware of any performance slow down resulting from calloc(). If you'd prefer though, you could just use malloc() and then use the memset() function to zero it out yourself. – Maz May 05 '11 at 16:23
1

There are some comments to [my answer](http://stackoverflow.com/questions/1538420/c-difference-between-malloc-and-calloc/1538427#1538427) to a question about `calloc` that discuss performance. You might be interested in reading them. – Fred Larson May 05 '11 at 16:27
Alrighty; I'm only curious as it would make sense, that the extra step to zero out the memory would add to execution time. Surely unnoticeable in most circumstances, however if calling something with exceedingly deep recursion or high iterations, the performance loss may not be so negligible. Not sure myself, gonna hafta investigate. – Dan Lugg May 05 '11 at 16:28
@TomcatExodus: in this case you're setting the memory to 0 anyway (setting length to 0 and pointers to NULL). it's faster to do it with the allocation call all at once than to set each member to 0 individually. so you don't lose performance in this case – Claudiu May 05 '11 at 17:00

score 0 · Answer 3 · answered May 05 '11 at 16:15

0

One issue is that you never set list->tail to anything, and then attempt to access list->tail->next if list->head isn't NULL (which, as other have pointed out, isn't guaranteed anyway.)

answered May 05 '11 at 16:15

dlev

48,024
5
125
132

Thanks **dlev**; I noticed that half a second after my post. *Whoops!* :) – Dan Lugg May 05 '11 at 16:24

Double linked list; newbie attempt

3 Answers3