Is this doubly linked list function implemented correctly?

Question

I was watching a youtube video on doubly linked lists in C. One of the functions made for the doubly linked list was an "insert_after_node" function, which as the name suggests inserts a new node after an existing one.

For context node_t is a typedef for this struct:

struct node {
    int value;
    struct node* next;
    struct node* prev;
};

Here is the function:

void insert_after_node(node_t *node_to_insert_after, node_t* newnode) {
    newnode->next = node_to_insert_after->next;
    if (newnode->next != NULL) {
        newnode->next->prev = node_to_insert_after;
    }
    newnode->prev = node_to_insert_after;
    node_to_insert_after->next = newnode;
}

Logically Im thinking that the newnode->next->prev = node_to_insert_after; line of the function is incorrect and should instead be newnode->next->prev = newnode;. I mean isnt the previous node of the new nodes next node just the new node? No one seems to have commented on this which makes me think I might be wrong.

Am I wrong and if so why is the initial function correct?

The next node's previous node should always be the original node. — JMP
– JMP, Commented May 11 at 16:51
The code is wrong and your correction is right. Draw it out on paper. — Mark Tolonen
– Mark Tolonen, Commented May 11 at 16:55
First of all, this is not a valid C code! Unbalanced braces make the code invalid, not-compilable, so its semantics does not even exist yet. — CiaPan
– CiaPan, Commented May 12 at 7:32

Steven Low · Accepted Answer · 2025-05-11 17:26:31Z

2

newnode -> next -> prev = newnode

is good

answered May 11 at 17:26

Steven Low

561 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Craig Estey May 11 at 21:50

Side note: The arrow operator -> is tightly bound. Idiomatic style is to not have spaces around it. So, (always) do newnode->next->prev = newnode

Gallagator · Accepted Answer · 2025-05-11 17:03:29Z

1

Yes, you're right. It should be: newnode->next->prev = newnode; instead of newnode->next->prev = node_to_insert_after;

Aside from this, I'm not sure whether this is a typo but where you should have a }, you have {. For example, your struct definition should be:

struct node {
    int value;
    struct node* next;
    struct node* prev;
};

What I must ask is: why are you asking this question? Why not write some tests for yourself to see if things work rather than asking on stack overflow? For example, you could write a function which prints the list:

void print_list(struct node *head) {
    for(struct node *cur = head; cur != NULL; cur = cur->next) {
        printf("%d ", cur->value);
    }
    printf("\n");
}

Then you could use your insert functions and print the list to see if it works.

answered May 11 at 17:03

Gallagator

214 bronze badges

2 Comments

Samo May 11 at 17:28

Thanks for the answer. Yes you are correct I made some typos and the reason I didn't test it is because I couldnt figure out how to test each previous pointer. I am very new to C let alone data structures so thank you for answering.

Mark Tolonen May 11 at 19:09

This wouldn't test it because the error was setting the previous node. But make a function that walks the list forward, then backward and the error would be discovered.

trincot · Accepted Answer · 2025-05-14 19:08:11Z

You are correct, and that correction should be applied to the code you quoted.

I want to also point out another aspect that might be useful: this function will bring inconsistency when you pass it a node as second argument that is already part of a linked list (whether it be the same or a different one).

The name newnode suggests that it is assumed that this node is not currently linked with any other node, but why not have it work also in that case?

And once we support that, we might take another step and allow node_to_insert_after to be NULL. That would mean you would only detach the node from the linked list it is currently in, and just set its prev and next members to NULL, in order to isolate that detached node.

This way you have a single function that supports insertion of a new node into a linked list, removal of a node out of a linked list, and the combination of both, which results in moving a node from one (linked list) location to another.

This means the code must first properly detach the given node from the linked list it might be in before inserting it where it should end up:

void insert_after_node(node_t *node_to_insert_after, node_t *node) {
    // Detach node from its current context, if any
    if (node->next) {
        node->next->prev = node->prev;
    }
    if (node->prev) {
        node->prev->next = node->next;
    }
    // Update its own outgoing links
    node->next = node_to_insert_after ? node_to_insert_after->next : NULL;
    node->prev = node_to_insert_after;
    // Mirror those updated links to complete the insertion
    if (node->next) {
        node->next->prev = node;
    }
    if (node->prev) {
        node->prev->next = node;
    }
}

It is assumed that whatever node you pass as second argument, it has determined values for its prev and next members (i.e. they were not left uninitialised).

Collectives™ on Stack Overflow

Is this doubly linked list function implemented correctly?

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related