public class DNode { private char ch; private DNode next; private DNode prev; }
ID: 3630060 • Letter: P
Question
public class DNode {private char ch;
private DNode next;
private DNode prev;
}
Suppose that you have a doubly-linked list (implemented using the DNode class
described in the above). Write a method named
removeAllOccurrences() that takes two parameters, a reference to the first
node of the linked list and a character ch, and removes all occurrences of ch from
the linked list. Your method will need to return a reference to the first node in
the linked list, because the original first node may end up being removed . You do not need to code up this method as part of a
class – a written version of the method itself is all that is required. You may
assume that the method you write is a static method of the DNode class.
Explanation / Answer
public static DNode removeAllOccurrences(DNode root, char ch)
{
DNode curr = root;
while(curr != null) // break case: curr is null
{
if(curr.ch == ch)
{
// case: curr is root
if(curr.prev == null)
{
// next node is new root
root = curr.next;
// update curr.next prev node
if(curr.next != null)
curr.next.prev = null;
}
else
{
// link curr.prev to curr.next, both ways
curr.prev = curr.next;
if(curr.next != null)
curr.next.prev = curr.prev;
}
}
}
return root;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.