Lab 1 #

Let’s define the following interfaces:

interface Query<T, U> {
  U search(T index);
  Query add(T index, U value);
  Query delete(T index);
}

And the following abstract class:

abstract class SearchableNode<T, U> {
    private T index;    // the index of the node
    private U value;    // the value of the node

    public T getIndex() {
        return index;s
    }
    public U getValue() {
        return value;
    }
    
    public void setIndex(T index) {
        this.index = index;
    }
    
    public void setValue(U value) {
        this.value = value;
    }
}

Question 1 #

Write classes LinkedList (implements the Query interface) and LinkedListNode (extends from SearchableNode class) to implement linked list.

Make sure when you implement the search method, always print the items you went through (i.e., from the head node).

Question 2 #

Add searchFromTail method on top of question 1.

Question 3 #

Write classes BinarySearchTree (implements the Query interface) and BinarySearchTreeNode (extends from SearchableNode class) to implement a binary search tree.

Make sure when you implement the search method, always print the items you went through (i.e., from the root of the tree).

Question 4 #

Write classes SkipList (implements the Query interface) and SkipListNode (extends from SearchableNode class) to implement a skip list.

To save space, lets set the promotion rate to be 0.25. Which means, level 1 index will include only 1/4 items of the original linked list, and so on.

Make sure when you implement the search method, always print the items you went through (i.e., from the highest level of index).

Note #

You are encouraged to use recursion to implement the methods if possibles. It is more important to get things work correctly, and getting your code readable, rather than the efficiency of the algorithm.