Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!shadooby!samsung!zaphod.mps.ohio-state.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: The Universal Data Structure
Message-ID: <1708@uwm.edu>
Date: 30 Dec 89 22:35:24 GMT
Sender: news@uwm.edu
Reply-To: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Organization: University of Wisconsin-Milwaukee
Lines: 20


     I have in mind what might be aptly called the Universal Data Structure.
It is an ordered list with the following properties:

IT HAS ARRAY-LIKE FEATURES:
* Shift-by-K is a log(N) operation (where N is the list's size)
e.g.
  With arrays, one could perform a shift-by-K by adding K to the array index.

* Index Subtraction (finding the difference between 2 elements' indices)
  is log(N).

IT HAS LINKED-LIST-LIKE FEATURES:
* Insertion, and Deletion are log(N) operations.  With arrays, inserting or
deleting an element after the K'th element would require moving all the
remaining elements (k+1, k+2, ..., N) over by one.

     Is there a structure with such worst-case complexity?  There are hardware
implementations of arrays with the desired Insert/Delete behavior, but can the
structure be implemented other kinds of hardware?