Double Linked Question (JAVA)
Attached classes below
Attached classes
--------------------------------------------
MyLinkedList.java
package A8;
public class MyLinkedList { private int size; private Node head, tail;
// Constructors public MyLinkedList() { head = tail = null; } public MyLinkedList(E[] objects) { for (int i = 0; i
// Methods //*** ADDING *** public void add(E e) { addLast(e); } public void addFirst(E e) { /** add code to set 'previous' */ Node newNode = new Node(e); // Create a new node if (tail == null) // if empty list head = tail = newNode; // new node is the only node in list else { newNode.next = head; // link the new node with the head head = newNode; // head points to the new node } size++; } public void addLast(E e) { /** add code to set 'previous' */ Node newNode = new Node(e); // Create a new for element e if (tail == null) // if empty list head = tail = newNode; // new node is the only node in list else { tail.next = newNode; // Link the new with the last node tail = tail.next; // tail now points to the last node } size++; } public void add(int index, E e){/** add code to set 'previous' & to improve performance */ if (index size) throw new IndexOutOfBoundsException(); //according to Java doc. else if (index == 0) addFirst(e); else if (index == size) addLast(e); else { Node newNode = new Node(e); Node current = head; // ] for (int i = 1; i temp = head; // element will be returned head = head.next; size--; if (head == null) // if list becomes empty tail = null; return temp.element; // return the removed element } } public E removeLast() { /** improve performance using 'previous' */ if (size == 0) return null; else if (size == 1) { Node temp = head; head = tail = null; size = 0; return temp.element; } else { Node temp = tail; // to return it Node current = head; // get ref. to second to last for (int i = 0; i = size) return null; else if (index == 0) return removeFirst(); else if (index == size - 1) return removeLast(); else { Node previous = head; for (int i = 1; i current = previous.next; previous.next = current.next; size--; return current.element; } } public boolean remove(E e) { if (indexOf(e) >= 0) { //if the element exists remove(indexOf(e)); //call the other remove method return true; } else return false; } public void clear() { size = 0; head = tail = null; } //*** GETTING *** public E getFirst() { if (size == 0) return null; else return head.element; } public E getLast() { if (size == 0) return null; else return tail.element; } public E get(int index) { /** improve performance using 'previous' */ if (index = size) return null; else if (index == 0) return getFirst(); else if (index == size - 1) return getLast(); else { Node current = head; // ] for (int i = 0; i //*** SETTING *** public E set(int index, E e) { /** improve performance using 'previous' */ if (index size - 1) return null; Node 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
