New Object in C gets initialized to existing object

user_14646358 0
Viewed 71

I'm trying to implement a circular doubly linked list in C. Inserting one element was fine, but when inserting the second element, curr had the same address as prev.

struct ListNode {
    void *item;
    struct ListNode *next;
    struct ListNode *prev;
};

struct List {
    int num_members;
    ListNode head;

    /* function pointers */
    ...
};

int  ListAppend(List* list, void* item){
    ListNode* node = &(list->head);
    ListInsertBefore(list,item,node);
    
    return 0;
}

int  ListInsertBefore(List* list, void* item, ListNode* node){
    ListNode* prev = node->prev;
    ListNode curr;
    curr.item = item;
    
    node->prev = &curr;
    curr.next = node;
    prev->next = &curr;
    curr.prev = prev;

    list->num_members += 1;

    return 0;
}

Output of GDB：

62      curr.item = item;
7: node = (ListNode *) 0xbfffef08
8: *node = {item = 0x0, next = 0xbfffee70, prev = 0xbfffee70}
9: &curr = (ListNode *) 0xbfffee70
10: curr = {item = 0x0, next = 0xbfffef08, prev = 0xbfffef08}
11: prev = (ListNode *) 0xbfffee70
12: *prev = {item = 0x0, next = 0xbfffef08, prev = 0xbfffef08}
doubly-linked-list memory c
2 Answers

Generally when you add to a linked list like this, there's two cases to handle. The first is when the list is empty. Here the procedure is something like:

  • Allocate a new Node
  • Make the Node point to the payload Item
  • Because it's a doubly linked, circular list:
    • The Node's prev and next point to itself (as the only node)
  • Make the List point to the new Node
  • Increment the list-size counter

When the list is not empty, now the code needs to interleave the new node into the head of the list. Additionally the current head & tail nodes need to point to the new node too.

  • Allocate a new Node
  • Make the Node point to the payload Item
  • Because it's a doubly linked, circular list:
    • The new Node's next points to the List's head
    • The new Node's prev points to the List's tail (list->head->prev)
    • The List's head node (list->head) prev points to the new node
    • The List's tail node (list->head->prev) next points to the new node
    • The List's head points to the new node
  • Increment the list-size counter

It will really really help if you draw this out on paper for each step. Draw arrows for your pointers.

To help you debug this, when you create a new List and ListNode set all the pointers to NULL, and use the assert() function to check pointers you're assuming to be non-null are in-fact what you think they are.

user_17308950

ListNode curr in ListInsertBefore is a local variable that will get destroyed at the end of the function scope. Taking, storing and dereferencing its address outside the function scope make the program have undefined behavior. You need to allocate memory dynamically with malloc, example:

ListNode *ListInsertBefore(List *list, void* item, ListNode *node) {
    ListNode* curr = malloc(sizeof *curr); // allocate memory dynamically
    if(curr) {
        *curr = (ListNode) {item, node, node->prev};

        node->prev->next = curr;
        node->prev = curr;

        list->num_members++;
    }
    return curr;
}

Note: I made it return a pointer to the newly created ListNode instead of always returning 0. You can now use that return value to check if insertion actually succeeded.

Also note: Memory allocated dynamically also needs to be released using free:

List *ListCreate() {
    List *list = malloc(sizeof *list);
    if(list) *list = (List) {0, {NULL, &list->head, &list->head}};
    return list;
}

void ListFree(List *list) {
    for(ListNode *next, *curr = list->head.next; curr != &list->head; curr = next) {
        next = curr->next;
        free(curr);
    }
    free(list);
}

Demo

user_75822470
Related