Rewrite your removeAll method from homework 3 to work with a chain of nodes that
ID: 3669071 • Letter: R
Question
Rewrite your removeAll method from homework 3 to work with a chain of nodes that is doubly linked. If you wish, you may base your answer on the posted homework 3 solution. The assumptions in the previous question still apply with the following changes: The DoubleListnode class has the same fields and methods as the Listnode class. The DoubleListnode class also has a field named prev and the methods getPrev and setPrev that work as described in lecture. The chain is guaranteed to be a correctly formed doubly-linked chain of nodes with the next field of the last node and the prev node of the header node both set to null. Give the worst-case time complexity for your method above expressed in "Big-O" notation. Include a brief justification for the time complexity you give and include any assumptions you make about the complexity of methods that are called by your implementations.Explanation / Answer
/*As you mention In homework solution we have provided you solution for linked List. In doubly linked list there is one difference only that in addition with next pointer we have previous pointer is also there which point to previous node of current node And previous pointer of first node and next pointer of last node is set to null.
So Here it also comes there case when we delete one node are:
Here is one simple doubly linkedlist declaration
*/
Class DoublyLinkedList {
static Node head = null;
class Node {
String data;
Node next, prev; // next and prev points to next and previous node
}
{
Node temp=head; // created new node which point to head node initially
While(!temp.data.equals(value) && temp!=null) //searching element in list which we want to delete
{
temp=temp.next;
}
/* base case */
if (temp == null ){
System.out.println(“Element not present in the list”);
return 0;
}
/* If node to be deleted is head node */ //case 1
if (head == temp) {
head = head.next;
head.prev=null;
}
/* Change next only if node to be deleted is NOT the last node */
if (temp.next != null) {
temp.next.prev = temp.prev;
}
/* Change prev only if node to be deleted is NOT the first node */
if (del.prev != null) {
del.prev.next = del.next;
}
/* Finally, free the memory occupied by temp*/
Return value;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.