Generalized data structure

Question

Data structures are seen as important, equal to algorithms. This view is especially encouraged in situations, where appropriate data structure is the main factor that allows an algorithm to exist and to perform at satisfying complexity.

However, despite the additional features of data structures (e.g. organization, like in trees storing entries according to less-like relation), all that data structures do is keeping information unchanged between algorithm's actions. Can this generic feature of data structures be izolated and defined in abstract way?

Answer 1

Notice that a data structure stores more than just it's accessible elements. This is probably what mean by additional feature, but I would consider it the essential feature. Take for example a binary search tree. This tree stores information on the order of its elements. In particular, by a traversal you can output the sorted sequence of elements stored in the tree in linear time. There are roughly $\Theta(4^n)$ different full binary trees with $n$ leaves. Thus the data structure stores roughly $2n$ additional bits in this case.

Maybe this view helps. Some algorithmic problems are one-shot problems. So you take the input, process it, and then (hopefully) output the solution. Other problems, however, are trying to solve several problems for which part of the input is mostly the same. Here it might pay off to preprocess the static input (the data), such that further requests are easier to answer. The result of the preprocessing is stored (often in form of a labeled graph). This is what you do, when you store data in a data structure.

The above paragraph explained how static data structure behave. Usually data structures are dynamic, allowing you to alter the represented data and its associated information.

Answer 2

I will add an answer for different aspect: How is an ADT(Abstract Data Type) different from an abstract type?

An ADT has:

1. Storage of elements of the same type
2. Limited interface - operations for storing and retrieving elements from the data structure
3. Inner processing - automatic operations that are executed upon the elements of the data structure
4. The structure is optimized in time/space complexity and/or "optimized" in usage complexity

The generic data feature of ADTs, besides the storing and interface operations of adding/getting elements, is the (optimized) automatic inner processing of the elements. In concrete implementations this feature results in additional memory/time. This feature is used to simplify algorithms that need such a processing and a storage of same type elements.