current = head; for (int i = 0; i //*** TOSTRING *** public String toString() { StringBuilder result = new StringBuilder("["); Node current = head; for (int i = 0; i current = head; for (int i = 0; i current = head; for (int i = 0; i current = head; for (int i = 0; i = size) throw new IndexOutOfBoundsException("Index: " + idx + ", Size: " + size); } private Node getNodeAt(int index){ /** write code for this method to return a reference to a node at a given index */ return null; }
//*** INNER NODE CLASS *** private static class Node { /** add code to consider 'previous' */ E element; Node next;
public Node(E e) { element = e; } } }
-----------------------------------
TestMyDoublyLinkedList.java
package A8;
public class TestMyDoublyLinkedList { public static void main(String[] args) {
String[] array = {"A", "B", "A", "A"}; MyDoublyLinkedList list = new MyDoublyLinkedList(array); System.out.printf("%-32s%-10s ", "Initialized with {A,B,A,A}:", list);
testAdding(list); testGetting(list); testSetting(list); testRemoving(list); testChecking(list);
System.out.printf(" %-32s%-10s ", "ToString: " , list); System.out.printf("%-32s%-10s ", "ToReversedString: " , list.toReversedString()); //the follow code should throw an exception System.out.println(" Adding 'X' at 20: "); list.add(20, "X"); }
private static void testAdding(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Adding elements: ", list); list.addFirst("*"); System.out.printf("%-32s%-10s ", " - '*' at first", list); list.addLast("C"); System.out.printf("%-32s%-10s ", " - 'C' at last", list); list.add("D");System.out.printf("%-32s%-10s ", " - 'D'", list); list.add(2, "#"); System.out.printf("%-32s%-10s ", " - '#' @ 2", list); } private static void testGetting(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Getting elements: ", list); System.out.printf("%-32s%-10s ", " - First Element", list.getFirst()); System.out.printf("%-32s%-10s ", " - Last Element", list.getLast()); System.out.printf("%-32s%-10s ", " - Element at 1", list.get(1)); System.out.printf("%-32s%-10s ", " - Element at 20", list.get(20)); } private static void testSetting(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Setting elements: ", list); System.out.printf("%-32s%-10s ", " - Element @ 0: '"+list.set(0,"+")+"' -> '+'", list); System.out.printf("%-32s%-10s ", " - Element @ 2: '"+list.set(2, "-")+"' -> '-'", list); System.out.printf("%-32s%-10s ", " - Element @ 9: '"+list.set(9, "&")+"' -> '&'", list); } private static void testRemoving(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Removing elements: ", list); System.out.printf("%-32s%-10s ", " - First element '" + list.removeFirst() + "'", list); System.out.printf("%-32s%-10s ", " - Last element '" + list.removeLast() + "'", list); System.out.printf("%-32s%-10s ", " - Element @ 1 '" + list.remove(1) + "'", list); System.out.printf("%-32s%-10s ", " - Element @ 9 '" + list.remove(9) + "'", list); } private static void testChecking(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Checking: ", list); System.out.printf("%-32s%-10s ", " - Contains 'A'? ", list.contains("A")); System.out.printf("%-32s%-10s ", " - Contains 'Z'? ", list.contains("Z")); System.out.printf("%-32s%-10s ", " - First occurence of 'A' @ ", list.indexOf("A")); System.out.printf("%-32s%-10s ", " - Last occurence of 'A' @ ", list.lastIndexOf("A")); System.out.printf("%-32s%-10s ", " - First index of 'Z' @", list.indexOf("Z")); System.out.printf("%-32s%-10s ", " - Last index of 'Z' @", list.lastIndexOf("Z")); } }
Download the attached classes (MyLinkedList.java and TestMyDoublyLinkedList.java) and add them to your project in Eclipse. Fix the package statement in each class to refer to your current package (see "Useful Eclipse Shortcuts" below) Rename MyLinkedList class to At this point, Eclipse should show no syntax errors. Add or change the code in MyDoublyLinkedList so as to convert it to a doubly linked list. That is, you need to have and use two references for each node: next, pointing to the next node, and previous, pointing to the previous node. Comments are added to My DoublyLinkedi?st beside the parts that need to be changed. Whenever you make a change, make sure that next and previous properly point to the correct nodes or to nul1 - Some comments ask you to improve the performance of your code using previous. Here, you have to think about how the performance can be improved knowing that each node points to both the next and the previous nodes. For example, if you want to get a reference to the second-to-last node, you would only need to use tail . previous instead of having to traverse the list from head up to the node at size-2 in case of singly linked lists. To improve the readability and maintainability of your code, try to use helper methods whenever appropriate. A method that you have to create is getNodeAt int index) which returns a reference to a node at a given index. Again, you have to try to improve the performance of this method given that you have both next and previous - - Testing: Use the TestMyDoublyLinkedList class to test your code. You should have an output similar to the one in the next page - - See if you can fixed the runtime error (shown in the next page) after adding 'X' at 20