Homework Assignment 3

Fast Linked Lists


Overview:

One of the primary disadvantages of linked lists over other data structures is that finding a specific element in a linked list, even if it is sorted, normally requires linear time. On contrary, searching a sorted array takes log(n) by peforming a binary search. Can we use a binary search on linked lists? Theoretically yes, however the searching won't be faster than linear search. This is because the linked list can only be accessed sequentially and not in random order.

In this lab assignment you will implement a sorted linked list that allows fast searching. How can we make searches faster? By implementing shortcuts! That it is, you will implement a sorted singly linked list with some shortcuts. This new data stucture allows skiping some nodes during searching, therefore leading to a better performance. To do a search in a normal singly-linked list of length n, we obviously need to look at n items in the worst case. To speed up this process, we can make a second-level list that contains roughly half the items from the original list.

Now we can find a value x (let x = 8) in this structure using a two-stage algorithm. First, we scan for x in the shortcut list, If we find x, we're done. Otherwise, we reach some value w = 9 bigger than x and we know that x = 8 is not in the shortcut list. In the second phase, we scan for x in the original list, starting from the predecessor of w which in the above picture is 7.

Now there is an obvious improvement - add shortcuts to the shortcuts, and repeat recursively. That's exactly how our fast linked lists are constructed. The picture below shows a fast linked list of 6 levels, where the level 0 is the bottom level:


Objectives:


Instructions:

Note, the implementation will be slightly different from the basic idea discussed in the overview. Therefore, read instructions carefully before you begin with coding.

You are to implement the FastLinkedList class that support search, insert and delete operations on Comparable data, which you may asume is not NULL. The FastLinkedList represents a single linked list of nodes. Each Node object contains a data field data and an array of references next

private static class Node<AnyType>
{
  public AnyType data;
  public Node[] next;

  public Node(int randLevel, AnyType data)
  {
    next = new Node[randLevel + 1];
    this.data = data;
  }
}

The size of this array is chosen at random (between 0 and some MAX_LEVEL) at the time when the node is created. For example, a level 3 node has 4 next references, indexed from 0 to 3. The references at index 0 always points to the immediate next node in the list. The other references point to nodes further down the list.

The first node of the FastLinkedList is a special header node that contains no data.

In simple terms, FastLinkedLists are sorted linked lists with two differences:

  1. the nodes in a regular linked list have one next reference. The nodes in FastLinkedLists have many next references.
  2. the number of next references for a given node is determined randomly.

toString():

This method simply traverses the level 0 references and visits every node while collecting the values. The method generates a string of values in a format of your choice.

You are to implement a second string method that takes a level as a parameter. The method traverses nodes at that given level. The method generates a string of values in a format of your choice.

These two methods are for debug purposes only and won't be graded by TAs.

Search:

The search algorithm is straightforward. Starting at the header in the highest level, we scan through each level as far as we can without passing the target value x, and then proceed down to the next level. The search ends when we either reach a node with search key x or fail to find x on the lowest level.

For example, here is a figure showing searching for 5. The boxes in cyan show the searching path:

This is like elevators in skyscrapers, each elevator goes to a specific level.

For testing and debug purposes, you are to implement a search method that takes two parameters: a value to search for and a level. This method returns true if it finds the specified value at the specified level, othewise, false. In the picture above, a call to contains(3, 1) returns true, but a call to contains(3, 2) returns false. See the starter code for design details.

Insert:

To insert a value (which you may assume is not NULL) we first perform the same kind of search. But, in order to insert a new node into the list we must maintain an array of references (it's called nodesToUpdate) to the nodes that must be updated. Here is a figure showing the insertion of a new element into FastLinkedList. The dashed lines show links that need to be changed.

Two things must be done to insert the node. We must make the new node x point at what the nodes in nodesToUpdate are currently pointing at. Then we update the nodes in nodesToUpdate to point at x.

Note, if the level of a new node is greater than any node already in the list then the header node must be updated and the level of the list must be set to the new level.

For testing and debug purposes, you are to implement an insert method that takes two parameters: a value to insert and a level. This method creates a new node with the specified level and inserts it into the list. See the starter code for design details.

Delete:

The deletion algorithm starts the same way as the insertion algorithm. We declare an update array nodesToUpdate and then search for the node to be deleted. If the node is found we set the nodes in nodesToUpdate to point at what x is pointing at. This effectively removes x from the list. After deleting the node we must check if the level of the list must be lowered.

Note that the list may contain duplicates. Your delete method must delete only the first occurrence.


Starter Code:

Download the following files

What to submit:

You FTP the following java files

  1. FastLinkedList.java

Do not submit anything else like zip files, folders, desktops, class files. Failure to do so will result in 10 points penalty.


Grading:

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate method/classes were used, as well as judge the overall style and modularity of your code. Points will be deducted for poor design decisions and un-commented, or un- readable code.


Victor S.Adamchik, CMU, 2009