CSC300: Example [1/6] Previous pageContentsNext page

Suppose I have a sorted linked list of doubles.

Let's write an insert method.

file:LinkedInsert.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
 
package ds1.student.linked;

import stdlib.StdOut;

import java.text.DecimalFormat;

public class LinkedInsert {
    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) {
        testInsert ("[ 11 21 31 41 51 ]", "11 21 41 51", 31);
        //PlaygroundInsert list = of ("11 21 41 51"); 
        //list.insert(31);
        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 LinkedInsert from(String s) {
        LinkedInsert result = new LinkedInsert();
        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) {
        LinkedInsert aList = LinkedInsert.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);
        }
    }
}

Previous pageContentsNext page