CODEWITHSUNDEEP
c#
Harris Calvin
Harris Calvin

Reputation: 473

iterating through linked list to remove nodes

I know how to iterate through a single linked list's nodes using a while loop but how can I remove certain nodes if their value matches int value I am a little stuck and even feel hyperventilated with all this deep thinking but I just can't seem to get my head wrapped around this.

class Node
{
public int value ;
public Node next ;
}

this is the while loop which should iterate through the nodes and it stops after it finds the first undesired value. This linked list can have more than node whose value is undesired so I am confused on what additional code I must write to implement the removal of nodes with the undesired value.

while ((currentNode != null) && (currentNode.Value != UndesiredValue))
   currentNode = currentNode.next;

Example output:

if linked list has integers

5, 7, 8 ,9 3, 5, 5, 2

and undesired value is 5 then the list becomes 7, 8, 9, 3, 2 since the nodes with 5 would have been removed.

Upvotes: 1

Views: 5764

Answers (2)

Rune FS
Rune FS

Reputation: 21742

You should look at the situations you can end in. There's two major scenarios for removal

  • Remove the first element
  • Remove any other element

Your implementation need to handle both. It's straight forward to handle the first one. You simply iterate pass the leading elements with the given value

var currentNode = head; //head points to the first element of type `Node`
while(currentNode != null && currentNode.Value == undesiredValue) {
     currentNode = currentNode.Next; 
}
head = currentNode;

After that you'd need to find the elements with the undesired value and exclude them from the list

//at this point the head should not be removed
while(currentNode != null && currentNode.Next != null){
   //skip all elements with the undesired value
   var next = currentNode.Next;
   while(next != null && next.Value == undesiredValue){
       next = next.Next;
   }
   currentNode.Next = next;
}

The inner loop does exactly the same as the previous simple loop did and you could condense the code somewhat however this code shows the approach you should take when tackling a design problem. Analyse which different scenarios you might have solve each of the scenarios and you might then be able to solve several scenarios at the same time (E.g. there's a third scenario of removing the last element however that's solved together with the second of the scenarios above)

Upvotes: 0

Heinzi
Heinzi

Reputation: 172280

Hint: This is (part of) your list before removal:

+----------------+
| previous Node  |
+----------------+
| some value     |        +----------------+
|     Next ------------>  | currentNode    |
+----------------+        +----------------+
                          | UndesiredValue |       +-----------+
                          |    Next  ------------> | next Node |
                          +----------------+       +-----------+

This is (part of) your list after removal:

+----------------+
| previous Node  |
+----------------+
| some value     |                                 +----------------+
|     Next ------------------------------------->  | next Node      |
+----------------+                                 +----------------+

As you can see, changing the Next reference of the previous node should be enough.

(Since this is obviously a homework or training problem -- I cannot see another reason for re-implementing a linked list in C# -- this should be enough to get you on the right track.)

Hint 2:

  • When iterating through the list, keep a reference to the previous node as well as to the current node (that's one simple C# assignment inside the loop body).
  • After you found something, update the Next reference of the previous node (that's also one simple C# assignment).
  • Removing the first element requires special care, but let's take care of that after the rest of your algorithm works.

Upvotes: 3

Related Questions