CODEWITHSUNDEEP
cpointersdata-structures
Victor
Victor

Reputation: 1

Deleting from a C Linked List (Pointer to pointer)

I found the following code fragment in C language which deletes an element from the list

void
remove_ll(struct link_list **head, int key)
{
        struct link_list **cur;
        for(cur = head; *cur; ) {
                struct link_list *entry = *cur;
                if (entry->key == key) {
                        *cur = entry->next;
                        free(entry);
                } else {
                        cur = &entry->next;
                }
        }
}

I am trying to understand how it works.

This is my idea.

List example:

     0x1f7d018               0x1f7d038              0x1f7d078
+++++++++++++++++++     +++++++++++++++++++     +++++++++++++++++++
|0x2174010:       |     |0x1f7d070:       |     |0x1f7d090:       |
|key = 10         |     |key = 34         |     |key = 90         |
|&next = 0x1f7d038|++++>|&next = 0x1f7d078|++++>|&next = NULL     |
|                 |     |                 |     |                 |
+++++++++++++++++++     +++++++++++++++++++     +++++++++++++++++++

After deleting the value 34

     0x1f7d018               0x1f7d038
+++++++++++++++++++     +++++++++++++++++++
|0x2174010:       |     |0x1f7d090:       |
|key = 10         |     |key = 90         |
|&next = 0x1f7d038|++++>|&next = NULL     |
|                 |     |                 |
+++++++++++++++++++     +++++++++++++++++++

This is correct?

Best regards.

Upvotes: 0

Views: 97

Answers (3)

Akshay Patole
Akshay Patole

Reputation: 474

When you are deleting any node from a linked list then you are actually freeing up the memory allocated by that node.

So in order to maintain your linked list you need to take care that the Node1 which is previous to the Node2 (which is going to be deleted) should point directly to the Node3 which is next to the Node2.

Node1 --> Node2 --> Node 3

Suppose, we are deleting Node2

So the next pointer of Node1 should point to the address of Node3. And remember to free the memory allocated by Node2 for avoiding memory leaks.

In case of doubly linked list, you need to take care next as well as prev pointer. You can try implementing doubly linked list. It will sure help you to understand better. :)

Upvotes: 1

Windeal
Windeal

Reputation: 87

Pay more attention to the value of &next

Upvotes: 0

MiltoxBeyond
MiltoxBeyond

Reputation: 2731

It is more precise like so:

List example:

     0x1f7d018               0x1f7d038              0x1f7d078
+++++++++++++++++++     +++++++++++++++++++     +++++++++++++++++++
|0x2174010:       |     |0x1f7d070:       |     |0x1f7d090:       |
|key = 10         |     |key = 34         |     |key = 90         |
|&next = 0x1f7d038|++++>|&next = 0x1f7d078|++++>|&next = NULL     |
|                 |     |                 |     |                 |
+++++++++++++++++++     +++++++++++++++++++     +++++++++++++++++++

After deleting the value 34

     0x1f7d018                                      0x1f7d078
+++++++++++++++++++                             +++++++++++++++++++
|0x2174010:       |                             |0x1f7d090:       |
|key = 10         |                             |key = 90         |
|&next = 0x1f7d078|++++++++++++++++++++++++++++>|&next = NULL     |
|                 |                             |                 |
+++++++++++++++++++                             +++++++++++++++++++

Upvotes: 1

Related Questions