DIV CSS 佈局教程網

JavaScript 資料結構與演算法(三):鏈表
編輯:JavaScript綜合知識     

前面的佇列與堆疊都是特殊的線性表,也都屬於比較簡單的、基於陣列的順序儲存結構。由於 JavaScript 解釋器針對陣列做了大量優化,我們不會遇到許多語言中「陣列填滿後難以擴充」的問題(push、pop、shift、unshift、splice 等方法都已經包裝好了)。但順序儲存有一個根本上的限制,而鏈式儲存正是為了解它而出現的。

從順序儲存到鏈式儲存

線性表的順序儲存結構,最大的缺點是:改動其中一個元素的位置,往往會牽動整個集合。原因在於記憶體中的配置是連續而沒有間隙的,刪掉一個自然就得補位。

鏈式儲存換了個思路:我們完全不關心資料在記憶體中的排列,只需要在每個元素裡記錄「下一個資料在哪裡」即可。用鏈接方式儲存的線性表就稱為鏈表,其中每筆資料 = 資訊 + 位址。

我們把位址稱為「鏈」,一個資料單元就是一個節點,鏈表就是一串節點組成的集合,每個節點都有一個指標指向它的下一個節點。

對比就很清楚:陣列元素靠位置關係做邏輯引用,鏈表則靠每個節點保存的指標來引用。這種結構的優勢在插入與刪除時特別明顯——完全不必理會排列,只要把鏈的指向接上即可。

這樣一來,思路就不必局限在陣列上,用物件也行,只要物件之間存在引用關係即可。

常見的幾種鏈表

單鏈表:單純地往下一個傳遞,每個節點只記錄下一個節點的資訊。

靜態鏈表:用陣列描述的鏈表,陣列中每個索引都是一個「節」,包含資料與指向。

循環鏈表:單鏈表只能往後傳遞,到達尾部後要回溯到頭部很麻煩,因此把尾節的鏈接回頭節形成循環。

雙向鏈表:針對單鏈表的優化,讓每個節都知道前後是誰,除了後指標還有一個前指標,提高查找效率,代價是設計上的複雜度提升——本質上是空間換時間。

綜合來看,鏈表就是線性表中針對順序儲存的一種優化手段。而在 JavaScript 中,由於陣列會自動更新索引,我們可以用物件來做鏈式結構。

單鏈表:最基本的引用

function createLinkList() {
  var prev = null;
  return {
    add: function(val) {
      // 保存目前的引用
      prev = { data: val, next: prev || null };
    }
  };
}

var linksList = createLinkList();
linksList.add("arron1");
linksList.add("arron2");
linksList.add("arron3");
// node 的 next 鏈:-arron3- → -arron2- → -arron1

透過 node 物件的 next 直接引用下一個 node,初步實現了鏈式引用。但還有一個關鍵問題沒解決:如何動態插入資料到某個節點之後?為此必須設計一個遍歷方法,沿著鏈搜尋目標節點,找到後把新節插入並改寫指標。

// 在鏈表中找到對應的節(用 curry 手法固定起點)
var findNode = function createFindNode(currNode) {
  return function(key){
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;
  };
}(headNode);

插入節點

指標的換算關係很簡單:在 a-b-c-d 中,若要在 c(此時 c.next 指向 d)之後插入 f,結果是 a-b-c-f-d,做法是讓 c.next 指向 f,再讓 f.next 指向 d。

// 建立節
function createNode(data) {
  this.data = data;
  this.next = null;
}

// 初始化頭部節,從 headNode 開始形成一條鏈
var headNode = new createNode("head");

this.insert = function(data, key) {
  var newNode = new createNode(data);
  var current = findNode(key);
  newNode.next = current.next;   // 先接上後繼
  current.next = newNode;        // 再改寫前驅
};

這兩行的順序至關重要:必須先把新節的 next 指向原本的後繼,才不會在改寫 current.next 時把後半條鏈丟掉。

刪除節點

鏈表的特性決定了刪除方式:a→b→c→d 中要刪掉 c,就必須把 b.next 從指向 c 改成指向 d。也就是要先找到前一個節點——這有點像 DOM 操作中必須先取得父節點才能呼叫 removeChild。

// 找到前一個節
var findPrevious = function(currNode) {
  return function(key){
    while (!(currNode.next == null) && (currNode.next.data != key)) {
      currNode = currNode.next;
    }
    return currNode;
  };
}(headNode);

this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
    prevNode.next = prevNode.next.next;   // 跳過目標節
  }
};

完整可執行的單鏈表

function createLinkList() {
  function createNode(data) {
    this.data = data;
    this.next = null;
  }

  var headNode = new createNode("head");

  var findNode = function(currNode) {
    return function(key) {
      while (currNode.data != key) { currNode = currNode.next; }
      return currNode;
    };
  }(headNode);

  var findPrevious = function(currNode) {
    return function(key) {
      while (!(currNode.next == null) && (currNode.next.data != key)) {
        currNode = currNode.next;
      }
      return currNode;
    };
  }(headNode);

  this.insert = function(data, key) {
    var newNode = new createNode(data);
    var current = findNode(key);
    newNode.next = current.next;
    current.next = newNode;
  };

  this.remove = function(key) {
    var prevNode = findPrevious(key);
    if (!(prevNode.next == null)) {
      prevNode.next = prevNode.next.next;
    }
  };

  this.display = function(fn) {
    var currNode = headNode;
    while (!(currNode.next == null)) {
      currNode = currNode.next;
      fn(currNode.data);
    }
  };
}

var cities = new createLinkList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");

cities.display(function(data){ console.log(data); });
cities.remove("Russellville");

要留意的是 findNode 找不到 key 時會沿著 next 走到 null,下一輪比對就會拋出錯誤。實務上應在迴圈條件中加上 currNode != null 的檢查並回傳 null,由呼叫端決定如何處理。

雙鏈表

原理與單鏈表相同,只是每個節多了一個指向前驅的指標。

插入:

this.insert = function(data, key) {
  var newNode = new createNode(data);
  var current = findNode(headNode, key);
  newNode.next = current.next;
  newNode.previous = current;
  current.next = newNode;
};

刪除:

this.remove = function(key) {
  var currNode = findNode(headNode, key);
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next = null;
    currNode.previous = null;
  }
};

刪除時有一個明顯的優化:不需要再去找父節點,因為雙向引用讓前驅可以直接取得,效率比單鏈表高。

該用哪一種

陣列與鏈表的取捨是經典題目:陣列的隨機存取是 O(1),但插入刪除是 O(n);鏈表插入刪除是 O(1)(前提是已經找到位置),但只能循序存取,而且每個節點都多一份指標的空間成本,快取局部性也較差。

在 JavaScript 中,由於陣列底層已經足夠優秀,實務上大多不需要自己實作鏈表。真正理解它的價值在於看懂那些「指標思維」的應用:jQuery 的 deferred 鏈、React Fiber 的鏈式結構、瀏覽器 DOM 的節點樹、以及 LRU 快取常用「雜湊表 + 雙向鏈表」的組合——背後都是同一套想法。

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