The SquareList Data Structure

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].