CODEWITHSUNDEEP
clinked-list
張皓翔
張皓翔

Reputation: 361

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

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!

Upvotes: 0

Views: 59

Answers (2)

M Oehm
M Oehm

Reputation: 29116

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.

Upvotes: 2

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136208

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.

Upvotes: 1

Related Questions