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

Contents [0/13]

Homework [1/13]
Mutator function patterns [2/13]
Cautious Loop [3/13]
Cautious Recursion (control freak) [4/13]
Cautious Recursion (control freak) [5/13]
Optimistic Recursion [6/13]
Does this work? [7/13]
Does this work? [8/13]
Does this work? [9/13]
Does this work? [10/13]
Does this work? [11/13]
Does this work? [12/13]
Does this work? [13/13]

Homework [1/13]

Notes about class

Mutator function patterns [2/13]

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);
  }
}

Cautious Loop [3/13]

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 cautious, 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:

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;
    }
  }

Cautious Recursion (control freak) [4/13]

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.

Cautious Recursion (control freak) [5/13]

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:

Optimistic Recursion [6/13]

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.

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

Some common mistakes:

Does this work? [7/13]

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/13]

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/13]

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/13]

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/13]

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/13]

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/13]

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);
    }
  }


Revised: 2008/03/17 13:01