The SquareList Data Structure

The SquareList self-adjusting data structure Mark presents here performs basic tasks such as insert, delete, and findmin. It's particularly useful in programs that frequently require minimum and maximum values.


May 01, 2003
URL:http://www.drdobbs.com/database/the-squarelist-data-structure/184405336

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.

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(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 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 [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]).

Deleting

Deleting is similar to inserting, although differences do exist. When a node is deleted, the depth of the vertical list is checked. If the depth of the list equals maxSize-1, then no modifications need to be made to the list. If the depth of the list equals maxSize-2 (or some constant c), then a node is shifted into the list to increase its depth; see Listing Three.

Listing Three

public int delete(int value)
{
    slNode top = new slNode(findVertList(value));
    slNode toDelete = findInVertList(top, value);
    if(toDelete == null)
        return -1;
    size--;
    // Top node 
    if(toDelete.getParent() == null)
        deleteParentNode(toDelete);
    // Bottom node in sublist
    else if(toDelete.getChild() == toDelete)
        deleteBottomNode(top);
    // Found node in sublist
    else 
        deleteMiddleNode(top, toDelete);
    updatemaxDepth();
    delFixUp ();
    return value;
}

Delete must find the value of the node to be deleted. It begins by examining [n] top nodes to find the appropriate vertical list. Then, [n] nodes in the vertical list are searched to find the node. The removal of the node is simply a matter of manipulating pointers, so it is performed in constant time. The use of delFixUp yields a running time of O([n]).

After the completion of a delete operation, delFixUp is called. If a deleted node had a depth equal to maxDepth, then delFixUp would not need to be executed. delFixUp does one of three things when called. If a list has a depth of maxDepth-2, then a search is performed for a list that has a depth of maxSize. When that list is found, then either shiftLeft or shiftRight is called to balance the depth of the list. If no lists are found to have a depth equal to maxSize, then a node is shifted from the last list into the list that is too short via shiftLeft; see Listing Four.

Listing Four

private void delFixUp (slNode theTop)
{
    // Nothing needs to be done.
    if(theTop.getDepth() == maxDepth -1)
        return;
    slNode temp = getFullList();
    if(temp.getValue() > theTop.getValue())
        // This situation should only occur if the list goes from 
       // square + 1 to square
        if((temp == head.getLeft()) && (temp.getDepth() == 1))
        {
            // Move the last node left one list
            putInVertList(temp.getLeft(), temp);
            // Only want to shiftLeft if node is not placed in the short list
            if(theTop != temp.getLeft())
                shiftLeft(temp.getLeft(), ONE);
            // Set the respective pointers
            head.setLeft(temp.getLeft());
            temp.getLeft().setRight(head);
    }
        else shiftLeft(temp, ONE);
    else if(temp.getValue() < theTop.getValue())
        shiftRight(temp, ONE);      
    else ;  // Do nothing.  Depths of lists are appropriate
}



The reason for requiring all vertical lists (except the last list) to be no shorter than maxSize-1 is so that when the list goes from square+1 to square, the deletion of one node results in a list that is perfectly square. getFullList returns the top node of the list with depth [n]. A comparison is made between that top node and the deleted node. If the top node is smaller than the deleted node, then shiftRight is called to move nodes from the left to the right. If the top node is greater than the deleted node, then the nodes are shifted from right to left with the shiftLeft routine.

If the depth of a vertical list needs to be corrected, getFullList examines [n] nodes in the list of top nodes. Then either shiftRight or shiftLeft is used to move the nodes, which have a stated running time of O([n]).

Testing

To empirically test the data structure, I created a SquareList of size n before adding or deleting any nodes. I then performed three tests that involved inserting 100 nodes into the list. After the completion of those trials, I then executed three trials of deleting 100 nodes from the list. My strategy was as follows: Within the code, counters were placed inside loops. The counter was incremented with each iteration of the loop, and the value was returned upon completion. After creating the list, the counter was reset to 0. Then, 100 nodes were either inserted in or deleted from the list. For example, in trial number 1 with 1000 nodes, the first node was inserted into a list of 1000 nodes, and the 100th insertion was into a list with 1099 nodes. Table 2 shows the data, while Figure 6 graphs it. The average value of the counter for insertion and deletion is highlighted as well as the value of n. The last two columns show the ratio of insert or delete as a ratio of n.

Table 2: Test results.

Figure 6: Test results plot.

Conclusion

Clearly, there are changes you could make to improve the efficiency of the SquareList. For instance, findVertList could search left or right to find the appropriate vertical list. If users know in advance that data will be somewhat ordered, this could be a significant advantage. Alternatively, putInVertList could search from the bottom up as well as from the top down to find the correct location of a node. The SquareList may also be more efficient if calls to shiftLeft and shiftRight are delayed until a time that requires that the list be "squared." Programmers could also implement dummy nodes to make the implementation more convenient.

Acknowledgement

Thanks to Dr. John C. Lusth for his guidance on this project.


Mark is a contract programmer for Adecco Technical. He can be contacted at [email protected].

May03: The SquareList Data Structure

Figure 2: Insertion operation.

May03: The SquareList Data Structure

Figure 3: A shiftRight operation.

May03: The SquareList Data Structure

Figure 4: A second shiftRight.

May03: The SquareList Data Structure

Figure 5: A shiftLeft operation.

May03: The SquareList Data Structure

Figure 6: Test results plot.

May03: The SquareList Data Structure

Table 1: Commonly used data structures.

May03: The SquareList Data Structure

Table 2: Test results.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.