A new representation for linear lists

ABSTRACT

We present a new data structure for maintaining a set of records in a linear list according to their key values. This data structure has the property that we can keep a number of fingers at points of interest in the key space (e.g., the beginning or the end of the list), so that access and modification in the neighborhood of a finger is very efficient. In the Section 2 we discuss the general structure of our B-tree. Since we propose to search the tree from a leaf upwards, additional links need to be introduced. In Section 3 we show how to obtain our result for the case of one finger. A key idea is the construction of a number representation behaving as described above, which we can use to model the propagation of modifications in the B-tree along the finger path. In Section 4 we generalize the structure so that several fingers in the key space can be maintained, with the advantage that access is cheap in the neighborhood of each finger. Finally in Section 5 we present some implementation notes and applications, mostly to sorting.

REFERENCES

• 1: R. Bayer and E. McCreight, "Organization and Maintainance of Large Ordered Indexes", Acta Informatica 1 (1972), 173-189
• 2: James R. Bitner , Gideon Ehrlich , Edward M. Reingold, Efficient generation of the binary reflected gray code and its applications, Communications of the ACM, v.19 n.9, p.517-521, Sept. 1976 [doi>10.1145/360336.360343]
• 3: Michael L. Fredman, Two applications of a probabilistic search technique: Sorting X+Y and building balanced search trees, Proceedings of seventh annual ACM symposium on Theory of computing, p.240-244, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803774]
• 4: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 5: Donald E. Knuth, The state of the Art of Computer Programming, Stanford University, Stanford, CA, 1976
• 6: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978
• 7: H. Rademacher, "On the Partition Function p(n)", Proc. London Math. Soc. 43, 241-254

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Records

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory