Data structure

From Algorithmist
Revision as of 11:04, 20 August 2007 by Ahy1 (Talk | contribs) (revert spam)

Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

A data structure is any structure that holds data. The most common forms of data structures in real-world programming applications are "struct"s and "object"s.

Some popular data structures are:

Besides there are few more advanced data structures such as

Structs are simply collections of data with no inherent functionality, and are commonly used in the C programming language.

Objects, like structs, contain data ("properties"). However, unlike structs, objects contain functions ("methods") that allow the programmer to define different behaviours for different objects. Most modern programming languages (including C++, Python, Java, and JavaScript) make frequent and heavy use of objects.

Often a programmer wants to make sure some "invariant" of the data structure never changes. Some typical invariants are "the items in this list are sorted", or "the 'estimated distance' of each node in a graph is always greater than or equal to the true distance", or "the number of descendents of every internal node in a 2-3 tree is always 2 or 3", or "At any one time, the distance from any one leaf to the root of a 2-3 tree is the same for every leaf of that tree".

Rather than carefully manually analyzing every part of a program to make sure "maintains the invariant" ("properly modifies the data structure"), a programmer can automatically guarantee that the entire program maintains the invariant by ... into objects, and ..., and then ... and ..., and then tell the compiler to "warn" the programmer if any other part of the program tries to access that object.

Typically, a method can "temporarily" break an invariant, as long as the invariant is restored by the time each method finishes. (Certain kinds of "re-entrant", "interruptable", and "parallel processing" applications have the additional restriction that the implementation must preserve invariants at every instant that the method could ever be interrupted by any other routine that might possibly read the data structure. It was long thought that Wiki:WaitFreeSynchronization was impossible ).

Programmers distinguish a "class" (which is sort of like the blueprints for a bookshelf), an "object" (which is like a specific bookshelf in a specific location built using some particular set of blueprints), and the "state" of the object (the data contained in the object at one particular moment, like the particular books in a bookshelf at one particular moment).

Programmers also distinguish between code that "implements" a class, code that "uses" a class, and the "interface" between them.

Modern development environments provide well-tested implementations of many popular data structures that you may choose to use. Even if a particular data structure did not come with the particular development environment you are using, you may find someone has already written an implementation and is willing to give you a copy for a nominal price or for free.