Data structure is a data organization, management, and storage format that enables efficient access and modification.
Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer—a bit string, representing a memory address, that can be itself stored in memory and manipulated by the program.
Thus, the array and record data structures are based on computing the addresses of data items with arithmetic operations, while the linked data structures are based on storing addresses of data items within the structure itself.
Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type.
Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, relational databases commonly use B-tree indexes for data retrieval, while compiler implementations usually use hash tables to look up identifiers.
Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms.
There are numerous types of data structures, generally built upon simpler primitive data types:
- Byte is the smallest amount of data that a Computer CPU can copy from memory to a register or back in a single instruction
- Array is a number of elements in a specific order, typically all of the same type (depending on the language, individual elements may either all be forced to be the same type, or may be of almost any type).
- Linked 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.
- Record (also called tuple or struct) is a value that contains other values, typically in fixed number and sequence and typically indexed by names.
- 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.
- Tagged union contains an additional field indicating its current type, for enhanced type safety.
- Object is a data structure that contains data fields, like a record does, as well as various methods which operate on the data contents.
In addition, hashes, graphs and binary trees are other commonly used data structures.
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 Template Library, the Java Collections Framework, and the Microsoft .NET Framework.