001package algs13; 002import stdlib.*; 003 004public class MyLinked3 { 005 static class Node { 006 public Node() { } 007 public double item; 008 public Node next; 009 } 010 011 int N; 012 Node first; 013 014 public MyLinked3 () { 015 first = null; 016 N = 0; 017 checkInvariants (); 018 } 019 020 private void myassert (String s, boolean b) { if (!b) throw new Error ("Assertion failed: " + s); } 021 private void checkInvariants() { 022 myassert("Empty <==> first==null", (N == 0) == (first == null)); 023 Node x = first; 024 for (int i = 0; i < N; i++) { 025 if (x==null) { 026 throw new Error ("List too short!"); 027 } 028 x = x.next; 029 } 030 myassert("EndOfList == null", x == null); 031 } 032 033 public boolean isEmpty () { return first == null; } 034 public int size () { return N; } 035 public void add (double item) { 036 Node newfirst = new Node (); 037 newfirst.item = item; 038 newfirst.next = first; 039 first = newfirst; 040 N++; 041 } 042 043 // return Double.NEGATIVE_INFINITY if the linked list is empty 044 public double sum () { return sum (first); } 045 private static double sum (Node x) { 046 double result = 0; 047 while (x != null) { 048 result = result + x.item; 049 x = x.next; 050 } 051 return result; 052 } 053 054 // return Double.NEGATIVE_INFINITY if the linked list is empty 055 public double max () { 056 // TODO 057 return Double.NEGATIVE_INFINITY; 058 } 059 060 // return Double.NEGATIVE_INFINITY if the linked list is empty 061 public double maxRecursive () { 062 // TODO 063 return Double.NEGATIVE_INFINITY; 064 } 065 066 // delete the kth element 067 public void delete (int k) { 068 if (k < 0 || k >= N) throw new IllegalArgumentException (); 069 // TODO 1.3.20 070 checkInvariants (); 071 } 072 073 // reverse the list "in place"... without creating any new nodes 074 public void reverse () { 075 // TODO 1.3.30 076 checkInvariants (); 077 } 078 079 // remove 080 public void remove (double item) { 081 // TODO 1.3.26 082 checkInvariants (); 083 } 084 085 086 private static void print (String s, MyLinked3 b) { 087 StdOut.print (s + ": "); 088 for (Node x = b.first; x != null; x = x.next) 089 StdOut.print (x.item + " "); 090 StdOut.println (); 091 } 092 private static void print (String s, MyLinked3 b, double i) { 093 StdOut.print (s + ": "); 094 for (Node x = b.first; x != null; x = x.next) 095 StdOut.print (x.item + " "); 096 StdOut.println (": " + i); 097 } 098 public static MyLinked3 listFromString (String s) { 099 MyLinked3 list = new MyLinked3 (); 100 String[] nums = s.split (" "); 101 for (int i = nums.length-1; i >= 0; i--) { 102 try { list.add (Integer.parseInt (nums[i])); } catch (NumberFormatException e) {} 103 } 104 return list; 105 } 106 private static void testMax () { 107 MyLinked3 b = new MyLinked3 (); 108 print ("empty", b, b.max()); 109 b.add (-1); 110 print ("singleton", b, b.max()); 111 b.add (-2); 112 b.add (-3); 113 b.add (-4); 114 print ("at end", b, b.max()); 115 b.add (5); 116 print ("at beginning", b, b.max()); 117 b.add (3); 118 b.add (2); 119 b.add (4); 120 print ("in the middle", b, b.max()); 121 } 122 private static void testMaxRecursive () { 123 MyLinked3 b = new MyLinked3 (); 124 print ("empty", b, b.maxRecursive()); 125 b.add (-1); 126 print ("singleton", b, b.maxRecursive()); 127 b.add (-2); 128 b.add (-3); 129 b.add (-4); 130 print ("at end", b, b.maxRecursive()); 131 b.add (5); 132 print ("at beginning", b, b.maxRecursive()); 133 b.add (3); 134 b.add (2); 135 b.add (4); 136 print ("in the middle", b, b.maxRecursive()); 137 } 138 private static void testDelete () { 139 MyLinked3 b = new MyLinked3 (); 140 b.add (1); 141 print ("singleton", b); 142 b.delete (0); 143 print ("deleted", b); 144 for (double i = 1; i < 13; i++) { 145 b.add (i); 146 } 147 print ("bigger list", b); 148 b.delete (0); 149 print ("deleted at beginning", b); 150 b.delete (10); 151 print ("deleted at end", b); 152 b.delete (4); 153 print ("deleted in middle", b); 154 } 155 private static void testReverse () { 156 MyLinked3 b = new MyLinked3 (); 157 b.reverse (); 158 print ("reverse empty", b); 159 b.add (1); 160 print ("singleton", b); 161 b.reverse (); 162 print ("reverse singleton", b); 163 b.add (2); 164 print ("two", b); 165 b.reverse (); 166 print ("reverse two", b); 167 b.reverse (); 168 print ("reverse again", b); 169 for (double i = 3; i < 7; i++) { 170 b.add (i); 171 b.add (i); 172 } 173 print ("bigger list", b); 174 b.reverse (); 175 print ("reversed", b); 176 } 177 private static void testRemove () { 178 MyLinked3 b = new MyLinked3 (); 179 b.remove (4); 180 print ("removed 4 from empty", b); 181 b.add (1); 182 b.remove (4); 183 print ("removed 4 from singelton", b); 184 b.remove (1); 185 print ("removed 1 from singelton", b); 186 for (double i = 1; i < 5; i++) { 187 b.add (i); 188 b.add (i); 189 } 190 for (double i = 1; i < 5; i++) { 191 b.add (i); 192 b.add (i); 193 b.add (i); 194 b.add (i); 195 b.add (i); 196 } 197 print ("longer list", b); 198 b.remove (9); 199 print ("removed all 9s", b); // does nothing 200 b.remove (3); 201 print ("removed all 3s", b); 202 b.remove (1); 203 print ("removed all 1s", b); 204 b.remove (4); 205 print ("removed all 4s", b); 206 b.remove (2); 207 print ("removed all 2s", b); // should be empty 208 } 209 210 public static void main (String args[]) { 211 testMax (); 212 // testMaxRecursive (); 213 // testDelete (); 214 // testReverse (); 215 // testRemove (); 216 } 217} 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250