CSC300: Cautious Loop [3/13] Previous pageContentsNext page

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

Previous pageContentsNext page