CODEWITHSUNDEEP
c++linked-list
user2948246
user2948246

Reputation: 77

Delete a node in the middle of a singly linked list given only the node. C++

Before I submit my code here I want to know if my idea is correct, as I already the "correct" answer to this problem.

Is it possible to solve this question by finding the position of the given node, and then using the regular 'Delete at a given position' function? So basically the previous node will point to the next node of the given node. i.e, If s is given node, ptr is previous node, then ptr->next = s->next. Is this correct?

Upvotes: 0

Views: 176

Answers (1)

natansun
natansun

Reputation: 231

You're right.

Let's say the Node to delete is delNode.

The solution you suggested has 2 parts:

  1. Search for its index in the list.
  2. then delete the Node at[index].

Time Complexity is O(n) - where n is size of the list. (part 1 worst case is O(n)). There are no problems with this solution. If Node delNode isn't found, no deletion will occur.

A different solution: (With its Pros & Cons).

Assume the Nodes before and after delNode are A and B respectively. A has its A.data and A.next, and delNode has its delNode.data and delNode.next (i.e: delNode.next == B). Deletion of delNode means that after its deletion, A.next == B.

But without using a search we can NOT change A.next because A isn't reacheble from delNode (Singly Linked List).

So instead of searching delNode we can try manipulate the list like this: delNode.data = delNode.next.data (Simplier: delNode = B.data). delNode.next = delNode.next.next (delnode.next = B.next).

These changes keeps delNode Object in Memory, but its State was changed and all the content of B were copy to delNode. So delNode right now is actually B, and the because B.next (==C) was also copied to delNode.next, the next Node after delNode is C.

before: Head--> ... --> A --> delNode --> B --> C --> ...

after: Head--> ... --> A --> delNode(== B state includes B.next == C) --> C --> ...

So the Node who's been deleted is actually B and B only.

A quick summary:

Pros:

  • Time Complexity is O(1).

Cons:

Cases the solution is not applicable:

  • delNode.next == Null.
  • Polymorphic List. For a List with Polymorphic types there's a problem. For example: Car and Bus are both has the same SuperClass Vehicle, and the list contains Vehicle objects. If delNode is a Car, and B is a Bus, the Idea of copy B state to delNode is WRONG! These objects have different concrete types, therefore this solution is not applicable to this case.

Last Thing

C++ implementation - Don't forget to delete(B).

Upvotes: 2

Related Questions