Backing up in singly linked lists
Amir M. Ben-Amram, Holger Petersen · 1999
two-way movement in the input, nor tables or other types of auxiliary memory are available.We show how to reduce the time overhead for backingThe main result of this paper is a method for reducup in a singly linked list to O(n') per operation for any ing the time overhead for backing up in a linear list.e > 0 without modifying the list and without making More specifically for every E > 0 the time complexity use of storage other than a finite number of pointers into of backing up by one position in a singly linked list the list.We also prove a matching lower bound.Our of length n can be reduced to 0(n<).There are some results add precision to the intuitive feeling that doubly preparatory operations that take linear time, but since linked lists are more efficient than singly linked lists, merely inspecting the input takes linear time, the worst and quantify the efficiency gap in a read-only situation.case complexity of any reasonable program will not suf-As an application, our upper bound implies that readfer from these operations.We will therefore assume only programs can do string matching much faster than throughout this paper that the time complexity of all previously expected.programs to be simulated is at least linear.