List of data structures

This is a list of well-known data structures. For a wider list of terms, see list of terms relating to algorithms and data structures. For a comparison of running times for a subset of this list see comparison of data structures.

Data types

edit

Primitive types

edit

Composite types or non-primitive type

edit
  • Array, a sequence of elements of the same type stored contiguously in memory
  • Record (also called a structure or struct), a collection of fields
    • Product type (also called a tuple), a record in which the fields are not named
  • String, a sequence of characters representing text
  • Union, a datum which may be one of a set of types
  • Tagged union (also called a variant, discriminated union or sum type), a union with a tag specifying which type the data is

Abstract data types

edit

Some properties of abstract data types:

Structure Ordered? Uniqueness?
List yes no
Associative array no keys (indexes) only
Set no yes
Stack yes no
Multimap no no
Multiset (bag) no no
Queue yes no

"Ordered" means that the elements of the data type have some kind of explicit order to them, where an element can be considered "before" or "after" another element. This order is usually determined by the order in which the elements are added to the structure, but the elements can be rearranged in some contexts, such as sorting a list. For a structure that isn't ordered, on the other hand, no assumptions can be made about the ordering of the elements (although a physical implementation of these data types will often apply some kind of arbitrary ordering). "Uniqueness" means that duplicate elements are not allowed. Depending on the implementation of the data type, attempting to add a duplicate element may either be ignored, overwrite the existing element, or raise an error. The detection for duplicates is based on some inbuilt (or alternatively, user-defined) rule for comparing elements.

Linear data structures

edit

A data structure is said to be linear if its elements form a sequence.

Arrays

edit

Lists

edit

Trees

edit

Trees are a subset of directed acyclic graphs.

Binary trees

edit

B-trees

edit

Heaps

edit

Bit-slice trees

edit

In these data structures each tree node compares a bit slice of key values.

Multi-way trees

edit

Space-partitioning trees

edit

These are data structures used for space partitioning or binary space partitioning.

Application-specific trees

edit

Hash-based structures

edit

Graphs

edit

Many graph-based data structures are used in computer science and related fields:

Other

edit

See also

edit
edit