DIV CSS 佈局教程網

JavaScript 資料結構與算法之鏈表
編輯:JavaScript基礎知識     

鏈表簡介

鏈表是一種常見的資料結構,也屬於線性表,但不會按線性的順序來儲存資料,而是在每一個節點中儲存了指向下一個節點的指標。使用鏈表結構可以克服陣列需要預先知道資料大小的缺點,能充分利用記憶體空間,實現靈活的動態記憶體管理。接下來介紹單向鏈表與雙向鏈表在 JavaScript 中的實現。

單向鏈表

鏈表中最簡單的形式就是單向鏈表。鏈表中的每個節點都包含兩個部分:第一部分儲存自身資訊,第二部分則儲存指向下一節點的指標,最後一個節點指向 NULL。

首先建立一個構造函式:

/**
 * 單向鏈表構造函式
 */
function LinkedList() {
  /**
   * 單向鏈表中節點的構造函式
   * @param {Any} element 要傳入鏈表的節點
   */
  var Node = function(element) {
    this.element = element;
    this.next = null;   // 下個節點的地址
  }
  var length = 0;       // 鏈表長度
  var head = null;      // 頭節點,初始化為 NULL
}

單向鏈表需要具備 append、insert、indexOf、remove、removeAt、getHead、isEmpty、toString、size 等方法。

雙向鏈表

雙向鏈表的每個節點除了指向下一節點外,還有一個指向前一節點的指標,因此需要同時維護 head 與 tail。它需要具備 insert、removeAt、showHead、showLength、showTail 等方法。

append 方法

向鏈表尾部添加元素:

this.append = function(element) {
  var node = new Node(element);
  if (head === null) {
    head = node;
    tail = node;
  } else {
    var current = head;
    while (current.next) {
      current = current.next;
    }
    current.next = node;
    node.prev = current;
    tail = node;
  }
  length++;
  return node;
};

insert 方法

向雙向鏈表中某個位置插入元素:

this.insert = function(position, element) {
  if (position >= 0 && position <= length) {
    var node = new Node(element);
    var index = 0;
    var previous;
    var current = head;
    if (position === 0) {
      if (head === null) {
        head = node;
        tail = node;
      } else {
        current.prev = node;
        node.next = current;
        head = node;
      }
    } else if (position === length) {
      current = tail;
      current.next = node;
      node.prev = current;
      tail = node;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = node;
      node.prev = previous;
      current.prev = node;
      node.next = current;
    }
    length++;
    return true;
  } else {
    return false;
  }
};

removeAt 方法

移除雙向鏈表中某個位置的元素:

this.removeAt = function(position) {
  if (position > -1 && position < length) {
    var current = head;
    var index = 0;
    var previous;
    if (position === 0) {
      head = current.next;
      if (length === 1) {
        tail = null;
        head.prev = null;
      }
    } else if (position === length - 1) {
      current = tail;
      tail = current.prev;
      tail.next = null;
    } else {
      while (index++ < position) {
        previous = current.prev;
        current = current.next;
      }
      previous.next = current.next;
      current.next.prev = previous;
    }
    length--;
    return current.element;
  } else {
    return false;
  }
};

showHead、showLength、showTail 方法

this.showHead = function() {
  return head;
};
this.showLength = function() {
  return length;
};
this.showTail = function() {
  return tail;
};

感想

鏈表這一節,基本都是先按需求寫程式碼,寫完後再和書上對比,發現被瞬間秒成渣——自己寫的很多暗坑,邏輯也很混亂。看來還是學藝不精,需要多加練習。

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