An aspect of data type expressing the nature of values that are composite, i.e. not atoms. The nonatomic values have constituent parts (which need not themselves be atoms), and the data structure expresses how constituents may be combined to form a compound value or selected from a compound value. Thus “date” regarded as a data structure is a set containing a member for every possible day, combined with operations to construct a date from its constituents — year, month, and day — and to select a desired constituent.
An implementation of a data structure involves both choosing a storage structure and providing a set of procedures/functions that implement the appropriate operations using the chosen storage structure. Formally, a data structure is defined as a distinguished domain in an abstract data type that specifies the structure. Computer solution of a real-world problem involves designing some ideal data structures, and then mapping these onto available data structures (e.g. arrays, records, lists, queues, and trees) for the implementation.
Note that terms for data structures are used to denote both the structure and data having that structure.
See also dynamic data structure, static data structure.