Data Structures

Compiler implementations usually use hash tables to look up identifiers. A hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Graphs and trees are linked abstract data structures composed of nodes. Each node contains a value and also one or more pointers to other nodes. Graphs can be used to represent networks, while trees are generally used for sorting and searching, having their nodes arranged in some relative order based on their values.

A union is a value that may have any of several representations or formats, or it is a data structure that consists of a variable which may hold such a value.

It is a common misconception that a priority queue is a heap. A priority queue is an abstract concept like a list or a map, just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.

A queue is a First In First Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed.

Recursion uses stack data structure.

The network data model majorly uses graph data structure.

Quadratic Probing is used for collision resolution in hashing.It is a technique in which the interval between probes is increased by adding the successive outputs of a quadratic polynomial to the starting value given by the original hash computation.

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.

By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal spanning tree algorithm and Dijkstra's shortest path problem.

The Breadth First Search algorithm uses a queue data structure to store intermediate results as it traverses the graph.

A walk in which the children are traversed before their respective parents are traversed is called a post-order walk.

Arrays are useful mostly because the element indices can be computed at run time. Among other things, this feature allows a single iterative statement to process arbitrarily many elements of an array. For that reason, the elements of an array data structure are required to have the same size and should use the same data representation.

A stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop.