Circular linked list only has one element after inserting two

Question

I am attempting to implement a circular linked list, but it is not working as I expected. Even though I insert two elements with insertAfter, printList only prints one node. Here is a minimal example:

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

struct dnode_elm {
    int item;
    struct dnode_elm *next, *prev;
};

struct dnode_elm *
insertAfter(struct dnode_elm *a, int value) {
    struct dnode_elm *v= malloc(sizeof(struct dnode_elm));
    v->item=value;
    a->next=v;
    v->prev=a;
    v->next=a->next;
    a->next->prev=v;
    return v;
}

void
printList(struct dnode_elm *h) {
    while (h != h->next) {
        h = h->next;
        printf("%d --> ",h->item);
    }
}

int
main(void) {
    struct dnode_elm h = { INT_MAX, &h, &h };
    insertAfter(&h, 1);
    insertAfter(&h, 2);
    printList(&h);
}

[**Do not cast the return value of malloc**. You're missing ``.](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — Antti Haapala -- Слава Україні, May 14 '16 at 07:45
Also, compile with **warnings enabled and them set to errors.** `gcc -Wall -Werror` for example. — Antti Haapala -- Слава Україні, May 14 '16 at 07:45
Also please make a minimal example, adding the actual function calls that demonstrate the problem, now we just need to understand Korean and guess whatever it was that you'd type in to reproduce the problem. — Antti Haapala -- Слава Україні, May 14 '16 at 07:47
@AnttiHaapalaI added but still not working... only dummy node is printed out — Jo Jay, May 14 '16 at 07:50
@AnttiHaapala's advice is to help you correct problems outside of your immediate question. They are valid concerns. In C, `void *` will implicitly convert to whatever pointer type matches the destination variable, so casting it is not necessary. — jxh, May 14 '16 at 07:55
Furthermore, if you do not have `#include `, `malloc` can break on many platforms, because it is assumed to implicitly return an `int` instead of a pointer. And it might seem to work, but break when the pointer does not fit in an int. — Antti Haapala -- Слава Україні, May 14 '16 at 07:57

jxh · Answer 1 · 2018-12-22T18:22:17.877

7

Your insertion logic is wrong.

a->next=v;
v->prev=a;
v->next=a->next;
a->next->prev=v;

After this sequence of code, v->next is equal to v, which is probably not what you want.

One possible fix is to assign v's pointers first, and then fix up the nodes around v afterwards.

v->prev = a;
v->next = a->next;
v->next->prev = v;
v->prev->next = v;

To illustrate:

Insert v after a.

Set v->next and v->prev.

Set v->next->prev and v->prev->next.

However you could have rearranged the assignments in your code as well, by moving the first assignment to be your last.

v->prev=a;
v->next=a->next;
a->next->prev=v;
a->next=v;

This allows the assignment to a->next->prev to work as you expect.

In addition, your printing logic is flawed. You need to remember what the initial list pointer is so you can properly detect when you have reached the end.

void *start = h;
while (start != h->next) {
    h = h->next;
    printf("%d --> ",h->item);
}

edited Dec 22 '18 at 18:22

answered May 14 '16 at 07:49

jxh

69,070
8
110
193

@jxhwhy v->next->prev = v; v->prev->next = v; – Jo Jay May 14 '16 at 07:59
@JoJay to set the next and previous nodes to point to `v`. (one could have used `a` for `v->prev` there but written this way it is more obvious). – Antti Haapala -- Слава Україні May 14 '16 at 08:06
@jxhI set variables to void double pointer and it seems to be worked. but while loop run infinately – Jo Jay May 14 '16 at 08:55
like 2147483647 --> 90 --> 2147483647 --> 90 --> 2147483647 --> 90 --> 2147483647....... – Jo Jay May 14 '16 at 08:56
@JoJay: Fix `printList`. – jxh May 14 '16 at 09:25
@JoJay: Assuming you are printing a non-empty list, your print function loops while the list is not empty. – jxh May 14 '16 at 10:40
yes i know. that's why I coded while(h->next!=h). it means not empty – Jo Jay May 14 '16 at 10:50
@JoJay: So, as you are printing it out, when do you expect it to become empty? – jxh May 14 '16 at 12:22

Circular linked list only has one element after inserting two

1 Answers1