- First Node Currentnode Previous Node Size Int Mylinkedlist Type Type Addbefore Item Addafter Item Type 1 (43.77 KiB) Viewed 47 times
public class MyLinkedListTest{private MyLinkedList<Integer> list;@Beforepublic final void setup(){list = new MyLinkedList<Integer>();}@Testpublic final void add_before(){list.addBefore(1);list.addBefore(2);list.addBefore(3);list.addBefore(4);assertEquals("add_before fail", "[1, 2, 3, 4]", list.toString());assertEquals("add_before fail", null, list.current());assertEquals("add_before fail", Integer.valueOf(1), list.first());assertEquals("add_before fail", Integer.valueOf(1), list.current());assertEquals("add_before fail", Integer.valueOf(2), list.next());assertEquals("add_before fail", Integer.valueOf(2), list.current());assertEquals("add_before fail", 4, list.size());}@Testpublic final void add_after(){list.addAfter(1);list.addAfter(2);list.addAfter(3);list.addAfter(4);assertEquals("add_after fail", "[]", list.toString());assertEquals("add_after fail", 0, list.size());}@Testpublic final void add_after_1(){list.addBefore(1);list.first();list.addAfter(2);list.addAfter(3);list.addAfter(4);assertEquals("add_after_1 fail", "[1, 4, 3, 2]", list.toString());assertEquals("add_after_1 fail", 4, list.size());}@Testpublic final void remove(){insert_ten_items(list);assertEquals("remove fail", null, list.remove());
assertEquals("remove fail", "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]",list.toString());assertEquals("remove fail", Integer.valueOf(0), list.first());assertEquals("remove fail", Integer.valueOf(0), list.remove());assertEquals("remove fail", "[1, 2, 3, 4, 5, 6, 7, 8, 9]",list.toString());assertEquals("remove fail", Integer.valueOf(2), list.next());assertEquals("remove fail", Integer.valueOf(3), list.next());assertEquals("remove fail", Integer.valueOf(4), list.next());assertEquals("remove fail", Integer.valueOf(4), list.remove());assertEquals("remove fail", "[1, 2, 3, 5, 6, 7, 8, 9]",list.toString());assertEquals("remove fail", 8, list.size());}@Testpublic final void contains_and_not(){insert_ten_items(list);assertTrue("contains_and_not fail", list.contains(3));assertFalse("contains_and_not fail", list.contains(100));assertEquals("contains_and_not fail", Integer.valueOf(0),list.first());assertEquals("contains_and_not fail", Integer.valueOf(1), list.next());assertEquals("contains_and_not fail", Integer.valueOf(2), list.next());assertEquals("contains_and_not fail", Integer.valueOf(3), list.next());assertEquals("contains_and_not fail", Integer.valueOf(3),list.remove());assertFalse("contains_and_not fail", list.contains(3));assertEquals("contains_and_not fail", "[0, 1, 2, 4, 5, 6, 7, 8, 9]",list.toString());}@Testpublic final void empty(){assertTrue("empty fail", list.isEmpty());assertEquals("empty fail", "[]", list.toString());}@Testpublic final void not_empty(){insert_ten_items(list);assertFalse("not_empty fail", list.isEmpty());assertEquals("not_empty fail", "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]",list.toString());}@Testpublic final void from_instruction(){assertEquals("from_instruction fail", "[]", list.toString());list.addBefore(1);assertEquals("from_instruction fail", "[1]", list.toString());list.addBefore(2);assertEquals("from_instruction fail", "[1, 2]", list.toString());list.addBefore(3);assertEquals("from_instruction fail", "[1, 2, 3]", list.toString());
assertEquals("from_instruction fail", Integer.valueOf(1),list.first());list.addAfter(4);assertEquals("from_instruction fail", "[1, 4, 2, 3]", list.toString());assertEquals("from_instruction fail", Integer.valueOf(1),list.current());assertEquals("from_instruction fail", Integer.valueOf(4), list.next());assertEquals("from_instruction fail", "[1, 4, 2, 3]", list.toString());assertEquals("from_instruction fail", Integer.valueOf(4),list.current());assertEquals("from_instruction fail", "[1, 4, 2, 3]", list.toString());assertEquals("from_instruction fail", Integer.valueOf(2), list.next());assertEquals("from_instruction fail", "[1, 4, 2, 3]", list.toString());assertEquals("from_instruction fail", Integer.valueOf(2),list.current());list.addBefore(5);assertEquals("from_instruction fail", "[1, 4, 5, 2, 3]",list.toString());list.addBefore(6);assertEquals("from_instruction fail", "[1, 4, 5, 6, 2, 3]",list.toString());assertEquals("from_instruction fail", Integer.valueOf(2),list.remove());assertEquals("from_instruction fail", "[1, 4, 5, 6, 3]",list.toString());}// ---------- helper methods ---------public final void insert_ten_items(MyLinkedList<Integer> list){for (int index = 0; index < 10; index++)list.addBefore(index);}}
#first: Node #currentNode #previous Node #size : int MyLinkedList<Type> : Type) +addBefore(item +addAfter (item : Type) +current(): Type +first(): Type +next(): Type +remove(): Type +contains (item : Type): boolean +size(): int +isEmpty(): boolean +toString(): String Field summary • first-A reference to the first node in the list. o Is null if the list is empty. This reference should be updated whenever the first node is changed. current - A reference to the current node in the list. The current node of the list is used to traverse. The current node should only be changed by the methods first, next and remove.
Initialized to be the null. When this node is null the current node has fallen off the end of the list. • previous - A reference to the node before the current node in the list. o Whenever the current node is updated you should update this node. This node is only null if current is equal to first. If current is null then this node should be the last node in the list. size - The number of elements stored in the list. 0 Method summary • add Before - Adds the item before the current node. This method adds the item between the previous node and the current node. If the current node is null the new element is added in the last position. If the current node is the first node then the new element becomes the new first node. This method should run in O(1) time. addAfter - Adds the item after the current node. This method adds the item between the current node and its next node. If the current node is null this method does nothing. This method should run in O(1) time. • remove - Removes the current node and returns the element. The link between the previous node and the node after the current node must be reconnected. If the current node is null this method does nothing and returns null. After this method the current node will be updated to the node after the removed node. This method should run in O(1) time. • current - Returns the item stored in the current node. This method returns null if the current node is null. This method should run in O(1) time. • first-Sets the current node to be the first node.
This method returns the item stored in the current node after the update. This method returns null if the first node is null. This method should run in O(1) time. next - Sets the current node to be the next node in the list. This method returns the item stored in the current node after the update. This method returns null if the current node is null. This method should run in O(1) time. • contains - Searches the nodes for the item and returns true if found (and false otherwise). This method should run in O(n) time. • size - Returns the field size. This method should run in O(1) time. • isEmpty - Returns true if the size is 0 and false otherwise. This method should run in O(1) time. • toString - Returns a string that has the contents of the nodes separated by commas and spaces and enclosed in square brackets. o Example: [1, 2, 3, 4] This method should run in O(n) time.
+item Type +next Node Node +toString(): String Note: Node should be a protected class within MyLinkedList. Field summary . item - The item stored in this node. • next - A reference to the next node in the list. Is null if there is no next node. Method summary • toString - Returns the toString of item.