CODEWITHSUNDEEP
c++algorithmdata-structureslinked-list
Oleksiy
Oleksiy

Reputation: 39810

Is it possible to delete the last node in a linked list?

For example, there is an exercise that says:

Write a function to delete a node from a linked list, given only that pointer

And this is the solution:

void deleteNode(Node* toDelete) {

    // this function essensially first copies the data from the next pointer
    // and then, deletes the next pointer
    // However, it doesn't work if trying to delete the last element in the list

    Node *temp = toDelete->next;    // create a temp, assign to the one after toDelete
    toDelete->data = temp->data;    // change toDelete's data to the one's after it
    toDelete->next = temp->next;    // change toDelete's next to the one's after it

    delete temp;
    temp = nullptr;
}

How can I alter my solution to be able to delete the last element in the linked list, given only the pointer last node?

Upvotes: 1

Views: 2863

Answers (3)

AndersK
AndersK

Reputation: 36082

In order to handle deletion of a node in a single linked list like that you would need to modify the node before and after.

            +-----+  +----------+  +------+
header----->|     |->| toDelete |->|      |
            +-----+  +----------+  +------+

you would need a pointer to the first element of the list since otherwise it is impossible to do what you want due to the nature of the data structure.

first you find the node before the one you need to delete e.g.

Node* before = header;
for (;before->next != toDelete; before = before->next) {;}

now do before->next = toDelete->next if toDelete is the last node it will be a nullptr otherwise a pointer to the next node

(of course you need to delete what the toDelete points to in both cases)

Upvotes: 2

Steve Jessop
Steve Jessop

Reputation: 279255

No, it's not possible with a singly-linked list.

The reason is that you need to modify the penultimate node (to make its next pointer null). But there is no way of finding that node from the last node.

In general, you cannot remove a node from a singly-linked list given only a pointer to the node.

What you're currently doing is essentially a "cheat", since you aren't really deleting the node pointed to. You're mutating the list and then deleting the successor of the node pointed to. This makes a difference if some other bit of code somewhere is holding a pointer to that successor when you call this function -- their pointer gets invalidated. So you're removing the data element pointed to, but you aren't removing the node pointed to.

Upvotes: 3

Mike Seymour
Mike Seymour

Reputation: 254471

Obviously you can't; the previous node points to a valid node, and there's no way to change that.

What you could do is add a sentinel node to the end of the list. You would never remove that node, and never use it to store data. Then your solution will work for all data nodes. This doesn't require any changes to the node structure, but does require changes to the way you iterate over the list.

Upvotes: 8

Related Questions