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