ListReferenceBased.java (3871B)
1 package lab3; 2 3 // Please note that this code is slightly different from the textbook code 4 //to reflect the fact that the Node class is implemented using data encapsulation 5 6 7 // **************************************************** 8 // Reference-based implementation of ADT list. 9 // **************************************************** 10 public class ListReferenceBased implements ListInterface 11 { 12 // reference to linked list of items 13 private Node head; 14 private int numItems; // number of items in list 15 16 public ListReferenceBased() 17 { 18 numItems = 0; 19 head = null; 20 } // end default constructor 21 22 public boolean isEmpty() 23 { 24 return numItems == 0; 25 } // end isEmpty 26 27 public int size() 28 { 29 return numItems; 30 } // end size 31 32 private Node find(int index) 33 { 34 // -------------------------------------------------- 35 // Locates a specified node in a linked list. 36 // Precondition: index is the number of the desired 37 // node. Assumes that 0 <= index <= numItems 38 // Postcondition: Returns a reference to the desired 39 // node. 40 // -------------------------------------------------- 41 Node curr = head; 42 for (int skip = 0; skip < index; skip++) 43 { 44 curr = curr.getNext(); 45 } // end for 46 return curr; 47 } // end find 48 49 public Object get(int index) 50 throws ListIndexOutOfBoundsException 51 { 52 if (index >= 0 && index < numItems) 53 { 54 // get reference to node, then data in node 55 Node curr = find(index); 56 Object dataItem = curr.getItem(); 57 return dataItem; 58 } 59 else 60 { 61 throw new ListIndexOutOfBoundsException( 62 "List index out of bounds exception on get"); 63 } // end if 64 } // end get 65 66 public void add(int index, Object item) 67 throws ListIndexOutOfBoundsException 68 { 69 if (index >= 0 && index < numItems+1) 70 { 71 if (index == 0) 72 { 73 // insert the new node containing item at 74 // beginning of list 75 Node newNode = new Node(item, head); 76 head = newNode; 77 } 78 else 79 { 80 Node prev = find(index-1); 81 // insert the new node containing item after 82 // the node that prev references 83 Node newNode = new Node(item, prev.getNext()); 84 prev.setNext(newNode); 85 } // end if 86 numItems++; 87 } 88 else 89 { 90 throw new ListIndexOutOfBoundsException( 91 "List index out of bounds exception on add"); 92 } // end if 93 } // end add 94 95 public void remove(int index) 96 throws ListIndexOutOfBoundsException 97 { 98 if (index >= 0 && index < numItems) 99 { 100 if (index == 0) 101 { 102 // delete the first node from the list 103 head = head.getNext(); 104 } 105 else 106 { 107 Node prev = find(index-1); 108 // delete the node after the node that prev 109 // references, save reference to node 110 Node curr = prev.getNext(); 111 prev.setNext(curr.getNext()); 112 } // end if 113 numItems--; 114 } // end if 115 else 116 { 117 throw new ListIndexOutOfBoundsException( 118 "List index out of bounds exception on remove"); 119 } // end if 120 } // end remove 121 122 public void removeAll() 123 { 124 // setting head to null causes list to be 125 // unreachable and thus marked for garbage 126 // collection 127 head = null; 128 numItems = 0; 129 } // end removeAll 130 131 } // end ListReferenceBased