CODEWITHSUNDEEP
clinked-listcircular-list
Jo Jay
Jo Jay

Reputation: 121

Circular linked list only has one element after inserting two

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);
}

Upvotes: 1

Views: 212

Answers (1)

jxh
jxh

Reputation: 70392

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:

enter image description here Insert v after a.

enter image description here Set v->next and v->prev.

enter image description here 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);
}

Upvotes: 7

Related Questions