資料結構大致上可以分為 linear 和 non-linear 兩種類別，其中 linear data structure 包含 array, linked-list stack, queue， non-linear data structure 包含 trees, graphs。

其中 non-linear 其實也可以用 linear data structure 來表示，因此先來介紹 linear data structure。

1. Linear data structure 定義

• 元素之間有順序性的
• 若元素存在多個，則第一個元素沒有 predecessor (前驅元素)，最後一個元素沒有 successor (後繼元素)
• 除了第一個元素和最後一個元素，其餘元素都只有一個 predecessor 和 successor

Linear data structure 按照儲存方式又分為：

• Sequential list (循序儲存結構)：Array
• Linked list (鏈式儲存結構)：Linked-list

有些文章會把 stack 和 queue 歸類在循序儲存結構，但實際上 stack 和 queue 也都存在鏈式儲存結構。

2. Array (陣列)

Array 為 linear data structure 的循序儲存結構，指的是會分配一段連續記憶體位置來儲存這個 linear list。因此一般來說在高階的程式語言中 array 的長度是固定的，**除了 JavaScript 之外！**JavaScript 的 array 長度是可以隨著元素的增減自動伸縮。但舉例來說，在 go 裡面，array 一旦宣告了，長度就是固定的，若是要使用像 JavaScript 中 array 的 data structure，則必需用 slice 這個資料型態。

2.1 時間複雜度

對 array CRUD 的 time complexity (Average)

3. Linked-list (鏈結串列)

Linked-list 為 linear data structure 的鏈式儲存結構。在 array 中，宣告時即確定了該 array 的長度，因此如果宣告的長度太小，則需要重新宣告新的 array，宣告的長度太大，則會造成記憶體空間的浪費。

Linked-list 和 array 最大的差別則是記憶體儲存的位置是不連續的。Linked-list 的每個元素稱為 node (節點)，每個 node 由 data 和 pointer (指標) 組成，其中又分為以下三種：

3.1 分類

3.1.1 Singly Linked-list

每個 node 的 pointer 會指向下一個 node。

3.1.2 Doubly Linked-list

每個 node 有兩個 pointer，一個指向前面的 node，另一個指向後面的 node。

3.1.3 Circular Linked-list

和 singly linked-list 一樣，每個 node 都只有一個 pointer，唯一的差別是最後一個 node 的 pointer 會指向第一個 node。

3.2 JavaScript 實作

3.2.1 node

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

3.2.2 Singly linked-list

class LinkedList {
  constructor() {
    this.head = null;
  }

  insertFirst(data) {
    this.insertAt(data, 0);
  }

  size() {
    let counter = 0;
    let node = this.head;
    while (node) {
      counter++;
      node = node.next;
    }
    return counter;
  }

  getFirst() {
    return this.getAt(0);
  }

  getLast() {
    return this.getAt(this.size() - 1);
  }

  clear() {
    this.head = null;
  }

  removeFirst() {
    if (!this.head) {
      return;
    }
    this.head = this.head.next;
  }

  removeLast() {
    if (!this.head) {
      return;
    }
    if (!this.head.next) {
      this.head = null;
      return;
    }

    let previous = this.head;
    let node = this.head.next;
    while (node.next) {
      previous = node;
      node = node.next;
    }
    previous.next = null;
  }

  insertLast(data) {
    const lastNode = this.getLast();

    if (lastNode) {
      lastNode.next = new Node(data);
    } else {
      this.head = new Node(data);
    }
  }

  getAt(index) {
    let counter = 0;
    let node = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }
      counter++;
      node = node.next;
    }
    return null;
  }

  removeAt(index) {
    if (!this.head) {
      return;
    }
    if (index === 0) {
      this.head = this.head.next;
      return;
    }
    if (index > this.size()) {
      return;
    }
    const previous = this.getAt(index - 1);
    if (!previous || !previous.next) {
      return;
    }
    previous.next = previous.next.next;
  }

  insertAt(data, index) {
    if (!this.head) {
      this.head = new Node(data);
      return;
    }
    if (index === 0) {
      this.head = new Node(data, this.head);
      return;
    }
    const previous = this.getAt(index - 1) || this.getLast();
    const node = new Node(data, previous.next);
    previous.next = node;
  }

  forEach(fn) {
    let node = this.head;
    let counter = 0;
    while (node) {
      fn(node, counter);
      node = node.next;
      counter++;
    }
  }

  *[Symbol.iterator]() {
    let node = this.head;
    while (node) {
      yield node;
      node = node.next;
    }
  }
}

3.3 時間複雜度

對 linked-list CRUD 的 time complexity (Average)

4. Linked-list, Array 比較

5. 參考資料

大話資料結構(全新彩色版)
JavaScript 學演算法
Difference between Linear and Non-linear Data Structures
Big-O Cheat Sheet
資結與演算法筆記 (1)— linked list 與 array 於O(n)之差異比較
The Coding Interview Bootcamp: Algorithms + Data Structures