# Singly linked list
有以下特點

1. 新增、刪除元素的相較於陣列來說代價很小
2. 沒有index
3. 無法直接獲取特定的元素

singled linked list 是由一個Node一個個指向下一個，若要尋找某一特定元素，需要從頭部開始尋找。


例如我想要尋找到29這個數，會由**head開始確認，確認是否為29，不是進行下一個直到找到29這數字**。

insert的方式也非常簡單，例如我想在42與6之間insert數字77。


只需要將42的箭頭指向77並將77指向6即可


從頭或尾巴插入更簡單，從頭指向原本的頭即可，從尾直接指向新的數。


## 實作

Singly Linked List 是由一連串的Node串連而成，每個Node都會有自己的值，每個Node又會指向下一個Node。Singly Linked List也需要有append, unshift, insert, delete, get, set, pop方法。

### Node
首先先做出Node，該class應該需要有本身的值與next指向下一個Node

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

### Singly Linked List
定義完Node後實作Singly Linked List，該class要有head, length, tail

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

### Append

1. 建立一個新的Node
2. 判斷若length是0，代表list中沒有Node的存在，新的Node等於head, tail
3. Length 加一
4. 回傳list

// 省略...
append(val) {
    const newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length += 1;
    return this;
}

其中head與tail都reference Node，所以head與tail next每次執行都會update。

### Pop

1. 確認list的長度，若為0返回`undifine`
2. 從head至tail找到tail與tail的前一個
3. 設定新的tail
4. list長度減1
5. 確認tail長度，若為0將head與tail設為`null`
6. 回傳tail

// 省略...
pop() {
    if (this.length === 0) return undefined;

    let current = this.head;
    let prev = this.head;

    while (current) {
      if (current.next === null) {
        this.tail = prev;
        this.tail.next = null;
        this.length -= 1;

        if (this.length === 0) {
          this.tail = null;
          this.head = null;
        }

        return current;
      }
      prev = current;
      current = current.next;
    }
  }
}

### Shift

1. 確認長度是否為0，是的話回傳`undefined`
2. 保存this.head
3. this.head.next 為新的head
4. length減一
5. 若length為0，設tail為null
6. 回傳保存下來的this.head

// ...省略
shift() {
    if (this.length === 0) return undefined;

    const head = this.head.val;
    this.head = this.head.next;
    this.length -= 1;

    if (this.length === 0) this.tail = null;
    return head;
}

### Unshift

1. 傳入參數值，建立新的Node
2. 判斷head是否存在，若不存在this.head = 新的Node
3. 若存在則new Node的next是現在的head
4. this.head替換成new Node
5. 長度加一
6. 回傳list

// ...省略
unshift(val) {
    const newNode = new Node(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length += 1;
    return this;
}

### Get

1. 傳入Index(從0開始)至method
2. 如果index < 長度 + 1或小於0 回傳`undefined`
3. 建立current儲存this.head
4. 若index為0則回傳current
5. 否則current = current.next
6. index - 1
7. 重複第4步驟

// ...省略
get(index) {
    if (this.length < index + 1 || index < 0) return undefined;
    let current = this.head;

    while (index) {
      current = current.next;
      index -= 1;
    }
    return current;
}

**O(n)**
### Set

1. 傳入index與value
2. 從Get method 得到node
3. 若得到的node不存在，回傳`false`
4. 修改node value並回傳`true`

// ...省略
set(index, val) {
    const node = this.get(index);

    if (!node) return false;

    node.val = val;
    return true;
}

### Insert

1. 傳入index與value
2. 確認index長度若 < 0或大於list的長度return `false`
3. 若index = list的長度 call append method, return `true`
4. 若index = 0 call unshift method, return `true`
5. 用get method 找尋index前一個node(preNode)
6. 實作新的node(newNode)
7. newNode的next = newNode的next
8. preNode的next = newNode
9. 長度加一,回傳`true`

// ...
insert(index, val) {
    if (index < 0 || this.length < index) return false;
    if (index === this.length) return !!this.append(val);
    if (index === 0) return !!this.unshift(val);

    const preNode = this.get(index - 1);
    const newNode = new Node(val);

    newNode.next = preNode.next;
    preNode.next = newNode;
    this.length += 1;
    return true;
}

**O(1)**
### Remove

1. 傳入index
2. 若index < 0 或 index > list長度減一 return `undefined`
3. 若index = list長度減一 return and call pop method
4. index = 0 return and call shift method
5. call get method 得到list前一個node(preNode)
6. preNode的next是要被移除的Node(removedNode)
7. preNode的next = removedNode的next
8. 長度減一
9. 回傳removedNode

remove(index) {
    if (index < 0 || this.length - 1 < index) return undefined;
    if (index === this.length - 1) return this.pop();
    if (index === 0) return this.shift();

    const preNode = this.get(index - 1);
    const removedNode = preNode.next;
    preNode.next = removedNode.next;
    this.length -= 1;
    return removedNode;
}

**O(1)** or **O(n)**

### Reverse

1. 交換head與tail, 並儲存原head的list(node)
2. 定義next與pre = null
3. loop next = node.next, node.next = pre, pre = node, node = next
4. 回傳this


reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;

    let next;
    let pre = null;

    for (let i = 0; i < this.length; i += 1) {
      next = node.next;
      node.next = pre;
      pre = node;
      node = next;
    }

    return this;
}

###### tags: `Data Structure`