# Data structures and Algorithms
Hello everyone, this note took a lot of time for me to explain and implement because I'm not a native speaker.
By the way, using English to explain the note is benefiting my English. If there is a mistake in the sentence or an incorrect topic, please text me.
## Table of Contents
* Data Strucrures
* [Bit](#Bit)
* [Data Type](#Data-type)
* [1's complement]()
* [2's complement]()
* Linked List
* [Singly Linked List](#Singly-Linked-List)
* [Doubly Linked List](#Doubly-Linked-List)
* Tree
* [Types of Tree](#Types-of-Tree)
* [Traversal](#Traversal)
* [Level-order](#Level-order)
* [Pre-order](#Pre-order)
* [In-order](In-order)
* [Post-order](Post-order)
* [Binary Tree](#Binary-Tree)
* [Binary Search Tree](#Binary-Tree)
* [Hash Table](#Hash-Table)
* Stack
* Queue
* [Regular Queue]()
* [Circular Queue]()
* [Priority Queue]()
* Algorithms
* Recursion
* Sum
* Fibonacci
* Search
* Linear Search
* Binary Search
* Sort
* Bubble Sort
* Insertion Sort
* Selection Sort
* Merge Sort
* Quick Sort
* Heap Sort
---
## Bit
* bit - basic unit of information(電腦中最小資訊單元)，也稱為1b
* byte - collection 8 bits to 1 group(8個位元一組)，也稱為1B
> 電信公司在說的300M，通常為300Mbps/s，但是下載軟體通常是用MB為單位，所以需轉換為位元組37.5MBps/s。
在電路中只會有低電壓(L)或者是高電壓(H)，而電腦的核心就是電路，**所以我們使用0代表低電壓，1代表高電壓**。當然，你要用X、Y也可以表示高、低電壓。
---
## Data Type
在程式語言中，我們需要宣告(define)該資料為何種型態才能讓編輯器(compliler)轉換成組合語言(assembly language)也就是機器語言。
### Binary
Binary(二進制)，也就是相加為2則進位，現實生活中我們的算數其實是decimal(十進制)，而踏入電腦世界中我們必須用二進制的概念才能使電路及電腦能夠連結。
> 01000001
上面這是一個8位元的表示法，，我們可以知道每個位元**由右至左**依序為$bitBinary=f(T)=2^{(T-1)}$
>以`01000001`為例
* Int(integer) - 對於整數來說可以是數字**65**
* Char(character) - 對於字串(string)來說可以是[ASCII Codes](https://en.wikipedia.org/wiki/ASCII)中的**A**
* BCD(binary codes decimal) - 用於二進位轉十進位，並且每4個bit為一組，也就是**41**
### Negative Number
當一個8位元的資料為00000101，我們可以知道是
#### 1's complement
#### 2's complement
---
## Linked List
Linked List(鏈結串列)，是一種透過指標指向節點的一種資料結構
**Time complexity:**
Write **O(1)**
Read **O(n)**
Delete **O(1)**
### Singly Linked List
***Methods:***
**append** - 新增節點至最後一個元素
**insertAfterNode** - 插入節點至目標後面
**traverse** - 遍歷
**getNode** - 取得目標節點
**getLength** - 回傳當前串列長度
```javascript=
//define node for pointer
class NodeStructure {
data = null;
next = null;
constructor(data) {
this.data = data;
}
}
// main class
class LinkedList {
// #is private modifier
#head = null;
#length = 0;
append(data) {
const node = new NodeStructure(data);
if (this.#head == null) {
this.#head = node;
this.#length++;
} else {
let pointer = this.#head;
while (pointer.next != null) {
pointer = pointer.next;
}
pointer.next = node;
this.#length++;
}
}
traverse() {
if (this.#length == 0) {
return;
}
if (this.#length == 1) {
console.log(this.#head);
return;
}
if (this.#length > 1) {
let pointer = this.#head;
console.log(pointer.data);
while (pointer.next != null) {
pointer = pointer.next;
console.log(pointer.data);
}
}
}
getLength() {
return this.#length;
}
getNode(data) {
let pointer = this.#head;
if (pointer.data == data) {
return pointer;
} else {
while (pointer.next != null) {
pointer = pointer.next;
if (pointer.data == data) {
break;
}
}
return pointer;
}
}
insertAfterNode(node, data) {
const nextTempNode = node.next;
node.next = new NodeStructure(data);
node.next.next = nextTempNode;
this.#length++;
this.traverse();
}
}
const linkedList = new LinkedList();
linkedList.append("Dennis");
linkedList.append("Ivy");
linkedList.append("Allen");
const targetNode = linkedList.getNode("Ivy");
linkedList.insertAfterNode(targetNode, "Josh");
//Dennis Ivy Josh Allen
```
> updated on Oct,08,2023
### Doubly Linked List
```javascript=
class NodeStructure {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
//main
class DoublyLinkedList {
#head = null;
#length = 0;
push(value) {
const node = new NodeStructure(value);
if (this.#length == 0) {
this.#head = node;
this.#length++;
} else {
let pointer = this.#head;
while (pointer.next != null) {
pointer = pointer.next;
}
pointer.next = node;
node.prev = pointer;
this.#length++;
}
}
traverse() {
if (this.#length == 0) {
return "Sorry list is empty";
} else {
let pointer = this.#head;
console.log(pointer);
while (pointer.next != null) {
pointer = pointer.next;
// console.log(pointer.prev);
console.log(pointer);
}
}
}
getNode(value) {
let i = 1;
let pointer = this.#head;
while (i < this.#length) {
if (pointer.data == value) {
break;
}
pointer = pointer.next;
i++;
}
return pointer;
}
getLength() {
return this.#length;
}
}
const doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.push(2);
doublyLinkedList.push(4);
doublyLinkedList.push(6);
const length = doublyLinkedList.getLength();
console.log(length); //3
doublyLinkedList.traverse();
const target = doublyLinkedList.getNode(4);
console.log(target);
{
/* <ref *1> NodeStructure {
data: 2,
prev: null,
next: <ref *2> NodeStructure {
data: 4,
prev: [Circular *1],
next: NodeStructure { data: 6, prev: [Circular *2], next: null }
}
}
<ref *1> NodeStructure {
data: 4,
prev: NodeStructure { data: 2, prev: null, next: [Circular *1] },
next: NodeStructure { data: 6, prev: [Circular *1], next: null }
}
<ref *2> NodeStructure {
data: 6,
prev: <ref *1> NodeStructure {
data: 4,
prev: NodeStructure { data: 2, prev: null, next: [Circular *1] },
next: [Circular *2]
},
next: null
} */
}
```
> updated on Oct,09,2023
---
## Tree
The Tree of data structures is according tree's structure to simulate leaf and branch。
In computer science, the tree is one of the most important concepts in data structures.
* Graph -> Tree -> Binary Tree -> Binary Search Tree -> Red-Black Tree
1. Folder
2. BST
3. HTML DOM
### Types of Tree
* Binary Tree
* Ternary Tree
* N-ary Tree
> source: https://www.geeksforgeeks.org/types-of-trees-in-data-structures/?ref=lbp
### Traversal
We can use the following traversal methods to traverse nodes in binary, ternary, and n-ary trees.
* Breadth First Search
* [Level-order Traversal](#Level-order)
* Depth First Search
* [Pre-order Traversal](#Pre-order)
* [In-order Traversal](#In-order)
* [Post-order Traversal](#Post-order)
[Leve-order resource](https://www.geeksforgeeks.org/level-order-tree-traversal/)
[Pre-order resource](https://www.geeksforgeeks.org/preorder-traversal-of-binary-tree/?ref=ml_lbp)
[In-order resource](https://www.geeksforgeeks.org/postorder-traversal-of-binary-tree/?ref=ml_lbp)
[Post-order resource](https://www.geeksforgeeks.org/postorder-traversal-of-binary-tree/?ref=ml_lbp)
### defination
* If the node has a child node that is called the "subtree".
* Each subtree's parent node is called the "root".
* If the node does not have a child node, it is called a "leaf".
* If a parent node has another subtree, the subtree is called a "sibling node".
::: info
Below, we will use the binary tree to explain traversal.
:::
#### Level-order
```bash=
A level 0
/ \
B C level 1
/ \ / \
D E F G level 2
\
H level 3
```
Step1: According to the priority level of the tree for output.
>output A->B->C->D->E->F->G->H
#### Pre-order
```bash=
A
/ \
B C
/ \ / \
D E F G
\
H
```
Step1: Traverse from A to left subtree, mark it as visited.
Step2: There is subtree D of B, mark B as visited and go to subtree D.
Step3: There is no subtree of D; therefore, it is called a leaf.
Step4: Return to the root node B and traverse its right subtree.
Step5: Return to the root node B and traverse its right subtree. Loop above Step 2 and Step 3.
>output: A->B->D->E->H->C->F->G
#### In-order
```bash=
A
/ \
B C
/ \ / \
D E F G
\
H
```
Step1: From A, move to its left subtree B, and then to its left subtree D. Since D is a leaf, mark it as visited.
Step2: Back to root B; mark it as visited.
Step3: In tree B, there is a right subtree E; mark it as visited.
Step4:
In tree E, there is a right leaf H; mark it as visited.
Step5: Return to the top root node and traverse its subtree to find a left or right leaf.
>output: D->B->E->H->A->F->C->G
#### Post-order
```bash=
A
/ \
B C
/ \ / \
D E F G
\
H
```
Step1: From node A, traverse to its left subtree, find a leaf node, and mark it as visited.
Step2: There is no subtree of D; return to the parent root node B.
Step3: There is a right subtree of B; move to subtree E.
Step3: There is only a right subtree of E; move to the right subtree.
Step4: There is no subtree of node H; mark it as visited.
Step5: Because the root node A has a right subtree, mark node F as visited after nodes E and B have been marked.
>output: D->H->E->B->F->G->C->A
### Binary Tree
二元樹(Binary Tree)是一個節點(root)中有兩個子節點(sub root)並且在其左右。
而二元搜尋樹(Binary Search Tree)就是在二元樹的基礎下，再增加一些條件，例如:比root大則放在右邊，反之放其左邊。
```bash=
1 root
/ \
2 3 layer 1
/ \ \
4 5 6 layer 2
```
#### Types of Binary Tree
Complete Binary Tree
```bash=
1 root
/ \
2 3 layer 1
/ \ \
4 5 6 layer 2
```
Perfect Binary Tree
* $2^{h} -1$
```bash=
1 root
/ \
2 3 layer 1
/ \ / \
4 5 6 7 layer 2
```
### Binary Search Tree
二元搜尋樹(Binary Search Tree)也被稱為 BST.
rule:
> Each node to the left of root must less than the root.On the other hand, each node to right of root must greater than the root.
For example:
```bash=
10 root
/ \
8 15 layer 1
/ \ \
3 6 20 layer 2
```
Above graphic have a problem on layer 2.
```bash=
10 root
/ \
8 15 layer 1
/ \
6 20 layer 2
/
3 layer 3
```
#### BST-Insert
Below example, insert 10、20、20、5 into tree.
```javascript=
class NodeStructure {
constructor(value) {
this.data = value;
this.right = null;
this.left = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const node = new NodeStructure(value);
if (this.root == null) {
this.root = node;
return;
} else {
let pointer = this.root;
while (true) {
if (node.data > pointer.data) {
if (pointer.right != null) {
pointer = pointer.right;
} else {
pointer.right = node;
break;
}
} else if (node.data < pointer.data) {
if (pointer.left != null) {
pointer = pointer.left;
} else {
pointer.left = node;
break;
}
} else {
// node.data exist in tree
console.log("sorry can't insert this value");
break;
}
}
}
}
}
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(20);
tree.insert(20); //sorry can't insert this value
tree.insert(5);
console.log(tree);
// BinarySearchTree {
// root: NodeStructure {
// data: 10,
// right: NodeStructure { data: 20, right: null, left: null },
// left: NodeStructure { data: 5, right: null, left: null }
// }
// }
```
>updated on April 28th,2024
---
## Hash Table
The hash table is a data structure that uses a hash function to map keys to values.
### Hash function
For example, the input value will be stored in the value box and mapped with the mod key.
:::danger
If the new input is 20, the hash table will have the same key of 0.
:::
It's called a collision when an unnecessary hash function produces the same result.
#### solutions
* **Open Addresing**
* Search for a empty slot sequentially
* **Closed Addresing**
1. Use a linked list or tree to resolve collisions with the same key in the hash table
2. Multiple hash function
Sign in with Wallet
Connect another wallet