Localized search in sorted lists

ABSTRACT

It is well known that every one of the set operations insert, delete and member can be performed in O(log n) steps, where n is the number of elements currently in the set. Here we implement these operations and a move operation for a sorted list with f fingers (points of reference) established on the list. It is shown that these operations can be performed in O(log d) steps, where d is the distance between the corresponding finger and the key involved.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: M. R. Brown, R. E. Tarjan: Design and Analysis of a Data Structure for Representing Sorted Lists, SICOMP, 1980, 594-614.
• 3: Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803395]
• 4: S. Rao Kosaraju, Real-time simulation of concatenable double-ended queues by double-ended queues (Preliminary Version), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.346-351, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804427]
• 5: Benton L. Leong , Joel I. Seiferas, New Real-Time Simulations of Multihead Tape Units, Journal of the ACM (JACM), v.28 n.1, p.166-180, Jan. 1981 [doi>10.1145/322234.322246]
• 6: Kurt Mehlhorn, A New Data Structure for Representing Sorted Lists, Proceedings of the International Workshop on Graphtheoretic Concepts in Computer Science, p.90-112, June 15-18, 1980

INDEX TERMS

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

Additional Classification:
  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: Trees

General Terms:
Algorithms, Theory