資料結構 part 2: Linked list, stack & queue and hashtable
===

---

###### tags: `data strcuture`, `資料結構`

這篇的筆記主要來自於 Wilson Ren 的[資料結構與演算法](https://www.udemy.com/course/algorithm-data-structure/#instructor-1)課程以及[JavaScript 資料結構與演算法](https://www.books.com.tw/products/0010805943#:~:text=%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%EF%BC%88data%20structure%EF%BC%89%E6%98%AF,%E9%9B%86%E5%90%88%E5%87%BD%E6%95%B8%E8%88%87%E9%9B%9C%E6%B9%8A%E8%A1%A8%E3%80%82)

# Linkedin List 鏈結串列
「陣列」是程式語言中最常見的存放資料序列的資料結構，但「陣列」的缺點是：**大小固定，移動成本高**。

相較於「陣列」，「鏈結串列」內的元素，不同於「陣列」在記憶體內是連續存放的，而「鏈結序列」則是：
1. **不是連續存放**。
2. 由 **元素本身的節點(這裡的元素可以是：字串、數字、陣列或任何)和指向下一個元素的引用(指位器或鏈結)** 組成。
3. 包含起點(head)和長度(length)。
4. 長度均由 0 開始，視插入多少 node 來計算最終長度。(但陣列是一開始要先定義好長度)


## Pros
- 「鏈結序列」在新增或移除時，不需要移動其他元素。假設要刪除 "Jake"，只需要把 "Allen" 的指位器指向 "Kelvin" 就好。


> 陣列：可以直接存取任一位置的任何元素。

## Cons
- 「鏈結序列」若要存取中間位置的元素，則需要從起點(head)開始迭代直到找到為止。
- 由於使用指位器，所需的記憶體較陣列多。
- 由於是不連續存放元素，若序列越大，要存取某位置的元素時，時間會花費越多。
- 反向遍歷的操作上會顯得較為困難。

> 陣列：
> - 新增元素：會不斷擴大電腦所需記憶體，假設有一個陣列的長度為 4，當該陣列滿了，想要再增加第 5 個元素的話，電腦就會額外建立 4 個記憶體空間，以此類推。


> - 刪除元素：當刪除陣列的任一位置的元素時，後面的元素都必須逐一往前遞補。


---
## linked list push

增加資料會考慮到的事情：
1. 如果新增的資料為第一個資料，代表後續沒有其他資料，那麽新增加的節點就會是 `head = null`，`length = 0`。
2. 如果不是第一個，那麼就要設定當前位置為 `head`，透過迴圈來遍歷每一個節點，如果不為 `null`，就把當前位置的節點設定為下一個節點，直到最後，再將最後一個節點的下一個指向新的 `node`，然後 `length` 在上述作業完後加一。

// create node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// create linked list
class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    
    // create a push func
    push(value) {
        let newNode = new Node(value)
        // If nothing in linked list, newNode would be the head
        if (this.head === null) {
            this.head = newNode;
        } else {
            // if something inside the linked list, then we need to find 
            // the current position 
            let currentNode = this.head;
            
            // use while loop to loop thr, if it's not null, 
            // value of currentNode would be the next value
            while(currentNode.next !== null) {
                currentNode = currentNode.next;
            }
            // otherwise, the next vlaue of currentNode would the new one.
            currentNode.next = newNode;
        }
        this.length++;
    }
    // create a func that can print out all nodes
    printAll() {
        if (this.length === 0) {
            console.log("0");
            return 
        }
        let currentNode = this.head;
        while(currentNode !== null) {
            console.log(currentNode.value);
            currentNode = currentNode.next;
        }
    }
}

let myLinkedList = new LinkedList()
myLinkedList.push("Mike");
myLinkedList.push("Allen");
myLinkedList.push("Jake");
myLinkedList.push("Kelvin");

myLinkedList.printAll();
console.log(myLinkedList.length)


---

## linked list pop

刪除資料會需要考慮到的事情：
1. 如果該鏈結串列內的資料的 `head` 不存在，就返回 `null`。
2. 如果長度等於 1 表示只有 `head`，那麼 `head = null`，`length = 0`，但因為 `pop()` 會返回刪除的值，因此我們必須將 `head` 存在另外一個變數，然後返回該變數。
3. 刪除最後的值，必須要遍歷到倒數第二個，因為只要將倒數第二個的 pointer 設定為 `null`，長度減一即可。假設長度為 `k`，那麼倒數第二個位置則為 `k-2`



// create node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// create linked list
class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    
    // create a push func
    push(value) {
        let newNode = new Node(value)
        // If nothing in linked list, newNode would be the head
        if (this.head === null) {
            this.head = newNode;
        } else {
            // if something inside the linked list, then we need to find 
            // the current position 
            let currentNode = this.head;
            
            // use while loop to loop thr, if it's not null, 
            // value of currentNode would be the next value
            while(currentNode.next !== null) {
                currentNode = currentNode.next;
            }
            // otherwise, the next vlaue of currentNode would the new one.
            currentNode.next = newNode;
        }
        this.length++;
    }
    pop() {
        if(!this.head) {
            return null;
        } else if (this.length === 1) {
            let temp = this.head;
            this.head = null;
            this.length = 0;
            return temp;
        } else {
            // loop thr all the node
            // create a current position
            let currentNode = this.head;
            for (let steps = 1; steps <= length -2; steps++) {
                currentNode = currentNode.next;
            }
            let temp = currentNode.next;
            currentNode.next = null;
            this.length --;
            return temp;
        }
    }
    // create a func that can print out all nodes
    printAll() {
        if (this.length === 0) {
            console.log("0");
            return 
        }
        let currentNode = this.head;
        while(currentNode !== null) {
            console.log(currentNode.value);
            currentNode = currentNode.next;
        }
    }
}

let myLinkedList = new LinkedList()
myLinkedList.push("Mike");
myLinkedList.push("Allen");
myLinkedList.push("Jake");
myLinkedList.push("Kelvin");
let poppedValue = myLinkedList.pop();
console.log(poppedValue);
myLinkedList.printAll();
console.log(myLinkedList.length)


// Node { value: 'Kelvin', next: null }
// Mike
// Allen
// Jake
// 3

# Stack & Queue

# Hashtable