Data structure

In computer programming, a data structure is a predefined format for efficiently storing, accessing, and processing data in a computer program. Some data structures are provided as a built-in component of a programming language, and others may require the inclusion of a library or module before the structure can be used. One of the most important steps in designing and writing a computer program.

Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

Linus Torvalds

Primitive data structures

The following are primitive data structures, also known as data types. Each of the following primitives can hold a single value, such as 1, 3.14, or the lowercase letter a.

Compound data structures

Compound data structures can contain multiple elements. These elements are usually values of a primitive data type, such as an integer or character. Some compound structures are restricted to a single data type, while others permit a mixture of data types. Some can contain data structures as elements.

Linear data structures

A linear data structure is a compound data structure whose elements are arranged in a logical sequence. In these structures, every element is followed by exactly one other element, unless it is the last one.

Tree structures

A tree is a compound structure whose elements are arranged in a parent-child hierarchy, similar to branches on a tree. The elements are referred to as nodes. A tree contains a single root node, which has no parents. Traversal usually occurs only in one direction, from the node to one of its children (called “descendents”). Then, traversal continues recursively, to one of the children of that node, until the desired node is reached. If a node has no children, it is called a leaf node.

If a tree is balanced, it is organized so that all branches are of the same “depth” — all leaf nodes have the same distance from the root node. If a tree is unbalanced, there is no restriction on how long a branch can be in relation to the others. Unbalanced trees are simpler to implement, but maybe less efficient in worst-case scenarios.

Hash structures

In computer science, a hash function is a function that produces a fixed-length number, often represented in hexadecimal, that can be calculated from a given set of input data. Regardless of the size of the input, as long as the input has not changed, it will always produce the same fixed-length hexadecimal number. These types of functions have important uses in computer science, because they can be used to validate or index data, even at a massive scale.

The following are examples of data structures designed to store the results of hash functions, many of which are special cases of structures described in the sections above.

Graph structures

A graph is a data structure that organizes data according to the relationships of its elements in a geometric space. The elements are usually vertices (points in the graph) and edges (the connections between vertices).

If the vertices in a graph can be traversed in only one direction (A→B, but not B→A), it is called a Directed graph. If vertices can be traversed in either direction, it is called an Undirected graph. If it’s possible to traverse edges and return at the starting vertex, it is called a Cyclic graph. If such traversal is not possible, it is called an Acyclic graph.