DIV CSS 佈局教程網

用 JavaScript 實現鏈表:Node 與 LList 類的完整封裝
編輯:JavaScript技巧     

鏈表(Linked list)是一種常見的基礎數據結構。它屬於線性表,但不同於數組那樣按順序在內存中排列,而是把數據分散存放在各個節點裡,每個節點通過指針指向下一個節點。這種結構的好處是插入和刪除不需要搬移大量元素。

下面用 JavaScript 完整實現一個單鏈表。

Node 類:表示一個節點

/**
 * Node 類用來表示節點
 * element 用來保存節點上的數據
 * next 用來保存指向下一個節點的鏈接
 */
function Node(element) {
  this.element = element;
  this.next = null;
}

LList 類:鏈表操作

/**
 * LList 類提供了對鏈表進行操作的方法
 * 鏈表只有一個屬性,使用一個 Node 對象保存頭節點
 */
class LList {
  constructor() {
    this.head = new Node('head');
  }

  // 查找指定數據的節點
  find(item) {
    let currNode = this.head;
    while (currNode.element !== item) {
      currNode = currNode.next;
    }
    return currNode;
  }

  // 查找指定節點的前一個節點
  findPre(item) {
    if (item === 'head') throw new Error('now is head!');
    let currNode = this.head;
    while (currNode.next && currNode.next.element !== item) {
      currNode = currNode.next;
    }
    return currNode;
  }

  // 在 item 之後插入新節點
  insert(newElement, item) {
    let newNode = new Node(newElement);
    let currNode = this.find(item);
    newNode.next = currNode.next;
    currNode.next = newNode;
  }

  // 刪除指定節點
  remove(item) {
    let preNode = this.findPre(item);
    if (preNode.next !== null) {
      preNode.next = preNode.next.next;
    }
  }

  // 遍歷顯示鏈表中的元素
  display() {
    let currNode = this.head;
    while (currNode.next !== null) {
      console.log(currNode.next.element);
      currNode = currNode.next;
    }
  }
}

幾個設計要點值得說明。鏈表構造時會預置一個 element 為 'head' 的頭節點,它不存業務數據,作用是簡化插入刪除的邊界判斷。插入操作必須先接新節點的 next,再改原節點的 next,順序顛倒會丟失後續鏈路。刪除則需要先找到前驅節點,靠「前驅.next = 前驅.next.next」跳過目標——這也是很多鏈表題目需要引入虛擬頭結點的原因。

測試代碼

const list = new LList();
// LList { head: Node { element: 'head', next: null } }

list.insert('0', 'head');
list.insert('1', '0');
list.insert('2', '1');
list.insert('3', '2');

list.remove('1');

console.log(list);
// LList { head: Node { element: 'head', next: Node { element: '0', next: [Object] } } }

console.log(list.display()); // 依次輸出 0 2 3

console.log(list.findPre('1'));
// Node { element: '0', next: Node { element: '1', next: ... } }

注意上面 findPre('1') 是在 remove 之後調用的,此時鏈表中已無 element 為 '1' 的節點,循環會一直走到尾部,這是示例代碼在查找失敗時缺少終止條件的表現。

總結

這份實現覆蓋了鏈表最核心的四個操作:find、findPre、insert、remove,再加上一個遍歷用的 display。真實場景中還需要補充幾處健壯性:查找失敗時返回 null 而不是 undefined、空鏈表判斷、以及循環鏈表的檢測。但作為理解指針操作的一份最小骨架,它已經足夠清晰——鏈表的全部奧妙,就在那幾行 next 賦值的先後順序裡。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved