Data Structures

Big-O Cheat Sheet

Linear data structures

Arrays

An array is a data structure consisting of a collection of elements, of the same memory size, each identified by at least one array index. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called a one-dimensional array.

Types of arrays include static arrays, dynamic arrays, and associative arrays. and multidimensional arrays.

Static arrays

Static arrays have a size that is fixed when they are created and consequently do not allow elements to be inserted or removed. When the word “array” is used without qualification, it usually refers to a static array.

• Good for:

  • Accessing elements by index in constant time.

  • Storing an element at a specific index, or at the end of the array, in constant time.

  • Static arrays are efficient if you know the index of the element you want to access ahead of time.

  • Space efficiency as few pointers are needed.

  • Sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called locality of reference.

• Bad for:

  • Insert or delete operations at the beginning or in the middle of the array, as it requires shifting all elements after it.

• Uses:

  • Implementing other data structures such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.

  • Vectors, matrices, and higher-dimensional arrays (including table-like structures).

  • Libraries provide low-level optimized facilities for copying ranges of memory (such as memcpy) which can be used to move contiguous blocks of array elements significantly faster than can be achieved through individual element access.

  • Database records.

  • Storing a sequence of elements of the same type.

Dynamic arrays

NOTE: Elaborate on this.

Dynamic arrays can be more space-efficient than static arrays, since they only allocate memory for the number of elements they actually hold.

Dynamic arrays can be more time-efficient for inserting elements at the end of the array.

Stacks

A stack is a collection of elements governed by a Last-In-First-Out (LIFO) policy. Stacks are implemented with arrays or linked lists.

Stacks require two primary operations:

• Push: Add an element to the top of the stack.
• Pop: Remove the top element from the stack.

Some additional operations include:

• Peek: Return the top element without removing it.
• IsEmpty: Check if the stack is empty.
• IsFull: Check if the stack is full.
• Size: Return the number of elements in the stack.

A stack may have a fixed capacity, or it may be dynamically resizable. If an element is pushed onto a full stack, it is called a stack overflow.

A stack underflow occurs when an element is popped from an empty stack.

• Good for:

  • Accessing, insertion, and deleting the last element in constant time.

  • Use cases that require LIFO behavior.

• Bad for:

  • Use cases that don’t require LIFO behavior.

• Uses:

  • Function call stack.
  • Undo mechanisms in text editors.
  • Expression evaluation.
  • Backtracking algorithms.
  • Memory management.
  • Parsing.
  • Depth-first search.

Trees

Log-structured merge-tree (LSM tree)

The log-structured merge-tree (also known as LSM tree, or LSMT) is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data.