Maintaining order in a linked list

ABSTRACT

We present a new representation for linked lists. This representation allows one to efficiently insert objects into the list and to quickly determine the order of list elements. The basic data structure, called an indexed 2-3 tree, allows one to do n inserts in O(nlogn) steps and to determine order in constant time. We speed up the algorithm by dividing the data structure up into log*n layers. The improved algorithm does n insertions and comparisons in O(nlog*n) steps. The paper concludes with two applications: determining ancestor relationships in a growing tree and maintaining a tree structured environment (context tree).

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: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 3: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 4: David Maier. An Efficient Method For Storing Ancestor Information In Trees. SIAM J. Comput. 8(4):599-618, November 1979.
• 5: Carlo Montangero, Giuliano Pacini, Maria Simi, and Franco Turini. Information Management in Context Trees. Acta Informatica 10:85-94, 1978.
• 6: Ben Wegbreit. Retrieval from Context Trees. Information Processing Letters 3(4):119-120, March 1975.
• 7: Ben Wegbreit, Faster retrieval from context trees, Communications of the ACM, v.19 n.9, p.526-529, Sept. 1976 [doi>10.1145/360336.360347]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees; Lists, stacks, and queues

General Terms:
Algorithms