A data structure in computer science is a way of storing data
in a computer so that it can be used efficiently. It is an organization
of mathematical and logical concepts of data. Often a carefully chosen
data structure will allow the most
efficient algorithm
to be used. The choice of the data structure often begins from the
choice of an abstract data type. A well-designed data structure allows
a variety of critical operations to be performed, using as few
resources, both execution time and memory space, as possible. Data
structures are implemented by a
programming language as data types and the
references and operations they provide.
Different kinds of data structures are suited to different kinds of
applications, and some are highly specialized to certain tasks. For
example,
B-trees are particularly well-suited for implementation of databases, while networks of machines rely on routing tables to function.
In the design of many types of computer program, the choice of data
structures is a primary design consideration. Experience in building
large systems has shown that the difficulty of implementation and the
quality and performance of the final result depends heavily on choosing
the best data structure. After the data structures are chosen, the
algorithms to be used often become relatively obvious. Sometimes things
work in the opposite direction — data structures are chosen because
certain key tasks have algorithms that work best with particular data
structures. In either case, the choice of appropriate data structures
is crucial.
This insight has given rise to many formalized design methods and
programming languages in which data structures, rather than algorithms,
are the key organizing factor. Most languages feature some sort of
module system, allowing data structures to be safely reused in
different applications by hiding their verified implementation details
behind controlled interfaces.
Object-oriented programming languages such as C++ and
Java in particular use
classes for this purpose.
Since data structures are so crucial, many of them are included in standard libraries of modern programming languages and
APIs, such as C++'s
containers, the
Java Collections Framework, and the Microsoft
.NET Framework.
The fundamental building blocks of most data structures are arrays,
records,
discriminated unions, and
references.
For example, the nullable reference, a reference which can be null, is
a combination of references and discriminated unions, and the simplest
linked data structure, the linked list, is built from records and
nullable references.
Data structures represent implementations or
interfaces:
A data structure can be viewed as an interface between two functions or
as an implementation of methods to access storage that is organized
according to the associated data type
