Singly-linked list insertion in C (pointer to pointer)

Question

There are two versions of singly linked list insertion function.

One is common version using one pointer and it's easy to understand:

void insert(struct node *newt) {
    struct node *node = head, *prev = NULL;
    while (node != NULL && node->data < newt->data) {
        prev = node;
        node = node->next;
    }
    newt->next = node;
    if (prev == NULL)
        head = newt;
    else
        prev->next = newt;
}

Another one is using pointer to pointer :

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && (*link)->data < newt->data)
        link = &(*link)->next;
    newt->next = *link;
    *link = newt;     //confuse me
}

I am confused about *link = newt; Although I assign newt to *link, the previous node still point to the original address?

Thank you in advance!

M Oehm · Accepted Answer · 2020-03-05 15:11:11Z

2

When inserting a node at the front, you must update the list's head. When inserting after that, you must update the next field of the previous node. Using a pointer to node pointer does that:

At first:

struct node **link = &head;

Now link is a pointer to the head pointer. If you update *link, you update the head through that pointer.

Later:

link = &(*link)->next;

Now link is a pointer to the current node's next field. If you update *link, you update that next field.

In both cases, if you read from *link, you get the current node.

answered Mar 5, 2020 at 15:11

M Oehm

29.2k3 gold badges36 silver badges44 bronze badges

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

Comments

Maxim Egorushkin · Accepted Answer · 2020-03-05 15:09:08Z

1

the previous node still point to the original address?

In *link = newt; it assigns newt to previous node's next member.

link either points to head or to previous node's next member.

answered Mar 5, 2020 at 15:09

Maxim Egorushkin

138k19 gold badges201 silver badges293 bronze badges

Collectives™ on Stack Overflow

Singly-linked list insertion in C (pointer to pointer)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related