Js 鏈表詳解

一、什麼是鏈表

鏈表是一種經典的數據結構，常用於實現棧、隊列、哈希表、LRU算法等。它由一系列結點組成，每個結點都包含指向下一個結點的指針，最後一個結點的指針指向空。相較於數組，鏈表可以更加靈活地插入、刪除元素，但是需要更多的空間來存儲指針。

二、實現鏈表

下面是一個簡單的鏈表實現。

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

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

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

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

    this.length++;
  }

  insert(data, position) {
    if (position  this.length) {
      return false;
    }

    const node = new Node(data);

    if (position === 0) {
      node.next = this.head;
      this.head = node;
    } else if (position === this.length) {
      this.tail.next = node;
      this.tail = node;
    } else {
      let current = this.head;
      let prev = null;
      let index = 0;

      while (index < position) {
        prev = current;
        current = current.next;
        index++;
      }

      node.next = current;
      prev.next = node;
    }

    this.length++;

    return true;
  }

  removeAt(position) {
    if (position = this.length) {
      return null;
    }

    let current = this.head;

    if (position === 0) {
      this.head = current.next;

      if (this.length === 1) {
        this.tail = null;
      }
    } else {
      let prev = null;
      let index = 0;

      while (index < position) {
        prev = current;
        current = current.next;
        index++;
      }

      prev.next = current.next;

      if (position === this.length - 1) {
        this.tail = prev;
      }
    }

    this.length--;

    return current.data;
  }
}

上面的代碼實現了鏈表的常見操作：追加元素、插入元素、刪除元素。需要注意的是，由於JS語言的特性，使用鏈表需要手動釋放內存空間，否則可能會產生內存泄漏。

三、鏈表的使用場景

鏈表主要用於需要頻繁刪除、插入元素的場景。比如，在LRU算法中，當頁面被訪問時，需要將其移到最前面。實現方法是使用鏈表，每次訪問時，將該頁面的結點從原位置刪除，然後追加到鏈表頭部，這樣，最近被訪問的頁面就總是在前面。

四、鏈表的性能分析

鏈表的時間複雜度為O(n)，並且需要更多的內存來存儲指針。使用鏈表需要根據實際情況來選擇，比如，在需要隨機訪問元素的情況下，數組的性能更優。

五、總結

鏈表是經典的數據結構，常用於實現棧、隊列、哈希表、LRU算法等。它由一系列結點組成，每個結點都包含指向下一個結點的指針，最後一個結點的指針指向空。相較於數組，鏈表可以更加靈活地插入、刪除元素，但是需要更多的空間來存儲指針。

上面的代碼實現了鏈表的常見操作：追加元素、插入元素、刪除元素。使用鏈表需要手動釋放內存空間，否則可能會產生內存泄漏。鏈表的時間複雜度為O(n)，並且需要更多的內存來存儲指針。使用鏈表需要根據實際情況來選擇，比如，在需要隨機訪問元素的情況下，數組的性能更優。