Browse Prior Art Database

Linear List Insertion Placement Algorithm

IP.com Disclosure Number: IPCOM000122715D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 53K

Publishing Venue

IBM

Related People

Cline, TL: AUTHOR [+1]

Abstract

Common list insertion requires inserting at the head, tail, after an object, and before an object in a linear list. How the positional information for insertion into a linear list can be architected to garner the least amount of memory used is disclosed in this document.

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

Linear List Insertion Placement Algorithm

      Common list insertion requires inserting at the head, tail,
after an object, and before an object in a linear list.  How the
positional information for insertion into a linear list can be
architected to garner the least amount of memory used is disclosed in
this document.

      Insertion into a linear list of objects is a common requirement
in list management.  Information is required to indicate where the
object is to be positioned in the list.

      The following algorithm will allow an N-bit field to contain
all the information that is necessary to indicate where an item is to
be positioned given that objects are identified by the sequence of
bits turned on and off (i.e., the lowest order bit on and all others
off would be the first identifier and N-1 bits on would be the last
identifier).

      Since the identifier in the list is specified with N-1 bits,
the highest order bit N is used to indicate if the insertion should
be before or after the list item that is identified by the N-1 bits.
      o   If the value found in the N-1 bit field equals an object
identifier that is in the list and the highest order bit N is off,
then the insertion point is after that object.
      o   If the value found in the N-1 bit field equals an object
identifier that is in the list and the highest order bit N is on,
then the insertion point is before that object.
      o   If N-1 bits are all off, the...