Fast Linked Lists

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:

- Practice implementing and using a linked list data structure
- Practice using generics
- Practice using Comparable interface

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:

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

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.

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.

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.

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.

You FTP the following java files

- FastLinkedList.java

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

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