wiki:DataStructures

Version 4 (modified by schiptsov, 9 years ago) ( diff )

--

To keep it simple, we can think of data structures in terms of its shape. There are

  • list - a sequence of the values of the same type (an array or vector) or of any type (a dynamic list or a fixed set)
  • table - of the values of the same type (matrix or multi-dimensional array) or of mixed types an associative list (alist) or an associative array or a hash table.
  • tree - trees of any kind, such as binary trees, binary-search trees, red-black trees, etc.
  • net - a graph or a network with any kind connections between its nodes.

They all are abstract data types, because deep down there is nothing but pointers and numbers.

We should use annotations for the compiler to choice appropriate built-in primitives and hardware-supported types of values.

cons: a pair of pointers - the basic building block

(a . b)

list: a sequence (could be annotated as a set, one-dimension array, etc)

(1 "two" 3 (4 5))

(1 . ("two" . (3 . (4 . ((5 . nil) nil))))

vecror: an array with a shape, which is a set of pointers.

((1)
 (2)
 (3))

matrix: multi-dimension array which is actually just a bunch of pointers to chunks of memory of the same size

((1 2 3)
 (3 4 5)
 (6 7 8))

associative array: two linked sets of pointers

(("a" . 1)
 ("b" . 2)
 ("c" . '(1 2 3)))

hash table: set of slots plus a hash-function to produce an offset in the index.

(("apple" . 1)
 ("orange" . 2)
 ("grapes" . 3))

a table could be "called" by sending a message to it: (t "orange") => 2

Note: See TracWiki for help on using the wiki.