5. Data Structure

Data Structure

• The way to organize the data

Stack

push : put at the top
pop : remove from the top

• LIFO (Last In First Out)
• Call Stack (e.g. factorial function)
  • always interact with the top element

Queue

enqueue : put at the back
dequeue : remove from the first

• FIFO (First In First Out)

Linked-List

head
tail
next

• Node and Pointer
  • just store two nodes as a pointer (head/ tail)
• No need to initialise
• No need to relocate (linking)
• No need of indices (head / tail linking)
  • change the point of next when add the element

    Block Chain
    Delegation Chain

What If we want to go back?

Double-Linked-List

• first : H -> null, T -> null
• add the node : H, T -> node
• add one more : H -> new node, T -> old node, new -> old node

LL: {head: Node7, tail: Node29}
Node7: {val: 7, next: Node34}
Node34: {val: 34, next: Node29}
Node29: {val: 29, next: null}

Set

Tree

• Can’t Have a LOOP
• subTree
  • Root
  • Children / Parent
  • Siblings
  • Cousins
  • Descendent
• Leaf Node: bottom node without any children (null)

---

Implementations

Array

Object

---

Hash Table/ Hash Map

• Object in JS: Hash Table/ Map
• same input -> same output
• elements are evenly distributed along the range using hash function
  • hash function: MAX === size of the array
  • multiple values in the same key: contains() -> return true;
    Array : used to keep objecs as elements
    => arr = [obj1, obj2, …]
    Linked-List : used to link the elements that object has
    => obj1 = {[key, value] -> [key, value], …}
    e.g. Person = [name: ‘Lisa’] -> [age: 28] -> …

---

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
예를 들어 우리가 (Key, Value)가 (“John Smith”, “521-1234”)인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function(“John Smith”) % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = “521-1234” 로 전화번호를 저장하게 된다.

REF
mangkyu.tistory.com/102

---

Tree Family

Heap

• type of Tree
• parent has higher priority than children (root: most important)
• highest property is retrieved first

Binary Heap

Add : the leaf node, check the priority through the entire tree by going up
Delete : the root node, put the last leaf node in the root and check the priority by going down the entire tree layer by layer

• Max Heap
• Min Heap
• fully filled layer by layer, with at most 2 leaf nodes

REF
www.cs.usfca.edu/~galles/visualization/Heap.html

Binary Search Tree (BST)

• divide the tree into two parts
  • Left: smaller than the root node
  • Right: bigger than the root node
• UNBALANCED TREE: if adds onlly bigger/ smaller elements, the height of the tree will be longer, thus unbalanced

REF
www.cs.usfca.edu/~galles/visualization/BST.html

B-Tree

• evolution of the binary search tree
• can have more than 2 children
• can have more than 1 key in 1 node

  one key -> 2 children
  two keys -> 3 children
  three keys -> divide into 2 keys with promotting the mid-value to the parent node

• maintain a balance (complement the cons of a BST)
• can have duplicated keys

REF
www.cs.usfca.edu/~galles/visualization/BTree.html

Graph

path
adjacency

• connection between edges with weights (e.g. facebook familiarity)
• pair of sets (Vertices: V, Edges: E)