Maintaining order in a generalized linked list
Copyright policy )Maintaining order in a generalized linked list
We give a representation for linked lists which allows to efficiently insert and delete objects in the list and to quickly determine the order of two list elements. The basic data structure, called an indexed BB[α]-tree, allows to do n insertions and deletions in O(n log n) steps and determine the order in constant time, assuming that the locations of the elements worked at are given. The improved algorithm does n insertions, deletions and comparisons in O(n log* n) steps.
- Saarland University Germany
Complexity of proofs, dynamic tree structure, algorithm, Analysis of algorithms and problem complexity, insertions, deletions, linked lists, basic data structure
Complexity of proofs, dynamic tree structure, algorithm, Analysis of algorithms and problem complexity, insertions, deletions, linked lists, basic data structure
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).43 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!