Brian: Created page with "A '''data structure''' or '''container''' is a scheme for organizing data in memory (such as random-access memory, a hard disk, or across the hard disks of a network of data serv..."

2011-03-20T02:06:17Z

Created page with "A '''data structure''' or '''container''' is a scheme for organizing data in memory (such as random-access memory, a hard disk, or across the hard disks of a network of data serv..."

New page

A '''data structure''' or '''container''' is a scheme for organizing data in memory (such as random-access memory, a hard disk, or across the hard disks of a network of data servers). Data structures are designed with efficiency and compactness in mind; that is, the best data structures are the ones that do not use very much more space than is taken up by the raw data themselves, and allow the data to be efficiently operated upon. Nearly all [[high-level programming language]]s have built-in support for some data structures; for example, [[imperative programming languages]] usually have built-in support for the [[array]], [[functional programming languages]] usually have built-in support for the [[Linked list|singly linked list]], and [[stack-based programming languages]], as the name implies, automatically organize all data onto a [[stack]].

Data structures are always used in conjunction with [[algorithm]]s; the algorithm determines ''what'' to do with data, and the data structure determines ''how'' this is done. For this reason, algorithms and data structures form the foundation of computer science. Choosing appropriate data structures for the implementation of an algorithm can greatly boost the algorithm's efficiency.

==Anatomy==
Strictly speaking, the ''data structure'' consists of two parts: the ''interface'' and the ''implementation'', although the latter is what is usually being referred to when the term ''data structure'' is used, because it is often highly nontrivial in comparison to the former. In short, the interface is the ''outside'' of an algorithm, whereas the implementation is the ''inside''.

===Interface===
The ''interface'' is the means by which a data structure may be operated on; the set of all operations that a data structure directly allows. For example, a [[stack]] allows an element to be pushed onto the top or removed from the top; these two operations are part of the stack's interface. A stack does ''not'' allow us to peek at the fifth element from the top without disturbing the elements above it, therefore this is ''not'' part of the interface. A stack allows us to pop ''two'' elements from the top, but this is probably not part of the interface either, because as long as the stack provides the means to pop ''one'' element in its interface, we can simply do this twice to achieve the desired effect. Knowing the interface of a data structure is knowing enough information to incorporate the data structure into a larger data structure or into an algorithm.

===Implementation===
At some level, a data structure must actually ''do'' what its interface tells us it does. The means by which this is accomplished is known as the ''implementation''. The implementation consists of the details concerning how the data are in fact organized in memory and what happens to them when an operation from the interface is executed. It consists of the details of what algorithms are used to operate on the data and what smaller data structures, if any, are incorporated into a given data structure. The bulk of the code associated with a data structure is usually implementation. For example, we can implement a [[stack]] by equipping an extensible [[array]] with a push and pop operation, where pushing adds an element on the end and popping removes one. We could also equip a [[linked list]] with the same operations; all the data are still there, but they are stored differently in memory. A third implementation would be to take a [[deque]] and restrict its interface, providing only the abilities to push and pop at the end. The implementation of a data structure can affect the efficiency of the algorithm that uses it, but does not affect its behavior.

===Abstract data type===
If all we know about a data structure is its interface, it is said to be an ''abstract data type''. For example, many programming languages' standard libraries contain ''[[associative array]]s'' or ''dictionaries'', which generalize the concept of arrays by allowing any [[Partial order|totally ordered]] types as indices. There are many ways of implementing these, such as by [[binary search tree]]s, [[hash table]]s, or [[skip list]]s, but the language standard usually does not specify ''which one'', and the programmer who uses the library has no need to know which implementation is used. Hence the associative array is said to be an abstract data type.

===Analogy===
A secretary's desk and filing cabinets can be considered a data structure. The desk is the interface; here you can ask the secretary to add a file to the records, or to retrieve a file that already exists in the records. The filing cabinet is the implementation; it is where the data are actually stored, neatly alphabetized and sorted. If a company places an ad in the papers, seeking a new secretary, the company is, in effect, advertising for an abstract data type; they need the tasks of storing and retrieving files (among others) to be performed, but do not specify which files should go in which drawers and the like. (In this example, the secretary himself/herself corresponds to the CPU.)

==Properties==
A data structure is said to be '''immutable''' if it is not possible to modify it after it has been created; in order to be useful, an immutable data structure must be fed all the data it is to contain at the time of its creation, and if we wish to add, remove, or replace the data it contains, we must actually use it to create a new data structure of the same type that is identical except for the modifications we wish to make. An example is the <code>String</code> in [[Java]]. A data structure that allows its content to be changed is said to be '''mutable'''. A data structure can be made immutable by simply not providing anything in the interface that would modify it, or using language-specific constructs such as a <code>const</code> declaration to block write access to what would otherwise be mutable. In a purely functional programming language such as [[Haskell]], with strict referential transparency, ''all'' data structures are immutable, whereas in [[assembly language]], whatever data structures one creates will be mutable.

A data structure is said to be '''persistent''' when, after updating it, it is still possible to retrieve or operate on previous versions of the data structure. Arrays, for example, are ''not'' persistent, because after we change an element of an array, the old value of that element is lost. We could, of course, simply take the collection of all versions a data structure has gone through to be a persistent representation of that data structure, but this will only be useful if the size of this is much less than the sum of the sizes of all the versions the data structure has gone through. (This is the case, for example, with properly implemented immutable tree data structures in which the new version shares most of its nodes with the old version.)

==Important data structures==
The following are among the most fundamental and ubiquitous abstract data types:
* '''[[String]]s''' are finite sequences of characters.
* '''[[Stack]]s''' allow items to be added and removed. When an item is removed, it is always the one most recently added.
* '''[[Queue]]s''' allow items to be added and removed. When an item is removed, it is always the remaining item added earliest.
* '''[[Deque]]s''' are generalizations of both stacks and queues; they allow addition and removal of elements at "both ends".
* '''[[Priority queue]]s''' are like queues, but the "most important" item is always the first to be removed. The "importance", or ''priority'', of an element is set when it is added.
* '''[[Symbol table|Set data structures]]''', or '''symbol tables''', maintain sets (collections of distinct items) and allow us to add an item, remove an item, or check whether an item is present.
* '''[[Associative array]]s''' or '''dictionaries''' are like sets, but two items are added at a time; the first may be used to "look up" the second.

The following are common implementations of data structures:
* '''[[Array]]s''' store a sequence of data sequentially in random-access memory.
:* '''Adjacency matrices''' are two-dimensional arrays used to represent [[graph]]s.
* '''[[Linked list]]s''' store a sequence of data in random-access memory by having each datum "link" to the next (by holding the memory address of the next item).
:* '''Adjacency lists''' are collections of sequential containers (typically arrays or linked lists) used to represent [[graph]]s.
* '''[[Tree]]s''' organize data in a hierarchial structure by assigning to all data but one, the ''root'', a parent.
:* '''[[Binary search tree]]s''' are trees in which each node has at most two children, called ''left'' and ''right'', and the value stored in a left child is always less than or equal to that stored in its parent, and the value stored in a right child is always greater than that stored in its parent. They are usually used to implement symbol tables and dictionaries.
:* '''[[Binary heap]]s''' are complete binary trees in which the value stored in each node is strictly greater than the values stored in its child nodes. They are often used to implement priority queues.
:* '''[[Trie]]s''' or '''prefix trees''' are trees used to contain sets of strings.

[[Category:Data structures]]

Data structure - Revision history

Brian: Created page with "A '''data structure''' or '''container''' is a scheme for organizing data in memory (such as random-access memory, a hard disk, or across the hard disks of a network of data serv..."