Data structure
In computer science and software engineering, a data structure is an object for storing and organizing data. It is a structure because the data in a certain way are arranged and linked together to provide access to them and their administration efficiently.
Data structures are characterized not only by the data it contains, but also by the operations on these data, that enable and implement access and management.
Explanation
The definition (definition) of data structures is generally carried out by an exact description (specification) for the data management and of the necessary operations. This concrete specification defines the general behavior of the operations and thus abstracted from the concrete implementation of the data structure.
If the focus of the observation on the concrete implementation of the operations shifted such data structure is also often spoken of an abstract data type instead of the term. The transition from the data structure to an abstract data type is not clearly defined, but depends solely on the approach from.
Most of the data structures there are in addition to their basic form many specializations that are specified specifically for completing a specific task. For B- trees are, for example as a specialization of the data structure tree especially well for implementations of databases.
In many algorithms, the resource requirements, ie, both the required running time and the memory space required depends upon the use of appropriate data structures.
Basic data structures
The following data structures have been developed and optimized in the rule for the classical imperative programming. Other programming paradigms, such as functional programming may well require different data structures.
Record
Records (also "tuple" or English called. Record) are among the simplest data structures. They embody values that contain different values , usually in a defined number and sequence. Records identify themselves mostly by one or more of the elements contained in them, often called data field.
Array
The array (even field) is the most basic data structure used. There are hereby saved several variables of the same base data type. An access to the individual elements is possible using an index. Technically, this corresponds to the value which is added to the start address of the array in the memory to obtain the address of the object. The only necessary operations are indexed and storing the indexed read, which can directly access each element of the array. In the one-dimensional case, the array is often referred to as a vector, and in the two-dimensional case, a table or matrix. Arrays, however, are not simply restricted to two dimensions, but can be used in any multi-dimensional. Because of their simplicity and fundamental importance of the vast majority of programming languages offer a concrete implementation of this data structure as a composite data type array in the base language support.
A special case is the associative array in which does not have a numeric index, but with a key to the stored data is accessed. One possible way to implement an associative array, the hash table.
Linked list
The linked list is a data structure for the dynamic storage of an arbitrary number of objects. It includes each list element in a linked list as a special feature a reference to the next element, whereby the whole of the objects becomes a concatenation of objects. Belonging to a list operations are relatively unspecified. They are often used in more complex data structures, and takes over operations is usually accessed there for reasons of efficiency directly to their elements. The lists offered in program libraries are in their underlying data structure usually much more complex and are often not genuine lists is to give outward but as such from. Lists are always linear structures.
Stack
In a stack (English or stack, stack ') can have any number of objects are stored, but the stored objects can be read again, only in reverse order. This corresponds to the LIFO principle. For the definition and thus the specification of the stack, it is immaterial what objects are stored in it. At a stack including at least the operations
- Push to place an object on the stack and
- Pop, to read the last saved object back and remove from the stack.
- (top or peek in to check the top item without deleting it )
The top operation is not mandatory, but is often implemented to pop / push to replace, as it is often interesting to "test" the top item to. A stack is usually implemented as a list, but may also be a vector.
Queue
In a queue ( engl. queue) can have any number of objects are stored, but the stored objects can be read back only in the same order as they were saved. This corresponds to the FIFO principle. For the definition and thus the specification of the queue, it is immaterial what objects are stored in it. To a queue include at least the operations
- Enqueue to store an object in the queue and
- Dequeue to read the first stored object again and remove from the queue.
A queue is typically implemented as a linked list, but may internally use an array; In this case, the number of the elements is limited.
Priority queue
A specialization of the queue is the priority queue, which is also a priority queue or engl. Priority queue is called. It departing from the FIFO principle. The implementation of the enqueue operation, which is called in this case also insert operation, the object is sorted according to a given priority that each object with it in the priority queue. The dequeue operation always returns the object with the highest priority. Priority queues are usually implemented with heaps.
Graph
A graph makes it possible to overcome the uni-directionality of the link as a data structure. The operations are also here to insert, delete and find an object. The most common representation of graphs in the computer are the adjacency matrix, the incidence matrix and adjacency list.
Tree
Trees are special kinds of graph in the graph theory. As a data structure only out- Trees are mostly used. In this case, starting from the root of a plurality of similar objects are linked together so that the linear structure of the list is broken, and a branch occurs. Since trees are among the data structures in computer science usually used, there are many specializations.
Thus, in binary trees, the number of children and more than two in height- balanced trees is in addition to differ the heights of the left and right subtree at each node not too much.
When ordered trees, in particular search trees, the elements in the tree are stored sorted, so you can quickly find elements in the tree. We distinguish further in binary search trees with AVL trees as balanced version and B- trees as well as a variant, the B * - trees. Specializations of B- trees in turn 2-3 -4- trees, which are often implemented as a red-black tree.
Not ranked, but " nested " are geometric tree structures such as the R- tree and its variants. Here only those subtrees are searched, which overlap with the requested region.
Trees are indeed multi-dimensional in their structure but in the chain of objects often unidirectional. The concatenation of the stored objects starts at the root of the tree and from there towards the nodes of the tree.
Heap
The Heap (also heap or heaps ) combines the data structure of a tree with the operations of a priority queue. Often the heap, in addition to the minimum required operations such as insert, remove and extractMin also other operations such as merge or CHANGEKEY. Depending on the order of priority in the priority queue is a min - heap or a max-heap is used. Other specializations of the heap are the binary heap, the binomial heap and Fibonacci heap. Heaps are usually built up over the trees.
Treap
The treap combined properties of trees and heaps in itself.
Hash table
The hash table or hash value table is a special index structure, in which the memory position can be calculated directly. Hash tables are there in competition with tree structures that can play all the index values in an order as opposed to hash tables, but require a greater administrative burden to provide the index. When using a hash table to search in data volumes is commonly known as hash functions. For very large data sets can be used a distributed hash table.