# CSC300: Lecture 4 (Mutating Linked Structures (1.3))

 Contents [0/15]

 Homework [1/15] Mutator function patterns [2/15] Non-nullable Loop [3/15] Non-Nullable Recursion (control freak) [4/15] Non-Nullable Recursion (control freak) [5/15] Nullable Recursion [6/15] Does this work? [7/15] Does this work? [8/15] Does this work? [9/15] Does this work? [10/15] Does this work? [11/15] Does this work? [12/15] Does this work? [13/15] Stack [14/15] StackWithNonStaticNode [15/15]

 Homework [1/15]

Read Core Java for the impatient chapter 3 and sections 4.1-4.4.

 Mutator function patterns [2/15]

Suppose I have a sorted linked list of doubles.

Let's write an insert method.

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 ``` ```package algs13; import java.text.DecimalFormat; import stdlib.*; public class Playground { private Node first; static class Node { public double item; public Node next; public Node (double item, Node next) { this.item = item; this.next = next; } } public void insert (double item) { // TODO: insert item into a SORTED list } /* ToString method to print */ public String toString () { // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes DecimalFormat format = new DecimalFormat ("#.###"); StringBuilder result = new StringBuilder ("[ "); for (Node x = first; x != null; x = x.next) { result.append (format.format (x.item)); result.append (" "); } result.append ("]"); return result.toString (); } /* Method to create lists */ public static Playground of(String s) { Node first = null; String[] nums = s.split (" "); for (int i = nums.length-1; i >= 0; i--) { try { double num = Double.parseDouble (nums[i]); first = new Node (num, first); } catch (NumberFormatException e) { // ignore anything that is not a double } } Playground result = new Playground (); result.first = first; return result; } private static void testInsert (String expected, String list, double item) { Playground aList = Playground.of (list); aList.insert (item); String actual = aList.toString (); if (! expected.equals (actual)) { StdOut.format ("Failed [%s].insert(%f): Expecting (%s) Actual (%s)\n", list, item, expected, actual); } } public static void main (String[] args) { testInsert ("[ 11 ]", "", 11); testInsert ("[ 11 21 31 41 51 ]", "21 31 41 51", 11); testInsert ("[ 11 21 31 41 51 ]", "11 31 41 51", 21); testInsert ("[ 11 21 31 41 51 ]", "11 21 41 51", 31); testInsert ("[ 11 21 31 41 51 ]", "11 21 31 51", 41); testInsert ("[ 11 21 31 41 51 ]", "11 21 31 41", 51); StdOut.println ("Finished tests"); } public static void main2 (String[] args) { Trace.drawStepsOfMethod ("insert"); Trace.drawStepsOfMethod ("insertH"); Trace.run (); Playground list = Playground.of ("11 21 31 41"); list.insert (25); StdOut.println ("result: " + list); } }```

 Non-nullable Loop [3/15]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ``` ``` public void insert (double item) { if (first == null || first.item >= item) { first = new Node (item, first); } else { Node x = first; while (x.next != null && x.next.item < item) { x = x.next; } x.next = new Node (item, x.next); } }```

This kind of caution is slightly different than what we saw for accessor loops.

On our linked lists, mutator loops are inherently non-nullable, since the "first" item must be special case.

Here is a derivation.

To create this, you work in pieces: first get the insert logic.

 ``` 11 12 13 14 15 16 17 18 ``` ``` public void insert (double item) { Node x = first; Node y = new Node (item, null); Node f = x.next; x.next = y; y.next = f; }```

Passes some tests (inserts the item after first, as long as list is not empty)

Now figure out the loop.

As with all loops we work in pieces:

• first the middle
• then the end
• then the beginning

the middle: Let suppose the item is going into the middle. Let's figure out how to get to the right place. Use the test inserting 31 into [ 11 21 41 51 ].

 ``` 11 12 13 14 15 16 17 18 19 20 ``` ``` public void insert (double item) { Node x = first; while (x.next.item < item) { x = x.next; } Node y = new Node (item, null); Node f = x.next; x.next = y; y.next = f; }```

Passes more tests

the end: Now figure out what to do if you hit null.

 ``` 11 12 13 14 15 16 17 18 19 20 ``` ``` public void insert (double item) { Node x = first; while (x.next != null && x.next.item < item) { x = x.next; } Node y = new Node (item, null); Node f = x.next; x.next = y; y.next = f; }```

Passes more tests

the beginning: Now figure out how to start. For this style of list, we must have a special case, since we need to modify `first` rather than `next`.

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ``` ``` public void insert (double item) { if (first == null || first.item >= item) { Node y = new Node (item, null); Node f = first; first = y; y.next = f; } else { Node x = first; while (x.next != null && x.next.item < item) { x = x.next; } Node y = new Node (item, null); Node f = x.next; x.next = y; y.next = f; } }```

 Non-Nullable Recursion (control freak) [4/15]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ``` ``` public void insert (double item) { if (first == null || first.item >= item) { first = new Node (item, first); } else { insertH (first, item); } } private static void insertH (Node x, double item) { if (x.next != null && x.next.item < item) { insertH (x.next, item); } else { x.next = new Node (item, x.next); } }```

Direct translation of loop.

 Non-Nullable Recursion (control freak) [5/15]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ``` ``` public void insert (double item) { if (first == null || first.item >= item) { first = new Node (item, first); } else { insertH (first, item); } } private static void insertH (Node x, double item) { if (x.next == null || x.next.item >= item) { x.next = new Node (item, x.next); } else { insertH (x.next, item); } }```

A single function call both:

• creates the new node
• puts it in it's place

 Nullable Recursion [6/15]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ``` ``` public void insert (double item) { first = insertH (first, item); } private static Node insertH (Node x, double item) { if (x == null || x.item >= item) { return new Node (item, x); } else { x.next = insertH (x.next, item); return x; } }```

This is the easiest to write, once you understand it.

• One function call creates the new node
• Previous function call puts it in it's place. This could be the starter, or the helper, allowing us to only check the termination condition once!

This pattern is really great with balanced trees (next quarter).

Some common mistakes:

• Forget to update `first` in the starter.
• Forget to update `x.next` in the helper.
• Forget to return `x` in the helper.

 Does this work? [7/15]

 ``` 01 02 03 04 05 06 07 08 09 10 ``` ``` public void insert (double item) { insertH (first, item); } private static void insertH (Node x, double item) { if (x.next == null || x.next.item >= item) { x.next = new Node (item, x.next); } else { insertH (x.next, item); } }```

 Does this work? [8/15]

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 ``` ``` public void insert (double item) { if (first == null || first.item >= item) { first = new Node (item, first); } else { insertH (first, item); } } private static void insertH (Node x, double item) { if (x.next == null || x.next.item >= item) { x.next = new Node (item, x.next); } }```

 Does this work? [9/15]

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 ``` ``` public void insert (double item) { if (first == null || first.item >= item) { new Node (item, first); } else { insertH (first, item); } } private static void insertH (Node x, double item) { if (x.next == null || x.next.item >= item) { x.next = new Node (item, x.next); } else { insertH (x.next, item); } }```

 Does this work? [10/15]

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 ``` ``` public void insert (double item) { if (first == null || first.item >= item) { first = new Node (item, first); } else { insertH (first, item); } } private static void insertH (Node x, double item) { if (x.next == null || x.next.item >= item) { new Node (item, x.next); } else { insertH (x.next, item); } }```

 Does this work? [11/15]

 ``` 01 02 03 04 05 06 07 08 09 10 11 ``` ``` public void insert (double item) { insertH (first, item); } private static Node insertH (Node x, double item) { if (x == null || x.item >= item) { return new Node (item, x); } else { x.next = insertH (x.next, item); return x; } }```

 Does this work? [12/15]

 ``` 01 02 03 04 05 06 07 08 09 10 11 ``` ``` public void insert (double item) { first = insertH (first, item); } private static Node insertH (Node x, double item) { if (x == null || x.item >= item) { return new Node (item, x); } else { insertH (x.next, item); return x; } }```

 Does this work? [13/15]

 ``` 01 02 03 04 05 06 07 08 09 10 ``` ``` public void insert (double item) { first = insertH (first, item); } private static void insertH (Node x, double item) { if (x == null || x.item >= item) { new Node (item, x); } else { x.next = insertH (x.next, item); } }```

 Stack [14/15]

 file:Stack.java [source] [doc-public] [doc-private]
 ``` 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 ``` ```package algs13; import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac Stack.java * Execution: java Stack < input.txt * * A generic stack, implemented using a linked list. Each stack * element is of type Item. * * % more tobe.txt * to be or not to - be - - that - - - is * * % java Stack < tobe.txt * to be not that or be (2 left on stack) * *************************************************************************/ /** * The Stack class represents a last-in-first-out (LIFO) stack of generic items. * It supports the usual push and pop operations, along with methods * for peeking at the top item, testing if the stack is empty, and iterating through * the items in LIFO order. *

* All stack operations except iteration are constant time. *

* For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class Stack implements Iterable { private int N; // size of the stack private Node first; // top of stack // helper linked list class private static class Node { public Node () { } public T item; public Node next; } /** * Create an empty stack. */ public Stack() { this.first = null; this.N = 0; } /** * Is the stack empty? */ public boolean isEmpty() { return first == null; } /** * Return the number of items in the stack. */ public int size() { return N; } /** * Add the item to the stack. */ public void push(T item) { Node oldfirst = first; first = new Node<>(); first.item = item; first.next = oldfirst; N++; } /** * Delete and return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); T item = first.item; // save item to return first = first.next; // delete first node N--; return item; // return the saved item } /** * Return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return first.item; } /** * Return string representation. */ public String toString() { StringBuilder s = new StringBuilder(); for (T item : this) s.append(item + " "); return s.toString(); } // check internal invariants private static boolean check(Stack that) { int N = that.N; Stack.Node first = that.first; if (N == 0) { if (first != null) return false; } else if (N == 1) { if (first == null) return false; if (first.next != null) return false; } else { if (first.next == null) return false; } // check internal consistency of instance variable N int numberOfNodes = 0; for (Stack.Node x = first; x != null; x = x.next) { numberOfNodes++; } if (numberOfNodes != N) return false; return true; } /** * Return an iterator to the stack that iterates through the items in LIFO order. */ public Iterator iterator() { return new ListIterator(); } // an iterator, doesn't implement remove() since it's optional private class ListIterator implements Iterator { private Node current = first; public void remove() { throw new UnsupportedOperationException(); } public boolean hasNext() { return current != null; } //public ListIterator () { TraceGraph.draw (); } public T next() { if (!hasNext()) throw new NoSuchElementException(); T item = current.item; current = current.next; return item; } } /** * A test client. */ public static void bookMain(String[] args) { StdIn.fromString ("to be or not to - be - - that - - - is"); Stack stack = new Stack<>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) stack.push(item); else if (!stack.isEmpty()) StdOut.print(stack.pop() + " "); } StdOut.println(stack.size() + " left on stack:"); for (String s : stack) { StdOut.print (s + " "); } StdOut.println (); } public static void main(String[] args) { //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); Integer r1 = null; Stack s1 = new Stack<>(); s1.push (11); s1.push (21); s1.push (31); s1.push (41); s1.push (51); r1 = s1.pop (); r1 = s1.pop (); r1 = s1.pop (); r1 = null; s1.push (61); s1.push (71); String r2 = null; Stack s2 = new Stack<>(); s2.push ("a"); s2.push ("b"); s2.push ("c"); s2.push ("d"); s2.push ("e"); r2 = s2.pop (); r2 = s2.pop (); r2 = s2.pop (); r2 = null; s2.push ("f"); s2.push ("g"); s2.push ("h"); } public static void main2(String[] args) { Trace.showObjectIdsRedundantly (true); //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); Stack s1 = new Stack<>(); s1.push (300); Stack s2 = new Stack<>(); s2.push ("duck"); s2.push ("goose"); } } ```

 StackWithNonStaticNode [15/15]

 file:StackWithNonStaticNode.java [source] [doc-public] [doc-private]
 ``` 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 ``` ```package algs13; import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac Stack.java * Execution: java Stack < input.txt * * A generic stack, implemented using a linked list. Each stack * element is of type Item. * * % more tobe.txt * to be or not to - be - - that - - - is * * % java Stack < tobe.txt * to be not that or be (2 left on stack) * *************************************************************************/ /** * The Stack class represents a last-in-first-out (LIFO) stack of generic items. * It supports the usual push and pop operations, along with methods * for peeking at the top item, testing if the stack is empty, and iterating through * the items in LIFO order. *

* All stack operations except iteration are constant time. *

* For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class StackWithNonStaticNode implements Iterable { private int N; // size of the stack private Node first; // top of stack // helper linked list class private class Node { T item; Node next; } /** * Create an empty stack. */ public StackWithNonStaticNode() { this.first = null; this.N = 0; } /** * Is the stack empty? */ public boolean isEmpty() { return first == null; } /** * Return the number of items in the stack. */ public int size() { return N; } /** * Add the item to the stack. */ public void push(T item) { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } /** * Delete and return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); T item = first.item; // save item to return first = first.next; // delete first node N--; return item; // return the saved item } /** * Return the item most recently added to the stack. * @throws java.util.NoSuchElementException if stack is empty. */ public T peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return first.item; } /** * Return string representation. */ public String toString() { StringBuilder s = new StringBuilder(); for (T item : this) s.append(item + " "); return s.toString(); } // check internal invariants private static boolean check(StackWithNonStaticNode that) { int N = that.N; StackWithNonStaticNode.Node first = that.first; if (N == 0) { if (first != null) return false; } else if (N == 1) { if (first == null) return false; if (first.next != null) return false; } else { if (first.next == null) return false; } // check internal consistency of instance variable N int numberOfNodes = 0; for (StackWithNonStaticNode.Node x = first; x != null; x = x.next) { numberOfNodes++; } if (numberOfNodes != N) return false; return true; } /** * Return an iterator to the stack that iterates through the items in LIFO order. */ public Iterator iterator() { return new ListIterator(); } // an iterator, doesn't implement remove() since it's optional private class ListIterator implements Iterator { private Node current = first; public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public T next() { if (!hasNext()) throw new NoSuchElementException(); T item = current.item; current = current.next; return item; } } /** * A test client. */ public static void bookMain(String[] args) { StdIn.fromString ("to be or not to - be - - that - - - is"); StackWithNonStaticNode stack = new StackWithNonStaticNode<>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) stack.push(item); else if (!stack.isEmpty()) StdOut.print(stack.pop() + " "); } StdOut.println(stack.size() + " left on stack:"); for (String s : stack) { StdOut.print (s + " "); } StdOut.println (); } public static void main(String[] args) { //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); Integer r1 = null; StackWithNonStaticNode s1 = new StackWithNonStaticNode<>(); s1.push (11); s1.push (21); s1.push (31); s1.push (41); s1.push (51); r1 = s1.pop (); r1 = s1.pop (); r1 = s1.pop (); r1 = null; s1.push (61); s1.push (71); String r2 = null; StackWithNonStaticNode s2 = new StackWithNonStaticNode<>(); s2.push ("a"); s2.push ("b"); s2.push ("c"); s2.push ("d"); s2.push ("e"); r2 = s2.pop (); r2 = s2.pop (); r2 = s2.pop (); r2 = null; s2.push ("f"); s2.push ("g"); s2.push ("h"); } public static void main2(String[] args) { Trace.showObjectIdsRedundantly (true); //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); StackWithNonStaticNode s1 = new StackWithNonStaticNode<>(); s1.push (300); StackWithNonStaticNode s2 = new StackWithNonStaticNode<>(); s2.push ("duck"); s2.push ("goose"); } } ```

Revised: 2008/03/17 13:01