Data Structures

Data Structures are representations of data collections that provide algorithms (procedures / functions / methods) that to support operations upon the data in the collection. States a solution to a problem.

Interface also know as application programming interface (API) or abstract data type (ADT) provide a specification by which the data structures abide in order to create consistency between implementations of data structures. These specify what data can be stored in a data structure and what operations a data structure should support. States a problem to be solved.

Amortization, an operation takes T(n) amortized time if any k number of operations takes at most k * T(n) time. This is an averaging over the sequence of operations.

The Two Main Interfaces

Set

Sequence

Static Sequence Interface: Maintain a sequence of items $x_0,x_1,...,x_{n-1}$ subject to the following operations:

  • build(x): Makes a new data structure for items in x;
  • len(): Returns the number of items;
  • iter_seq(): Output $x_0,x_1,...,x_{n-1}$ in sequence order.
  • get_at(i): Return $x_i$ (index i)
  • set_at(i, x): set $x_i$ to $x$
  • get_first(): Returns the first value in the sequence.
  • get_last(): Returns the last value in the sequence.
  • set_first(): Set the value of the first index in the sequence.
  • set_last(): Set the value of the last index in the sequence.

Dynamic Sequence Interface: Static sequence interface plus the following:

  • insert_at(i, x): Make $x$ the new $x_i$, shifting $x_i$ to $x_{i+1}$ for all x less than n to include the newly inserted value.
  • delete_at(i): Shift $x_{i+1}$ to $x_i$ for all x less than n.
  • insert_first(x): Shift all elements over by one and add $x$ to the front.
  • insert_last(x): Add $x$ to the end.
  • delete_first(): Remove the first element and shift all elements over.
  • delete_last(); Remove the last element.

The Two Main Data Structure Approaches

Using Arrays

Static Array

Dynamic Array

Linked List, Array Based

Using Pointers

Linked List, Pointer Based

Trees

AVL Tree

An AVL tree is a type of self-balancing binary search tree, named after its inventors, Adelson-Velsky and Landis (AVL). Like Red-Black trees, AVL trees also perform reconciliation on inserts and deletes to maintain it’s properties as a balanced search tree; being that for any node, the height of its two subtrees differs by at most 1. This is called the balance factor.

balance factor = height of left subtree - height of right subtree

AVL trees have O(log(n))) for search, insert, and delete

While Red-Black trees have bettor amortized time complexity for insert and delete, you may prefer AVL trees due to it’s more strict balancing for lookup-intensive applicaitons.