🪴 Data Structures with Thomas

2021-08-13 15.19.44

Talk with Thomas

Connection can be added to each data structure to give it new powers

Invariants are things that are fundamental to the structure

Array

Continuous memory, Instant lookup of index, binary search can be used.

Traversal -> iteration, recursion (for, map, ext) via index

Queue

first in first out

const queue = [1, 2, 3]
// enqueu Array.push (adds to the end)
// dequeu Array.shift (takes from the front)

const Queue = (items = []) => ({
	items,
	enqueue: element => items.push(element)
})

cosnst q = Queue()
q.enqueue(1)
q.enqueue(2)

Stack

Add and remove from the end

const stack = [1, 2, 3]
// push Array.push (adds to the end)
// pop Array.pop (takes from the back)

Traversal

const traverseArr = (arr) => {
  if (arr.length === 0) return
  console.log(arr[0]) // 1,2,3
  traverseArr(arr.slice(1))
  console.log(arr[0]) // 3,2,1
}

traverseArr([1, 2, 3])

Can pass tail or increment

Linked Lists

Node - data usually with a pointer to the next data (how you get to the next thing is important)

Distributed in memory, infinite size. Searching is slower (can’t use binary search).

Object that has some data and pointer to other notes

Traversal -> recursion

const linkedListNode = (data, next = null) => ({
  data,
  next,
})

const ll = linkedListNode(1, linkedListNode(2, linkedListNode(3)))
console.log(ll) // { data: 1, next: {data: 2, next: {data: 3, next: null}}}

const linkedListNode = (data, next = null, prev = null) => ({
  data,
  next,
  prev,
})

const ll = linkedListNode(1, linkedListNode(2), null)
console.log(ll) // { data: 1, next: {data: 2, next: null, prev: null}, prev: null}

Traversal

const linkedListNode = (data, next = null) => ({
  data,
  next,
})

const ll = linkedListNode(1, linkedListNode(2, linkedListNode(3)))
console.log(ll) // { data: 1, next: {data: 2, next: {data: 3, next: null}}}

const traverse = (head) => {
  if (!head) return // base case to stop recursion
  traverse(head.next)
}

traverse(ll)

Concept Recursion winding up or down. This is my mental modal for recusion. Depending where you call the recursion you can wind on the oposite side.

Binary Tree

const binaryTreeNode = (data, left = null, right = null) => ({
  data,
  left,
  right,
})

const bt = binaryTreeNode(10, binaryTreeNode(9, binaryTreeNode(11)))