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.
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.
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 propertythe 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.
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.
void insert(int value) { slNode toAdd = new slNode(value); size++; if(size == 1) head = toAdd; else { slNode temp = findVertList(toAdd); putInVertList(temp, toAdd); } updateMaxDepth(); }
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.
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.
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 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.
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.
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
])
.
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
.
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.
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].
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.