6.5. Exercises

6.5.1. Exercise 1

Implement a queue data structure, which does not use OCaml arrays or double-linked lists, and at most two values of type ref. Make sure it satisfies the Queue interface. To do so, use two OCaml lists to represent the part for “enqueueing” and “dequeueing”. What happens if one of them gets empty? Argue that the average-case complexity for enqueue and dequeue operations of your implementation is linear.

6.5.2. Exercise 2

Implement a procedure for “reversing” a doubly-linked list, starting from its arbitrary node (which might be at its beginning, end, or in the middle). Make sure that your procedure works in linear time.