Backing up in singly linked lists
We show how to reduce the time overhead for implementing two-way movement on a singly linked list to O(n(epsilon)) 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 c. 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.
string matching algorithms theory incompressibility two way automata