Jump to content

List of data structures: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
→Other: Add e-graph
Tags: Mobile edit Mobile web edit
 
(18 intermediate revisions by 15 users not shown)
Line 8: Line 8:
*[[Boolean data type|Boolean]], [[Truth value|true]] or [[false (logic)|false]].
*[[Boolean data type|Boolean]], [[Truth value|true]] or [[false (logic)|false]].
*[[Character (computing)|Character]]
*[[Character (computing)|Character]]
*[[Floating-point arithmetic|Floating-point]] numbers, limited-precision approximations of [[real number]] values.
*[[Floating-point arithmetic|Floating-point]] representation of a finite subset of the [[rationals]].
** Including [[single-precision floating-point format|single-precision]] and [[double-precision floating-point format|double-precision]] [[IEEE 754]] floats, among [[:Category:Floating point types|others]]
** Including [[single-precision floating-point format|single-precision]] and [[double-precision floating-point format|double-precision]] [[IEEE 754]] floats, among [[:Category:Floating point types|others]]
*[[Fixed-point arithmetic|Fixed-point numbers]]
*[[Fixed-point arithmetic|Fixed-point]] representation of the rationals
*[[Integer (computer science)|Integer]], integral or fixed-precision values
*[[Integer (computer science)|Integer]], a direct representation of either the [[Integer|integers]] or the [[non-negative integers]]
*[[Reference (computer science)|Reference]] (also called a [[Pointer (computer programming)|pointer]] or handle), a small value referring to another object's address in memory, possibly a much larger one
*[[Reference (computer science)|Reference]], sometimes erroneously referred to as a [[Pointer (computer programming)|pointer]] or handle, is a value that refers to another value, possibly including itself
*[[Symbol (programming)|Symbol]], a unique identifier
*[[Enumerated type]], a small [[set (mathematics)|set]] of uniquely named values
*[[Enumerated type]], a [[set (mathematics)|set]] of symbols
*[[Complex data type|Complex]], representation of [[complex numbers]]


=== Composite types or non-primitive type ===
=== Composite types or non-primitive type ===
{{main|Composite type}}
{{main|Composite type}}
*[[Array (data structure)|Array]], a sequence of elements of the same type stored contiguously in memory
*[[Array (data type)|Array]], a sequence of elements of the same type stored contiguously in memory
*[[Record (computer science)|Record]] (also called a structure or [[struct (C programming language)|struct]]), a collection of fields
*[[Record (computer science)|Record]] (also called a structure or [[struct (C programming language)|struct]]), a collection of fields
**[[Product type]] (also called a tuple), a record in which the fields are not named
**[[Product type]] (also called a tuple), a record in which the fields are not named
Line 74: Line 76:
|}
|}


"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.
"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 algorithm|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 ==
== Linear data structures ==
Line 81: Line 83:
=== Arrays ===
=== Arrays ===
*[[Array data structure|Array]]
*[[Array data structure|Array]]
*[[Associative array]]
*[[Bit array]]
*[[Bit array]]
*[[Bit field]]
*[[Bit field]]
Line 250: Line 253:
*[[Expression tree]]
*[[Expression tree]]
*[[Log-structured merge-tree]]
*[[Log-structured merge-tree]]
*[[PQ tree]]


== {{Anchor|Hashes}}Hash-based structures ==
== {{Anchor|Hashes}}Hash-based structures ==
* [[Approximate Membership Query Filter]]
*[[Bloom filter]]
*[[Binary fuse filter]]
**[[Bloom filter]]
*[[Cuckoo filter]]
**[[Cuckoo filter]]
*[[Xor filter]]
**[[Quotient filter]]
*[[Count–min sketch]]
*[[Count–min sketch]]
*[[Distributed hash table]]
*[[Distributed hash table]]
Line 269: Line 273:
*[[Rolling hash]]
*[[Rolling hash]]
*[[MinHash]]
*[[MinHash]]
*[[Quotient filter]]
*[[Ctrie]]
*[[Ctrie]]


Line 303: Line 306:
* [[Purely functional data structure]]
* [[Purely functional data structure]]
* [[Blockchain]], a hash-based chained data structure that can persist state history over time
* [[Blockchain]], a hash-based chained data structure that can persist state history over time

⚫
{{Data structures}}


==External links==
==External links==
*[http://tommyds.sourceforge.net/doc/benchmark.html Tommy Benchmarks] Comparison of several data structures.
*[http://tommyds.sourceforge.net/doc/benchmark.html Tommy Benchmarks] Comparison of several data structures.

⚫
{{Data structures}}


[[Category:Data structures|*]]
[[Category:Data structures|*]]

Latest revision as of 15:09, 9 October 2024

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]
Main article: Primitive type

Composite types or non-primitive type

[edit]
Main article: Composite 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

[edit]
Main article: Abstract data type

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]
Main article: Tree (data structure)

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]
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=List_of_data_structures&oldid=1250290565"