Stacked skip list data structures

Details Stacked skip list data structures Stacked skip list data structures

1995-10-02

1998-06-02

Black, Thomas G.

395603, 395462, 395470, G06F 1730

Patent

active

057615012

ABSTRACT:
Disclosed herein is a stacked skip list data structure for maintaining select nodes on multiple lists. The data structure includes a primary and a secondary skip list of nodes. Each node in the primary skip list uses at least one forward pointer in a primary array of forward pointers and provides a node level field for storing the level of such node, the level determined by the number of pointers being used. A secondary skip list is stacked on the primary skip list of nodes. It includes a subset (zero or more nodes) occurring on the primary skip list and utilizes zero or more unused forward pointers in the primary array as its forward pointers. Thus, a system agent performing operations on the secondary skip list utilizes the node level in the node level field as an index into the primary array of forward pointers to locate the secondary array of forward pointers.

REFERENCES:
patent: 4603380 (1986-07-01), Easton et al.
patent: 5261088 (1993-11-01), Baird et al.
patent: 5263160 (1993-11-01), Porter, Jr. et al.
patent: 5285528 (1994-02-01), Hart
patent: 5301290 (1994-04-01), Tetzlaff et al.
William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", Communications of the ACM, Jun. 1990, vol. 33, No. 6, pp. 668-676.
Robert Sedgewick, Algorithms, Addison-Wesley Publishing Co. (1988), pp. 15-33.
Jeffrey Esakov and Tom Weiss, Data Structures, Prentice-Hall, Inc. (1989), pp. 54-65.

Affiliated with

Also associated with

Rating

Stacked skip list data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Stacked skip list data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stacked skip list data structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1472615