Vector - sellout/data-structure-zoo GitHub Wiki

This is a mutable data structure, sometimes called an β€œarray” (which is too overloaded a term to use in this zoo) that can be used to implement a sequence or maybe a random-access list if you don’t care about some of the stack operations too much.

  • [index](/sellout/data-structure-zoo/wiki/index) – O(1)
  • [peek front](/sellout/data-structure-zoo/wiki/peek-front) – O(1) – this is simply [index](/sellout/data-structure-zoo/wiki/index) 0 container
  • [update!](/sellout/data-structure-zoo/wiki/update!) – O(1)
  • [chop front](/sellout/data-structure-zoo/wiki/chop-front) – O(n)
  • [chop front!](/sellout/data-structure-zoo/wiki/chop-front!) – O(n)
  • [pop front!](/sellout/data-structure-zoo/wiki/pop-front!) – O(n)

In a language like C where vectors (called arrays in that context) are provided as memory pointers, [chop front](/sellout/data-structure-zoo/wiki/chop-front) can be implemented in O(1). That should probably be a separate data structure, as Common Lisp provides something similar in its displaced arrays.