Name
Abstract | ||
|---|---|---|
We show how to reduce the time overhead for implementing two-way movement on a singly linked list to O(nε) per operation without modifying the list and without making use of storage other than a finite number of pointers into the list. We also prove a matching lower bound.These results add precision to the intuitive feeling that doubly linked lists are more efficient than singly linked lists, and quantify the efficiency gap in a read-only situation. We further analyze the number of points of access into the list (pointers) necessary for obtaining a desired value of ε. We obtain tight tradeoffs which also separate the amortized and worst-case settings.Our upper bound implies that read-only programs with singly-linked input can do string matching much faster than previously expected. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1145/1162349.1162353 | J. ACM |
Keywords | DocType | Volume |
intuitive feeling,efficiency gap,tight tradeoffs,two-way movement,string matching,finite number,incompressibility,worst-case setting,two way automata,read-only program,singly-linked input,read-only situation,time overhead | Conference | 53 |
Issue | ISSN | ISBN |
4 | 0004-5411 | 1-58113-067-8 |
Citations | PageRank | References |
6 | 0.51 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amir M Ben-Amram | 1 | 327 | 30.52 |
| Holger Petersen | 2 | 6 | 0.51 |