Data structure

Where values are stored and how they are connected affect the operations available to a program. Arrays, lists, trees, and dictionaries organize information differently. Auxiliary information, such as sizes or indexes, consumes storage but can avoid repeatedly reconstructing relationships whenever the program performs an operation on its data.

References: [1]

An abstract data type specifies operations, while a data structure supplies a representation for implementing them. Arrays and linked nodes can both implement a first-in, first-out queue. Sharing an interface does not give the implementations identical insertion, removal, or resizing costs, so behavior and representation should be discussed separately.

References: [2]

Ordering, links, and the relationship between an index and its contents are properties operations must preserve. An insertion that changes data but leaves an auxiliary count incorrect can break later work. A data structure is consequently more than a static layout: it includes rules for keeping that layout valid after updates.

References: [1]

A representation good for random access may be less suitable for frequent insertion, and an in-memory design may not suit disk-resident collections. Locality and the proportion of different operations also matter. There is no workload-independent best structure; useful comparisons evaluate representations together with the algorithms and access patterns they support.

References: [2]