Skip list data structure enhancements

Details Skip list data structure enhancements Skip list data structure enhancements

1995-10-02

1997-08-19

Loomis, John C.

395611, G06F 1730

Patent

active

056597398

ABSTRACT:
A system and technique for optimizing the efficiency of maintenance operations performed on skip lists of data elements or nodes stored in memory is provided. Each node of a skip list includes a back pointer for pointing to an immediate predecessor node and a node level field for recording the node level associated with the node. The system further includes a system agent for operating on the data structure, the system agent capable of locating the address of the immediate predecessor node pointing to a selected node by using the back pointer in the selected node.

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.
William Pugh, "Efficient Concatenable Ordered Lists", TR 87-831, Cornell University (1987).
Robert Sedgewick, Algorithms, Addison-Wesley Publishing Co. (1988), pp. 15-33, 193-212.
Jeffrey Esakov and Tom Weiss, Data Structures, Prentice-Hall, Inc. (1989), pp. 54-65, 184-191.
William Pugh, "A Skip List Cookbook" Jul. 1989 pp. 1-14.

Affiliated with

Also associated with

Rating

Skip list data structure enhancements does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1112593