Problem Detail: Can data structures be thought of as algorithms themselves? For example, I could implement a stack data structure that has certain non-functional characteristics. Is the separation between data structures and algorithms formally defined?
Asked By : Ben Aston
Answered By : D.W.
Yes, a data structure can be thought of as an algorithm. A data structure is a collection of state together with one or more algorithms that operate on that state. A data structure can be thought of as a tuple $(s,f_1,f_2,dots,f_k)$ where $s$ is its state, and each $f_i$ is an operation that can be performed on the data structure; the operation $f_i$ can read the state $s$ and its input parameters, and possibly modifies $s$ and possibly returns a new value. Alternatively, from an object-oriented viewpoint, you can think of a data structure as an object; $s$ is the state of the object, and $f_1,dots,f_k$ are the methods that can be invoked on the object. Normally, $f_1,dots,f_k$ are described as algorithms that operate on $s$ and their inputs. This lets you use the language and concepts of algorithms to analyze various data structures. I’m not sure there is a formal specification of what counts as a data structure, but this seems to get about close as I’ve seen. You might be interested in the notion of abstract data type (ADT) from programming languages. You can think of a data structure as an ADT, or more carefully, you can think of an ADT as the specification and the data structure code as a particular implementation of that ADT. When people talk about data structures informally, they don’t always distinguish between specification vs implementation; the term ADT helps make that distinction more precise. I don’t know if people normally try to formally define what we mean by “data structure”; it’s a loose term that is more useful to illustrate a particular type of concept in computer science. If I wanted to make it as precise as possible, the notion of an ADT would probably be the first formalization I’d consider. An ADT is like an interface specification, and a specific data structure is like a particular way of implementing that specification.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49056