This is a list of well-knowndata structures. For a wider list of terms, seelist of terms relating to algorithms and data structures. For a comparison ofrunning times for a subset of this list seecomparison of data structures.
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 assorting 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.
A data structure is said to be linear if its elements form a sequence.
Trees are a subset ofdirected acyclic graphs.
In these data structures each tree node compares a bit slice of key values.
These are data structures used forspace partitioning orbinary space partitioning.
Manygraph-based data structures are used in computer science and related fields: