	Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks

[Lab 3, CS206: Data Structures, Bryn Mawr College. In the following cell, give a hash title and by-line. Then you can remove this cell. This lab is due in one week.]

YOUR ANSWER HERE

Sorted Linked Lists¶

Consider our old friend Node:

class Node {
    double data;
    Node next;
    
    Node(double data) {
        this.data = data;
    }    
}

Node node = new Node(23.334);

node.data

Now, let's consider a slightly different LinkedList, a SortedLinkedList. This one has an insert method rather than an append method:

class SortedLinkedList {
    Node head;
    
    public void insert(Node node) {
        if (head == null) {
            head = node;
        } else if (node.data < head.data) {
            // insert here
            // NEED SOME CODE
        } else { // find where to insert it:
            Node current = head;
            while (current.next != null) {
                if (current.data < node.data) {
                    // insert it!
                    // NEED SOME CODE
                    return;
                }
            }
            // You got here and didn't insert!
            // insert it here
            // NEED SOME CODE
        }
    }
    
}

The idea is that when you insert a Node, it will put it in sorted order. In the next cell, define the method insert, and test it out to show that it works:

# YOUR CODE HERE
raise NotImplementedError()

Redefine the SortedLinkedList in the next cell, this time adding the method public boolean find(double value) that will look through the list and return true if the item is in the list, and false if it is not. When it finds it (or gives up), it should also print out how many comparisons it took. Test your function many times to see how it works.

# YOUR CODE HERE
raise NotImplementedError()

Sorted Binary Tree¶

Consider these Data Structures together that make a Binary Tree:

class Node {
    String data;
    Node left;
    Node right;
}

class BinaryTree {
    Node head;
}

We want to add an public void insert(Node node) method to BinaryTree like our SortedLinkedList, but we want to BinaryTree to remain sorted such that:

any string in any left branch is less than data
any string in any right branch is >= than data

Note that this is a recursive constraint, and is true for all BinaryTrees. Put the String in the first place that it will fit.

class BinaryTree {
    Node head;

    public void insert(Node node) {
        /// NEED CODE HERE
    }

}

In the following cell, define a BinaryTree with an public void insert(Node node) method. Test it out thoroughly to make sure it works.

# YOUR CODE HERE
raise NotImplementedError()

In the next cell, redefine BinaryTree to include the method public boolean find(String value) to search through and see if that value is in the tree. Return true or false appropriately. In addition, it should print out how many comparisons it took to determine the answer.

# YOUR CODE HERE
raise NotImplementedError()

Reflection¶

[In the following cell, give a thorough reflection of what you found and learned in this lab. Then you can remove this cell.]

YOUR ANSWER HERE

Jupyter at Bryn Mawr College

Sorted Linked Lists¶

Sorted Binary Tree¶

Reflection¶