萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 實現鏈表數據結構:節點定義、增刪改查、冒泡排序完整代碼

鏈表是基礎數據結構,JS 中通過對象引用模擬指針實現。本文展示單向鏈表完整實現:節點類、鏈表類、冒泡排序、繼承擴展。

核心代碼

// 1. 節點類
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// 2. 基礎鏈表類
class LinkedList {
  constructor() {
    this.head = null;
    this.current = null;
  }

  // 头插法添加
  addHead(data) {
    const node = new Node(data);
    node.next = this.head;
    this.head = node;
  }

  // 尾插法添加
  append(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
      return;
    }
    let cur = this.head;
    while (cur.next) cur = cur.next;
    cur.next = node;
  }

  // 打印所有節點
  print() {
    let cur = this.head;
    while (cur) {
      console.log(cur.data);
      cur = cur.next;
    }
  }

  // 查找節點
  find(data) {
    let cur = this.head;
    while (cur) {
      if (cur.data === data) return cur;
      cur = cur.next;
    }
    return null;
  }

  // 刪除節點
  remove(data) {
    if (!this.head) return false;
    if (this.head.data === data) {
      this.head = this.head.next;
      return true;
    }
    let cur = this.head;
    while (cur.next) {
      if (cur.next.data === data) {
        cur.next = cur.next.next;
        return true;
      }
      cur = cur.next;
    }
    return false;
  }

  // 獲取長度
  get size() {
    let count = 0, cur = this.head;
    while (cur) { count++; cur = cur.next; }
    return count;
  }
}

// 3. 可排序鏈表(繼承 + 冒泡排序)
class SortableList extends LinkedList {
  bubbleSort() {
    if (!this.head || !this.head.next) return;
    
    let swapped;
    do {
      swapped = false;
      let prev = null;
      let cur = this.head;
      
      while (cur.next) {
        if (cur.data > cur.next.data) {
          // 交換節點
          const next = cur.next;
          cur.next = next.next;
          next.next = cur;
          
          if (prev === null) {
            this.head = next;
          } else {
            prev.next = next;
          }
          prev = next;
          swapped = true;
        } else {
          prev = cur;
          cur = cur.next;
        }
      }
    } while (swapped);
  }
}

// 4. 測試
const list = new SortableList();
[4, 2, 5, 1, 3].forEach(v => list.addHead(v)); // 头插逆序
console.log('排序前:'); list.print(); // 3,1,5,2,4
list.bubbleSort();
console.log('排序後:'); list.print(); // 1,2,3,4,5

關鍵點解析

  1. 節點交換 vs 數值交換:鏈表排序通常交換節點指針而非數值,保持節點身份不變(若節點有其他引用)。
  2. 頭插法 vs 尾插法:頭插 O(1) 但逆序;尾插 O(n) 保持順序,可加 tail 指針優化為 O(1)。
  3. 冒泡排序適合鏈表:只需相鄰比較交換,無需隨機訪問,空間 O(1)。
  4. ES6 Class 繼承:extends 實現代碼復用,SortableList 繼承所有基礎操作。

擴展方向

  • 雙向鏈表:添加 prev 指針,支持雙向遍歷、O(1) 刪除已知節點。
  • 循環鏈表:尾節點指向頭節點,適用於輪該調度。
  • 跳表:多層索引,查找 O(log n),Redis 有序集合底層結構。

總結

JS 實現鏈表展示了引用機制模擬指針的能力。理解節點操作、指針交換、遞歸/迭代遍歷,是掌握數據結構與算法的關鍵一步。實際工程中數組性能通常更優(緩存友好),但鏈表在頻繁頭部插刪、不可變數據結構、函數式編程中仍有優勢。

copyright © 萬盛學電腦網 all rights reserved