CODEWITHSUNDEEP
algorithmdata-structuressingly-linked-listdoubly-linked-list
Arun
Arun

Reputation: 1

Is it necessary to isolate the node, when deleting from the middle of a Linked List?

Do we just make the previous node point to the next.

prev.next = next;
return current;

or isolate the node

prev.next = next;
current.next = null;
return current;

As are still able to traverse the remaining list, if we have the deleted node, with a next pointer. And how about in a Doubly Linked List?

Upvotes: 0

Views: 130

Answers (2)

Oswald
Oswald

Reputation: 31647

In theory

The most important thing is, that the list invariants stays intact after the deletion. That is

  • there are no circles,
  • each node points to the next node (unless the node is the last one),
  • in a doubly linked list, each node is the successor of its predecessor (unless the node is the first one),
  • in a doubly linked list, each node is the predecessor of its successor (unless the node is the last one),.

The list invariants do not say anything about nodes that do not belong to the list, so it does not really matter whether or not you set current.next = null during the deletion.

In parctice

Leaving current.next as it is might hinder automatic garbage collection, because references to objects might exist, that are no longer needed. But this depends on the exact circumstances.

In languages without automatic garbage collection, the concept of owning another object exists. An object that owns another object is responsible for managing the resources of that other object (e.g. the memory that the other object occupies). When the owning object is deleted, the owning must delete the owned object. In such a case, if you do not set current.next = null before deleting current, other objects are deleted that should not have been deleted.

Upvotes: 1

numberten
numberten

Reputation: 136

There's no real reason to 'isolate' the node. Once you set the previous node's next pointer to the next node, you've 'isolated' the current node in the sense that it can't be found from your list head. Assuming you don't have automatic garbage collection, you'd then need to delete it.

When working with a doubly linked list, you'll need to update current.next's previous pointer as well. Once you've replaced all node pointers that point to your old current node, you're finished splicing it from the list and it will no longer be findable.

In this example we're removing the 'b' node from both singly and doubly linked lists. The arrows in parentheses are the ones that would need to be updated.

   [a] (->) [b] -> [c]    would become    [a] -> [c]

[a] <(->) [b] (<-)> [c]   would become   [a] <-> [c]

Upvotes: 0

Related Questions