In computer science, a data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
1 Usage 2 Implementation 3 Examples 4 Language support 5 See also 6 References 7 Bibliography 8 Further reading 9 External links
Data structures can implement one or more particular abstract data
types (ADT), which specify the operations that can be performed on a
data structure and the computational complexity of those operations.
In comparison, a data structure is a concrete implementation of the
space provided by an ADT.
Different kinds of data structures are suited to different kinds of
applications, and some are highly specialized to specific tasks. For
example, relational databases commonly use
An array is a number of elements in a specific order, typically all of the same type. Elements are accessed using an integer index to specify which element is required (Depending on the language, individual elements may either all be forced to be the same type, or may be of almost any type). Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed-length or resizable. A linked list (also just called list) is a linear collection of data elements of any type, called nodes, where each node has itself a value, and points to the next node in the linked list. The principal advantage of a linked list over an array, is that values can always be efficiently inserted and removed without relocating the rest of the list. Certain other operations, such as random access to a certain element, are however slower on lists than on arrays. A record (also called tuple or struct) is an aggregate data structure. A record is a value that contains other values, typically in fixed number and sequence and typically indexed by names. The elements of records are usually called fields or members. A union is a data structure that specifies which of a number of permitted primitive types may be stored in its instances, e.g. float or long integer. Contrast with a record, which could be defined to contain a float and an integer; whereas in a union, there is only one value at a time. Enough space is allocated to contain the widest member datatype. A tagged union (also called variant, variant record, discriminated union, or disjoint union) contains an additional field indicating its current type, for enhanced type safety. A class is a data structure that contains data fields, like a record, as well as various methods which operate on the contents of the record. In the context of object-oriented programming, records are known as plain old data structures to distinguish them from classes.
In addition, graphs and binary trees are other commonly used data
Most assembly languages and some low-level languages, such as BCPL
(Basic Combined Programming Language), lack built-in support for data
structures. On the other hand, many high-level programming languages
and some higher-level assembly languages, such as MASM, have special
syntax or other built-in support for certain data structures, such as
records and arrays. For example, the C (a direct descendant of BCPL)
and Pascal languages support structs and records, respectively, in
addition to vectors (one-dimensional arrays) and multi-dimensional
Most programming languages feature some sort of library mechanism that
allows data structure implementations to be reused by different
programs. Modern languages usually come with standard libraries that
implement the most common data structures. Examples are the C++
Book: Data structures
Abstract data type Concurrent data structure Data model Dynamization Linked data structure List of data structures Persistent data structure Plain old data structure
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein,
Clifford (2009). Introduction to Algorithms, Third Edition (3rd ed.).
The MIT Press. ISBN 0262033844.
^ Black (ed.), Paul E. (2004-12-15). Entry for data structure in
Dictionary of Algorithms and Data Structures. Online version. U.S.
National Institute of Standards and Technology, 15 December 2004.
Retrieved on 2009-05-21 from
This article lacks ISBNs for the books listed in it. Please make it easier to conduct research by listing ISBNs. If the Cite book or citation templates are in use, you may add ISBNs automatically, or discuss this issue on the talk page. (September 2016)
Peter Brass, Advanced Data Structures, Cambridge University Press, 2008, ISBN 978-0521880374 Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley, 3rd edition, 1997, ISBN 978-0201896831 Dinesh Mehta and Sartaj Sahni, Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 2007. Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1985.
Alfred Aho, John Hopcroft, and Jeffrey Ullman, Data Structures and
Algorithms, Addison-Wesley, 1983, ISBN 0-201-00023-7
G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data
Structures - in Pascal and C, second edition, Addison-Wesley, 1991,
ISBN 0-201-41607-7 Book
Find more aboutData structureat's sister projects
Definitions from Wiktionary Media from Wikimedia Commons Quotations from Wikiquote Texts from Wikisource Textbooks from Wikibooks Learning resources from Wikiversity
Descriptions from the Dictionary of Algorithms and Data Structures
Data structures course
An Examination of Data Structures from .NET perspective
Schaffer, C. Data Structures and
v t e
List Stack Queue
Double-ended priority queue
Association list Linked list Skip list Unrolled linked list XOR linked list
B-tree Binary search tree
AA tree AVL tree Red–black tree Self-balancing tree Splay tree
Binary heap Binomial heap Fibonacci heap
R* tree R+ tree Hilbert R-tree
Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures
v t e
Arbitrary-precision or bignum Complex Decimal Fixed point Floating point
Double precision Extended precision Half precision Long double Minifloat Octuple precision Quadruple precision Single precision
Algebraic data type
Array Associative array Class Dependent Equality Inductive List Object
Option type Product Record Set Union
Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void
Abstract data type Data structure Generic Kind
Parametric polymorphism Primitive data type Protocol
Subtyping Type constructor Type conversion Type system Type theory
See also platform-dependent and independent units of information
v t e
Architecture Modeling Structure
Conceptual Logical Physical
Data flow diagram Information model Object model Object-role modeling Unified Modeling Language