# The SquareList Data Structure

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` `[`n`]. The list that is specific to each top node, the "vertical list," will also be restricted to the same depth limit of` `[`n`] plus some constant `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.

### 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)
{
size++;
if(size == 1)
else
{
}
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(n)` time for `insert/delete` to run in `O(n)` time. The necessary adjustment of pointers is performed in constant time, but the number of times that `shiftLeft` or `shiftRight` could be called is [`n`] if the entire list of top nodes needs to be traversed.

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 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 5: A shiftLeft operation.

`findVertList` examines the list of top nodes a maximum of [`n`] times to find the correct vertical list. `putInVertList` examines, at most, [`n`] nodes to find the appropriate location. To ensure the depths of the vertical lists are correct, `shiftRight` is called, at most, [`n`] times, and `shiftLeft` could be called, at most, [`n`] times, each of which run in constant time. While this may appear to be a cumulative running time of 4*[`n`], the actual running time can be limited to 3*[`n`] for a single `insert`. The running time for `insert` is `O(`[`n`]`).`

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.