The SquareList is a self-adjusting data structure that performs basic tasks such as insert, delete, and findmin. The structure is particularly useful in applications that frequently require the minimum and maximum values, as they both can be found in constant time. The SquareList maintains a doubly linked list of doubly linked lists of bounded size. The arrangement of the lists is similar to a square 2D array. The SquareList is required to abide by specific rules that let it perform insert/delete/find operations, within a worst-case running time of O(.
n)
The horizontal-linked list is comprised of one node from each of the vertical-linked lists. Those nodes are referred to as "top nodes." The design of the SquareList is such that the length of the list of top nodes will never be greater than [ [c.
As Figure 1 illustrates, the handle on SquareList is the "head," which is the minimum node. The SquareList is always sorted, so the maximum node can be found by following two pointers from the head. Every value in the circular linked list of top nodes is less than the value of the node to the right, with the exception of the last top node in the list. Each vertical list is also sorted in ascending order. The child nodes in the vertical list are not connected to nodes in other vertical lists.
Figure 1: The SquareList data structure.
One of the interesting characteristics of the SquareList is the pointer that connects the top node to the bottom node in the vertical list. The purpose of this pointer is so the nodes can be shifted from one vertical list to another in constant time. The bottom node pointer serves an additional benefit as well: The maximum node can be located in constant time.
It is necessary to keep track of the number of elements in the SquareList so that the length of the top list and the depth of the vertical lists can be controlled. Each top node contains a variable that holds the depth of the vertical list, which is incremented when a node is added, and decremented when a node is deleted. The use of a member variable eliminates the necessity of traversing the list to determine the depth.
Background
Table 1 lists several commonly used data structures. The priority queue is a binary tree that has the property that the root is smaller than its children and the subtrees have the same property. When extracting the root (min value), two trees are created and must be combined. Finding the maximum node is less efficient because all the leaf nodes need to be visited. The main advantage skiplists have over binary trees is that there is no need to balance the list. Skiplists have fast and consistent operations. The binomial heap is a set of binomial heaps that have the heap property—the key node is greater than the key of its parent. Binomial heaps also suffer from the disadvantage of having to search all of the leaf nodes to find the max value. Fibonacci heaps have an advantage in that they are able to perform operations that do not involve a delete in O(1) time. They are based on amortizing the amount of work to be performed. But from a practical perspective, Fibonacci heaps are less desirable because of the constant factors and because of their programming complexity.
Table 1: Commonly used data structures.
Inserting
As Listing One shows, inserting nodes into the SquareList is straightforward. When a new node is inserted into the SquareList, findVertList traverses the list of top nodes to find the vertical list in which the new node will be inserted. putInVertList places the node in the correct location in the vertical list. The depth of the top node of the current vertical list is then checked. If the depth is too great, the bottom node from that list is shifted to the top node of the list to the right. This progression continues recursively until a list is found with available space. This process is encapsulated in the shiftRight routine. If shiftRight is called and no space is found by the end of the SquareList, then either a new node is created or an analogous routine, shiftLeft, is called. The shiftLeft routine (Listing Two) pushes the nodes back until space is found in the SquareList. shiftLeft moves the top node of the vertical list to the bottom node of the vertical list to the left. The depth of that list is compared to the maxSize, and if the depth is too deep, shiftLeft is called recursively.
Listing One
void insert(int value)
{
slNode toAdd = new slNode(value);
size++;
if(size == 1)
head = toAdd;
else
{
slNode temp = findVertList(toAdd);
putInVertList(temp, toAdd);
}
updateMaxDepth();
}
Listing Two
private void shiftLeft(slNode top, int whichOp)
{
slNode temp = new slNode(top.getValue());
top.setValue(top.getChild().getValue());
if(top.getDepth() == 2)
top.setChild(top);
else
{
top.setChild(top.getChild().getChild());
top.getChild().setParent(top);
}
top.changeDepth(-1);
slNode left = top.getLeft();
temp.setParent(left.getBottom());
left.getBottom().setChild(temp);
temp.setParent(left.getBottom());
left.setBottom(temp);
left.changeDepth(1);
if(tooDeep(left, whichOp))
shiftLeft(left, whichOp);
}
The routines shiftLeft and shiftRight are required to run in O( time for n)insert/delete to run in O( time. The necessary adjustment of pointers is performed in constant time, but the number of times that n)shiftLeft or shiftRight could be called is [
The variable whichOp is set to a constant, which determines the allowable variation in the depth. The value of whichOp depends on whether the calling routine is delete or insert. shiftRight is analogous to shiftLeft.
For example, assume that you want to insert "75" in Figure 2. The top nodes are traversed until the proper vertical list is found. The vertical list is then traversed until the node is placed in the appropriate location. After the node is inserted, the depth of the top node ("50") is checked. If the depth exceeds maxSize (in this case, four), then a call to shiftRight is made to decrease the depth of the list. shiftRight is called recursively until the depths of all lists are no longer than maxSize; see Figure 3.
The values in the vertical list are not each shifted down one position. Rather, the bottom node of one list becomes the top node of the next, and the bottom pointer is reset. This allows the time bound to be met.
Figure 2: Insertion operation.
Figure 3: A shiftRight operation.
The shiftRight routine is called again; see Figure 4. If it is called when the top node equals head.getLeft, a check is made to determine if the list is square. If the number of nodes is square+1, then a new node is added to the list of top nodes and maxSize is incremented by 1. If the list is not square, then shiftLeft is called until a list is found that has a depth less than maxSize; see Figure 5.
Figure 4: A second shiftRight.
Figure 5: A shiftLeft operation.
findVertList examines the list of top nodes a maximum of [putInVertList examines, at most, [shiftRight is called, at most, [shiftLeft could be called, at most, [insert. The running time for insert is O([).
