鏈結串列（Linked List)

June 23, 2019

有序的元素集合
不同於陣列，鏈結串列中的元素在記憶體中並不是連續（Sequential）放置的
每個節點（Node）元素由一個存放元素本身資料（Data）和一個指向下一個元素的指標鏈結（Next Pointer）組成
如同火車一般的結構

與陣列 (Array) 的比較

陣列（Array）優點：

可支援循序及隨機存取
可靠度高，不會因為鏈結斷裂而遺失資料
循序存取速度快

陣列（Array）缺點：

因占用連續的記憶體空間可能會浪費不必要之記憶體
刪除或插入新元素造成資料移動頻繁（在大多數程式語言中陣列大小是固定的）
各元素型態皆相同
不支援串列之共享

鏈結串列（Linked List）優點：

元素在記憶體中可以非連續
方便動態刪除或插入新元素
各節點資料型態不必一定相同
支援串列之共享

鏈結串列（Linked List）缺點：

僅支援循序存取
指標斷裂，資料就遺失
循序存取速度慢，因需要先讀取指標

Implementation

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

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

  append(element) {
    const node = new Node(element);

    if (this.head === null) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }

    this.length++;
  }

  insert(position, element) {
    if (position < 0 || position >= this.length) {
      return null;
    }

    const node = new Node(element);

    let current = this.head;
    if (position === 0) {
      this.head = node;
      this.head.next = current;
    } else {
      let previous = null;
      let index = 0;
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }

      previous.next = node;
      node.next = current;
    }

    this.length++;
  }

  removeAt(position) {
    if (position < 0 || position >= this.length) {
      return null;
    }

    let current = this.head;
    if (position === 0) {
      this.head = current.next;
    } else {
      let index = 0;
      let previous = null;
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = current.next;

      return current.element;
    }
    this.length--;
  }

  remove(element) {
    const index = this.indexOf(element);
    this.removeAt(index);
  }

  indexOf(element) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.element === element) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }

  toString() {
    let current = this.head;
    const elements = [];

    while (current) {
      elements.push(current.element);
      current = current.next;
    }

    return elements.join(" ");
  }

  getHead() {
    return this.head;
  }
}