Browse Prior Art Database

Insertion Into a Sorted Linked

IP.com Disclosure Number: IPCOM000099200D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 2 page(s) / 88K

Publishing Venue

IBM

Related People

Ashford, TJ: AUTHOR [+2]

Abstract

This invention relates to a method for insertion using a hash table to reduce the search time to each new element in a triply, bilaterally linked list sorted elements, the links respectively ordering events, concurrent time but unique priority, and time. The method comprises the steps of (a) whether the insertion of a new element can be as a special case, and (b) in the event that such not the case, hashing and linearly searching along the ordering dimension in a preselected manner.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Insertion Into a Sorted Linked

       This invention relates to a method for insertion using a
hash table to reduce the search time to each new element in a triply,
bilaterally linked list sorted elements, the links respectively
ordering events, concurrent time but unique priority, and time.  The
method comprises the steps of (a) whether the insertion of a new
element can be as a special case, and (b) in the event that such not
the case, hashing and linearly searching along the ordering dimension
in a preselected manner.

      Consider an existing list of events (sorted in ascending by
time) of length 98, having one event for each of times 1-100 except
for the times 70 and 10.  The last events to be inserted were 73, 77,
80, 75, and 81.  In to this sorted list, there is an associated hash
and a list of most recently inserted new times.  The table provides a
means of associating a key and a  In this case, the set of keys
consists of all the found in the sorted list, and the value
associated a key in the hash table is a pointer to an event in the
list having a time field equal to the key.  When is more than one
event at a given time, then the is to the one which occurs first in
the sorted list. "look-up" in the hash table is a query in which a
key is and the associated value retrieved.  The benefit of hash table
is that this query is made in an constant time (as opposed to a
linear search the list, whose time increases linearly with the of the
list).  The list of most recently inserted new will have its oldest
element replaced on each by the newest element.  This will occur only
when "new" time (one requiring the use of this special list) is  The
length of the list (the number of most inserted events which are
remembered) may be of any but is of length 5 for these examples.  The
length the list is always to be short, in any case, so th...