Use a doubly linked list, store both physical endpoints and its length, and maintain a flag for lazy reversal of a doubly linked list. This makes endpoint insertion and reversal constant time. Finding an arbitrary indexed element takes a traversal from whichever physical endpoint is nearer.
class LLBuffer extends ReversableBuffer {
  private class Node(val value: Int) {
    var prev: Node = null
    var next: Node = null
  }
  private var first: Node = null
  private var last: Node = null
  private var size = 0
  private var backwards = false

  // Methods from (ii) go here.
}
Define to be the sequence of values obtained by starting at first and repeatedly following next until null. The representation invariant says that size is nonnegative; size == 0 holds exactly when both endpoints are null; otherwise there are exactly size distinct reachable linked list nodes, the final one is last, first.prev == null, last.next == null, and all neighboring links are reciprocal. These conditions make finite and the physical linked list acyclic. The abstraction function is
(1)
The flag does not change the representation invariant. An empty physical linked list represents the empty sequence for either flag value. No client receives a linked list node reference, so clients cannot invalidate its links.
Figure 1.
Physical doubly linked list order and logical sequence order under lazy reversal of a doubly linked list
. Details.

Ancestors (13)

  1. i
  2. b
  3. 2
  4. Imperative programming
  5. 2013
  6. Past exam of the year 1 of the computer science course of the University of Oxford
  7. Year 1 of the computer science course of the University of Oxford
  8. Computer science course of the University of Oxford
  9. Undergraduate course of the University of Oxford
  10. Course of the University of Oxford
  11. University of Oxford
  12. List of universities
  13. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version