Answer Happy

Question 2160 pts] Doubly linked list programming assignment: Rewrite the implementation of a sorted list using a doubly linked list. Use as a guide the implementation with a single linked list (lecture notes). Definition: A doubly linked list is a list in which each node is linked to both its successor and its predecessor. Example: listData David Joshua In this definition, a node has 2 link members; one is a reference to the next node in the list-immediate successor, and the other is a reference to the previous node in the list-immediate predecessor. The first node in the list has no predecessor and the last node has no successor. The advantage of using a double linked list is that the list can be traversed from first node to last, as any linked list, AND ALSO from last node to first (very convenient when we need to traverse a list backwards). The disadvantage is the extra storage required for the second reference in each node. Also, the inserting and deleting operations are a bit slower (both references have to be updated). Operations to be implemented on a double linked list: 1. Initialize the list 2. Determine whether the list is empty 3. Retrieve the first element in the list. 4. Retrieve the last element in the list 5. Find the length of the list 6. Display the list (direct and reverse order) 7. Search the list for a given item 8. Insert an item in the list 9. Delete an item from the list 10. tostring (direct and reverse order, 2 versions for each, one using recursion) 11. Compare 2 lists for equality (equals) 12. Make a copy of the list 13. Make a copy of the list in reverse order Use this interface: public interface DoublelinkedListADT<T> ( public void initializelist(); public boolean isEmptyList(); public T front (); Leah public T back(); public int length(); public void print (); Miriam
public void reversePrint (); public boolean search (T searchiten); public void insertNode (7 insertitem); public void deleteNode (T deleteItem)/ public String tostring(): public String recursiveToString(); public String backwardsString(); public String recursive BackwardsString(); public boolean equals (Object o); public void copy (DoubleLinkedlist<T> otherList); public void reversedCopy (Double LinkedList<T> otherList); Complete this class definition: public class DoublelinkedList<T> implements DoublelinkedListADT<T> I //Double linked list node class public class DoublelinkedlistNode<T> ( Tinfo; DoublelinkedLiatNode<T> next; DoublelinkedListNode<T> back; public DoublelinkedlistNode() ( info null; next = null; back null; public String toString() ( return info.toString(); protected int count; //number of nodes. protected DoublelinkedlistNode<T> first; //reference to first node protected DoublelinkedListNode<T> last; //reference to last node I Use this client program to do the testing: public class client_DLLString ( public static void main(String[] args) ( DoublelinkedList<String>list_: new DoublelinkedList<String> (); DoublelinkedList<String>list 2 new DoubleLinkedList<String> (); String item; list_1.insertNode("John"); list_1.insertNode ("Ann") 7 11st 1.insertNode ("Faul");
list_1.insertNode ("Joshua"); list_1.insertNode ("Will"); list_1.insertNode ("Erma"); list_1.insertNode ("Peter"); list_1.insertNode ("Linda"); list_1.insertNode ("Joan"); list_1.insertNode ("David"); list_1.insertNode ("Miriam"); list_1.insertNode ("Leah"); list_1.insertNode ("Jane"); System.out.println("Inserted in first list the names: John, Ann, Paul, Joshua, Will, Emma, Peter, Linda, Joan, David, MIriam, Leah, Jane"); System.out.println(" (Testing toString) First list sorted is: list_1); System.out.println(" (Testing recursive tostring) First list sorted is: [head) + list_1.recursiveToString()); System.out.println(" (Testing backwards) First list reversed (print) is:;" + list 1.backwardsString()); System.out.print(" (Testing recursive backwards) Firat list reversed (print) is: " + list 1.recursiveBackwardsString()); System.out.println(" [head]"); System.out.println("Will copy in second list only names that don't start with J. List one destroyed."); while (!list_1.isEmptyList ()) { itemlist_1.front (); list_1.deleteNode (item); if (item.charAt(0) 1 J¹) list_2.insertNode (item); System.out.println("Second list should hold names that don't start with J (sorted): System.out.println("First list should be empty. Nothing printed. "); ) + list 2): list_1.print(); System.out.print(" (Testing equals) "); if (list_1.equals (list_2)) System.out.println("The 2 lists are equals"); System.out.println("The 2 lists are NOT equals"); System.out.print(" (Testing, copy) "); list copy (list_2); else System.out.println("First list after copy is: " + list_1); System.out.print(" (Testing reversed copy) "); list_1.reversedCopy (11st_2); System.out.println("First list as the copy of the second list reversed is: list_1); 1
OUTPUT: Inserted in first list the names: John, Ann, Paul, Joshua, Will, Emma, Peter, Linda, Joan, David, Miriam, Leah, Jane (Testing tostring) First list norted is: [head] - Ann David Enna Jane Joan John Paul - Mirian - Joshua Leah Linda - Miriam Faul Peter Will [tail) (Testing recursive tostring) Firat list sorted is: [head] - Ann- David - Emma- Jane- Joan John Joshua Leah Linda - Miriam Paul Peter - Will - [tail] (Testing backwards First list reversed (print) is: [tail) - will - Peter Linda Leah Joshua John Joan Jane Emma David Ann- [head) (Testing recursive backwards) Firat list reversed (print) in: [tail] Will - Peter - Paal - Miriam - Linda Leah Joshua John Joan Jane Enna David Ann- [head] Will copy in second list only names that don't start with J. List one destroyed. Second list should hold names that don't start with J (sorted): [head] Ann-David- Emma Leah Linda Mirian Paul Peter Will (tail] First list should be empty. Nothing printed. (Testing equals) The 2 lists are NOT equals (Testing copy) First list after copy is: [head] - Ann David - Enna - Leah - Linds- Miriam Paul Peter Will (tail] (Testing reversed copy) First list as the copy of the second list reversed is: (head) Will - Peter Paul - Miriam Linda Leah Emma - David Ann- [tail] Hints: Take a look at the following picture when you write the method to insert a node: II Joshua 11stData Ⓒ H Leah newlode David Miriam Take a look at the following picture when you write the method to delete a node: location Delete Joshua Joshua 7 - Miriam