DIV CSS 佈局教程網

JavaScript資料結構:鏈結串列的完整實作
編輯:關於JavaScript     

最近在看《JavaScript 資料結構與算法》這本書,想補一下資料結構方面的底子,因為一直覺得這是我的弱項。以下把鏈結串列(Linked List)的觀念與實作做個筆記。

什麼是鏈結串列

鏈結串列用來儲存「有序的元素集合」,但和陣列不同,它的元素在記憶體中並不連續。每個元素由兩部分組成:存放資料本身的節點,以及指向下一個元素的引用(也稱 pointer 或 link)。

它的好處是可以輕易地在任意位置新增或移除元素,並在需要時自然擴容,不必搬動其他元素。

與陣列的差別

・陣列:可以直接以索引存取任何位置的元素,時間複雜度 O(1)。
・鏈結串列:要存取某個元素,必須從表頭開始逐個走訪,直到找到目標,時間複雜度 O(n)。

這就是典型的空間與時間取捨:鏈結串列犧牲了隨機存取的效率,換來插入與刪除的靈活性。

完整實作

function LinkedList() {
  var Node = function (element) {
    this.element = element;
    this.next = null;
  };
  var length = 0;
  var head = null;

  // 尾端追加
  this.append = function (element) {
    var node = new Node(element);
    var current;
    if (head == null) {
      head = node; // 串列為空,直接作為表頭
    } else {
      current = head;
      while (current.next) { // 走到最後一項
        current = current.next;
      }
      current.next = node;
    }
    length++; // 更新長度
  };

  // 指定位置插入
  this.insert = function (position, element) {
    var node = new Node(element);
    var current = head;
    var previous;
    var index = 0;
    if (position >= 1 && position <= length) { // 越界檢查
      if (position === 0) {
        node.next = current; // 插入表頭
        head = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      length++;
      return true;
    } else {
      return false;
    }
  };

  // 取得元素索引
  this.indexOf = function (element) {
    var current = head;
    var index = -1;
    while (current) {
      if (element === current.element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };

  // 依位置移除
  this.removeAt = function (position) {
    if (position > -1 && position < length) {
      var current = head;
      var previous;
      var index = 0;
      if (position === 0) {
        head = current.next; // 移除第一個節點
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next; // 跳過目前節點
      }
      length--;
      return current.element;
    } else {
      return null;
    }
  };

  // 依值移除
  this.remove = function (element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

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

  this.size = function () {
    return length;
  };

  this.toString = function () {
    var current = head;
    var string = "";
    while (current) {
      string = "," + current.element;
      current = current.next;
    }
    return string.slice(1);
  };

  this.getHead = function () {
    return head;
  };
}

這份實作刻意用閉包把 Node、length、head 藏起來,只透過 this 上掛的方法對外開放,這是避免使用 ES6 class 之前的常見封裝手法。若換成 class 語法搭配 private 欄位,結構會更清楚。

另外提醒一下,書上的 indexOf 範例有個小瑕疵:起始 index 設為 -1 卻在比對之後才遞增,導致第一個節點永遠比對不到。實作時建議把 index 初始化為 0,或改成先比對 current 再前移指標的寫法。

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