A data structure is a format for organizing, managing, and storing data so that it can be efficiently accessed or modified. A data structure is a concrete representations of data, whereas abstract data types define the logical form of the data type. Understanding the performance a data structure provides relies upon analysis of the algorithm’s computational complexity.

Some data structures provide better performance than others *for a particular application*.

Data structures are classified into two categories:

- linear data structures
- non-linear data structures

A structure where elements are arranged sequentially and attached to their next and previous adjacents are called **linear data structures**. This type of structure involves a single level and therefore all elements can be traversed in a single run.

Examples of linear data structures include: array, stack, queue, linked list.

A structure where elements are not arranged sequentially are called **non-linear data structures**. This type of structure involves more than a single level and therefore all elements cannot be traversed in a single run.

Examples of non-linear data structures include: tree, graph, map.

An **interface** represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can accept, and return type of these operations.

**Implementation** provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure.

A static array is a fixed length container of contiguous chunks of memory containing n elements indexable—each position can be referenced with a number—from range [0, n-1]. The only way to access elements in an array is by their index. Array indexing is zero-based, meaning the first element is found at position zero.

- Storing and accessing sequential data
- Used by IO routines as buffers
- Lookup tables and inverse lookup tables
- Used to return multiple values from a function
- Used in dynamic programming to cache answers to sub-problems

Static array | |
---|---|

Access | $O(1)$ |

Search | $O(n)$ |

Insertion | N/A |

Appending | N/A |

Deletion | N/A |

A dynamic array differs from a static array in that it does not have a fixed length. Rather, a dynamic array can grow and shrink in size as needed.

*One* way of implementing a dynamic array is to use a static array.

- Create a static array with an initial capacity.
- Add elements to the underlying static array, keeping track of the number of elements.
- If adding another element will exceed the capacity, then create a new static array with twice the capacity and copy the original elements into it.

Dynamic array | |
---|---|

Access | $O(1)$ |

Search | $O(n)$ |

Insertion | $O(n)$ |

Appending | $O(1)$ |

Deletion | $O(n)$ |

C.f. Linked list

A stack is a one-ended linear data structure which models a real world stack by having two primary operations: **push** and **pop**. A stack is a last in first out (LIFO) data structure.

- Used by undo mechanisms in text editors.
- Used in compiler syntax checking for matching brackets and braces.
- Used behind the scenes to support recursion by keeping track of previous function calls.
- Can be used to do a Depth First Search on a graph.

Stack | |
---|---|

Pushing | $O(1)$ |

Popping | $O(1)$ |

Peeking | $O(1)$ |

Searching | $O(n)$ |

Size | $O(1)$ |

*One* way of implementing a stack is by using a singly linked list:

- To initialize, point the head to a null node.
- To push, insert a new node before the head and adjust the head pointer to the new node.
- To pop, move the head pointer to the next node and deallocate the last node.

A queue is a linear data structure which models real world queues by having two primary operations: **enqueue** and **dequeue**. A queue is a first in first out (FIFO) data structure.

- Any waiting line models a queue.
- Used to keep track of the
*x*most recently added elements. - First come first serve web server request management.
- Breadth first search (BFS) graph traversal.

- Enqueue: add an element to the end of the queue
- Dequeue: remove an element from the front of the queue

There is no consistent terminology for inserting and removing elements from a queue. Enqueue is sometimes called adding or offering; dequeue is sometimes called removing or polling.

Queue | |
---|---|

Enqueue | $O(1)$ |

Dequeue | $O(1)$ |

Peeking | $O(1)$ |

Contains | $O(n)$ |

Removal | $O(n)$ |

is Empty | $O(1)$ |

A priority queue is an abstract data type that operates similar to a normal queue except that each element has a certain priority. The priority of the elements determine the order in which elements are removed. Priority queues only support **comparable data**, meaning the data must be able to be ordered in some way from least to greatest or greatest to least so that it is possible to assign relative priorities to each element.

- Anytime you need to dynamically fetch the ‘next best’ or ‘next worse’ element.
- Used in certain implementations of Dijkstra’s Shortest Path algorithm.
- Used in Huffman coding which is often used for lossless data compression.
- Best first search algorithms such as A*.
- Used by minimum spanning tree algorithms.

Priority queue | |
---|---|

Binary heap construction | $O(n)$ |

Polling | $O(log(n))$ |

Peeking | $O(1)$ |

Adding | $O(log(n))$ |

Naive removing | $O(n)$ |

Removing (hash table) | $O(log(n))$ |

Naive contains | $O(n)$ |

Contains (hash table) | $O(1)$ |

Problem: Often the standard library of most programming languages only provide a min PQ which sorts by smallest elements first, but sometimes we need a max PQ. Since elements are comparable, they implement some sort of comparable interface which we can simply negate to achieve a max heap.

A tree represents data as parent nodes linked to child nodes by edges.

A binary tree is a tree structure that adheres to the following properties:

- The value of the left sub-tree is less than the value of its parent node
- The value of the right sub-tree is greater than or equal to the value of its parent node

A graph represents data as nodes and edges.