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.[1][2][3] 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.[4] Contents 1 Usage 2 Implementation 3 Examples 4 Language support 5 See also 6 References 7 Bibliography 8 Further reading 9 External links Usage[edit]
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.[citation needed]
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.[citation needed] In addition, graphs and binary trees are other commonly used data
structures.
Language support[edit]
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
arrays.[7][8]
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++
Standard
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 References[edit] ^ 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
http://xlinux.nist.gov/dads/HTML/datastructur.html.
^
Bibliography[edit] 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. Further reading[edit] 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
External links[edit] 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 Data structures Types Collection Container Abstract Associative array Multimap List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set Arrays
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 Trie Hash tree Graphs Binary decision diagram Directed acyclic graph Directed acyclic word graph List of data structures v t e Data types Uninterpreted Bit
Byte
Trit
Tryte
Word
Numeric 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 Integer signedness Interval Rational Pointer Address physical virtual Reference Text Character String null-terminated Composite Algebraic data type generalized Array Associative array Class Dependent Equality Inductive List Object metaobject Option type Product Record Set Union tagged Other Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void Related topics Abstract data type Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Protocol interface Subtyping Type constructor Type conversion Type system Type theory See also platform-dependent and independent units of information v t e Data model Main Architecture Modeling Structure Schemas Conceptual Logical Physical Types Database
Related models Data flow diagram Information model Object model Object-role modeling Unified Modeling Language See also
Authority control GND: 40111 |