← dev

Data structures & algorithms

A common-sense guide to Data Structures and Algorithms

Data structures refer to how the data is organized.

To understand the performance of any data structure, we need to analyze the access patterns:

• Read: Looking for something in a particular spot.
• Search: Looking for a particular value.
• Insert: Adding a new value.
• Delete: Removing a value from the data structure.

Some data structures:

• Array: List of data elements
• Sets: A list that does not allow duplicate data elements
• Hash Tables/Map/Dictionary: List of paired values, with a key and a value.
• Stack: LIFO constraints on an array
• Queue: FIFO constraints on an array
• Priority Queue: Same as a queue, but we make sure elements are ordered

Node-based data structures:

• Linked List: Data structure that contains data element and a link to the next node in the list.

• Doubly Linked List: Data structure that contains data element and a link to the next and the previous node in the list.

• Tree: Each node can link to multiple nodes, called leaves.

• Binary tree: Each node has only 2 children

• Binary search tree: Same as a binary tree but with the additional restriction that a left child can only contain elements lower than the node itself, and right child are higher

• Heap: Specific type of binary tree that satisfies an specific condition.

  • For a max-heap: The value of each node must be greater than its descendants (heap condition)
  • The tree must be complete. No nodes are missing. Any node has 2 descendants or none at all. The last level can have missing nodes if limited to the very right of the tree.
  • Deletion behaves like a queue, removing the root of the tree, and moving the last node to that position, then trickle it down with the heap condition.
    • Finding the last node (F in the image) is a problem by itself that can be easily solved by implementing the binary tree as an array.

• Trie: Nodes can have any number of nodes, which store letters.

• Graph: Trees are a sub-type of graphs. The restriction on trees, is that they should not have cycles, and all nodes must be connected

  • Here, nodes are called vertex, and relationships are called edges.

• Directed Graph: Edges have a direction.

• Weighted Graph: Edges have a value/weight. - Think shortest-path problem (Dijkstra's Algorithm)

Implementing binary trees as arrays:

• Left child = (index * 2) + 1
• Right child = (index * 2) + 2

Sorting algorithms:

• Bubble sort O(n^2): Compare 2 elements at a time, and swap them if needed. Do this from beginning to end. Repeat everything until no swaps are performed.
• Selection sort O((n^2)/2): For each pass-through, look for the lowest value, and swap with the index of the current pass-through.
• Insertion sort O(n^2 + n): For each pass-through, take n + 1 position, and compare with everything behind it, if lower than what's behind, move elements by one until no more elements are below the current one, and insert in the last gap.
• Quicksort : Recursively partition arrays.
  1. Get a pivot (last element in array), Create a left pointer (first element) and a right pointer (element before pivot)
  2. Move left pointer to right if element is lower than pivot, until no longer lower.
  3. Move right pointer to left if element is higher than pivot, until no longer higher.
  4. Swap values in pointers.
  5. Go back to step 2.
  6. If both pointer meet, swap element pointed to with pivot.
  7. Sub-partition each side of the array at the pivot point.
  • Best case: O(n * log(n))
  • Worst case: O(n^2)
• Mergesort:
  • Best case: O(n * log(n))
• Timsort: wut?

Search algorithms:

• Linear search O(n): Go over each element until you find the data element.
• Binary search O(log(n)): Requires an ordered array. Divide in 2 sides the array, and define if the element search is higher or lower than the middle element. Repeat until you find the data element.
• Quickselect O(n): A hybrid of quicksort and binary search.
• Search on a BST O(log(n))
• Search on Graphs O(V + E): Remember that in this algorithms is important to keep track of already visited vertices
  • Depth-First Search (DFS): For each adjacent vertex, visit, and review next adjacent vertices.
  • Breadth-First Search (BFS): Relying on a queue, visit all adjacent vertices on a node, once exhausted, visit nodes on the first element of the queue. Repeat until queue is empty
• Dijkstra: Find shortest-path in weighted-graph

On recursion:

• Remember to always have a base case to stop the stack growth.
• Dynamic programming, means removing the recursion from a function.
  • Memoization: Reduces recursive calls by remembering previously computed functions. (Sort of having a cache)
  • Going bottom-up: Just ditch recursion.
• Recursion often brings O(2^n) complexity

Notes on Big O Notation:

• Remember it mostly ignores constants, so O((n^2)/2) is only O(n^2)
• It only considers the highest order, so O(n^2 + n) is only O(n^2)

#backlog

• [ ] Mergesort implementation
• [ ] Dijkstra implementation
• [ ] A* implementation
• [ ] Greedy algorithms