3.35 One way to implement a queue is to use a circular linked list. In a circular linked list, the last node's next link links to the first node. Assume the list does not contain a header and that we can maintain, at most, one iterator corresponding to a node in the list. For which of the following representations can all basic queue operations be performed in constant worst-case time? Justify your answers. a. Maintain an iterator that corresponds to the first item in the list. Sol: Does not work in constant time for insertions at the end. b. Maintain an iterator that corresponds to the last item in the list. Sol: Because of the circularity, we can access the front item in constant time, so this works. | |
| View Solution | |
| << Back | Next >> |