Difference between revisions of "Data structure"

From Algorithmist
Jump to: navigation, search
m (Data Structures moved to Data structure: Other articles often mention "data structure" or "data structures". Make it lowercase and singular to make this easier to link to.)
(22 intermediate revisions by 10 users not shown)
Line 1: Line 1:
 
{{stub}}
 
{{stub}}
  
A '''data structure''' is any structure that holds data.  The most common forms of data structures in real-world programming applications are "<code>struct</code>"s and "<code>object</code>"s.
+
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 "''objects''"s.
  
 
Some popular data structures are:
 
Some popular data structures are:
Line 7: Line 7:
 
* [[Graph data structures]] such as:
 
* [[Graph data structures]] such as:
 
** ... such as ...
 
** ... such as ...
 +
** [[quadtree]]
 +
** [[binary space partitioning]]
 
* [[binary search tree]]
 
* [[binary search tree]]
 
* [[Linked List]]
 
* [[Linked List]]
Line 17: Line 19:
  
 
* [[Interval tree]]
 
* [[Interval tree]]
 +
* [[Segment Trees]]
 
* [[Fenwick tree]]
 
* [[Fenwick tree]]
 
* [[disjoint data structures]]
 
* [[disjoint data structures]]
 
* [[binary heaps]]
 
* [[binary heaps]]
 +
* [[binomial heaps]]
 +
* [[fibonacci heaps]]
 
* [[skip list]]
 
* [[skip list]]
 
* [[circular queue]]
 
* [[circular queue]]
Line 26: Line 31:
 
* [[AVL tree]]
 
* [[AVL tree]]
 
* [[red-black tree]]
 
* [[red-black tree]]
 +
* [[rope]] [http://en.wikipedia.org/wiki/Rope_(computer_science)]
 +
 +
Moreover there are data structures to minimize the disk access time .
 +
* [[B-trees]]
 +
* [[B+ trees]]
 +
* [[k-d trees]]
  
  
Line 48: Line 59:
 
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.
 
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.
  
----
+
 
 +
 
 +
[[Category:Data Structure]]

Revision as of 17:46, 18 May 2009

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 "objects"s.

Some popular data structures are:

Besides there are few more advanced data structures such as

Moreover there are data structures to minimize the disk access time .


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.