*11-1
For each of the four types of linked lists in the following table,
what is the asymptotic worst-case running time for each dynamic-set
operation listed?
*

singly | singly | doubly | doubly | |

unsorted | sorted | unsorted | sorted | |

Search(L, k) | O(N) | O(N) | O(N) | O(N)- |

Insert(L, x) | O(1) | O(N) | O(1) | O(N)- |

Delete(L, x) | O(N)* | O(N)* | O(1) | O(1) |

Successor(L, x) | O(N) | O(1) | O(N) | O(1) |

Predecessor(L, x) | O(N) | O(N) | O(N) | O(1) |

Minimum(L) | O(N) | O(1) | O(N) | O(1) |

Maximum(L) | O(N) | O(1)+ | O(N) | O(1)+ |

- I need a pointer to the predecessor! (*)
- I need a pointer to the tail! (+)
- Only bottlenecks in otherwise perfect dictionary! (-)

Mon Jun 2 09:21:39 EDT 1997