CSC300 / CSC402: Linked Mutators using Loops

Contents [0/6]

Example [1/6]
Insertion logic [2/6]
The Middle [3/6]
The End [4/6]
The Beginning [5/6]
Cleanup [6/6]

(Click here for one slide per page)


Example [1/6]

Suppose I have a sorted linked list of doubles.

Let's write an insert method.

file:PlaygroundInsert.java [source]
01
02
03
04
05
06
07
08
09
10
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
 
package algs13;
import java.text.DecimalFormat;
import stdlib.*;
public class PlaygroundInsert {
  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
  }

  public static void main (String[] args) {
    //Trace.showObjectIdsRedundantly(true);
    Trace.showBuiltInObjects(true);
    Trace.drawStepsOfMethod ("insert");
    Trace.drawStepsOfMethod ("insertH");
    Trace.run ();
    testInsert ("[ 11 21 31 41 51 ]", "11 21 41 51", 31);
    //PlaygroundInsert list = of ("11 21 41 51"); 
    //list.insert(31);
    Trace.draw ();
    StdOut.println ("Finished tests");
  }
  
  public static void main1 (String[] args) {
    testInsert ("[ 11 21 31 41 51 ]", "11 21 41 51", 31);
    testInsert ("[ 11 21 31 41 51 ]", "11 31 41 51", 21);
    testInsert ("[ 11 21 31 41 51 ]", "11 21 31 51", 41);
    testInsert ("[ 11 21 31 41 51 ]", "11 21 31 41", 51);
    testInsert ("[ 11 ]", "", 11);
    testInsert ("[ 11 21 31 41 51 ]", "21 31 41 51", 11);
    StdOut.println ("Finished tests");
  }
  
  /* 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 PlaygroundInsert from(String s) {
    PlaygroundInsert result = new PlaygroundInsert ();
    if ("".equals (s)) return result;
    
    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) {
        throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
      }
    }
    result.first = first;
    return result;
  }

  private static void testInsert (String expected, String list, double item) {
    PlaygroundInsert aList = PlaygroundInsert.from (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);
    }
  }
}

Insertion logic [2/6]

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.next;

    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 [3/6]

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 [4/6]

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 [5/6]

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

Cleanup [6/6]

11
12
13
14
15
16
17
18
19
20
21
 
  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);
    }
  }