List of data structures

This is a list of well-known data structures. For a comparison of running times for a subset of this list see comparison of data structures.

Data types

Primitive types

Boolean, true or false.
Character
Floating-point representation of a finite subset of the rationals.
- Including single-precision and double-precision IEEE 754 floats, among others
Fixed-point representation of the rationals
Integer, a direct representation of either the integers or the non-negative integers
Reference, sometimes erroneously referred to as a pointer or handle, is a value that refers to another value, possibly including itself
Symbol, a unique identifier
Enumerated type, a set of symbols
Complex, representation of complex numbers

Composite types or non-primitive type

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

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

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

Lists

Doubly linked list
Array list
Linked list also known as a Singly linked list
Association list
Self-organizing list
Skip list
Unrolled linked list
VList
Conc-tree list
Xor linked list
Zipper
Doubly connected edge list also known as half-edge
Difference list
Free list

Trees

Trees are a subset of directed acyclic graphs.

B-trees

Bit-slice trees

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

Multi-way trees

Space-partitioning trees

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

Application-specific trees

Hash-based structures

Graphs

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

Other

External links

Tommy Benchmarks Comparison of several data structures.

v t e Data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Rope Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

This page was redesigned at the edge.

A page that knows where it met you.