Choosing a data structure - racket/racket GitHub Wiki
The most fundamental data structures in Rackets are lists, vectors, structs, and hash tables. These can in turn be used to build other, more elaborate data structures.
data structure | access | size | indices |
---|---|---|---|
list | sequential | variable | not used |
vector | random | fixed | integer |
struct | random | fixed | name |
hash table | random | variable | hashable |
growable vector | random | variable | integer |
splay | random | variable | total order |
Important takeaways:
- List referencing
(list-ref xs n)
takes time proportional to O(n). - Vector referencing
(vector-ref xs n)
takes constant time
Notes:
- A Racket
list
is often known as singly-linked list. - A Racket
vector
is often called an array in other languages - A
splay
tree is a self-adjusting binary tree
See also Notes on data structures in Racket, with some performance considerations.