Article View: comp.theory
Article #1980The Universal Data Structure
From: Mark William Hopkins
Date: Sat, 30 Dec 1989 22:35
Date: Sat, 30 Dec 1989 22:35
20 lines
1298 bytes
1298 bytes
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?
Technical Details
Message-ID:
<1708@uwm.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!shadooby!samsung!zaphod.mps.ohio-state.edu!uwm.edu!csd4.csd.uwm.edu!markhShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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