• @[email protected]
    link
    fedilink
    2
    edit-2
    5 days ago

    I was a bit surprised that deque is implemented as a linked list and not, for example, a ring buffer. It would mean that index reads would be constant time (though insert and delete at an index would be linear time), the opposite of using a linked list.

    • Eager Eagle
      link
      English
      14 days ago

      But a ring buffer is a FIFO data structure that can be implemented using linked lists. What ring buffer implementation did you have in mind?

        • Eager Eagle
          link
          English
          04 days ago

          Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory.

          • @[email protected]
            link
            fedilink
            13 days ago

            No that’s a subtly different thing. The storage is a contiguous vector, but because it is a ring buffer there must be one pair of adjacent elements that are not contiguous in memory. That’s what that comment is saying.

            But because it is only one discontinuity it doesn’t affect algorithmic complexity, so it is still O(1) to access elements, unlike a linked list which is O(N).

            If you google “circular buffer” there will be loads of diagrams that make it really obvious how it works.