DIV CSS 佈局教程網

JavaScript 資料結構與演算法:列表(List)的抽象定義與實作
編輯:JavaScript綜合知識     

列表是我們日常生活中最常接觸的資料結構——購物前列的清單、考試後公布的排名榜,都是列表。在程式設計裡,列表也是入門資料結構的第一站。本文從抽象資料型別的定義出發,一步步實作一個完整的 List 類別。

列表適合用在什麼場合

當元素數量不多時,列表是很好的選擇:查找與排序的效率都還算不錯。反之,若資料量極大,就該考慮樹、雜湊表或資料庫等更合適的結構了。

一、抽象資料型別的定義

設計抽象資料型別前,得先想清楚它該有哪些屬性、能做哪些操作。列表是一組有序的資料,每個成員稱為元素。在 JavaScript 中元素可以是任意型別,數量也沒有硬性上限,實際上只受程式記憶體限制。

依此,我們需要三個屬性:

1. listSize:目前列表中的元素個數。
2. pos:當前位置,也就是元素的索引。
3. dataStore:一個空陣列,用來實際存放元素。要取出目前位置的元素,寫成 dataStore[pos] 即可。

方法則如下表所示:

二、實作 List 類別

以下採用「建構函數 + 原型」的經典組合來實作:

function List() {
  // 列表的元素個數
  this.listSize = 0;
  // 列表的當前位置
  this.pos = 0;
  // 初始化空陣列保存列表元素
  this.dataStore = [];
}

List.prototype = {

  // 在列表末尾添加元素
  append: function(element) {
    var self = this;
    self.dataStore[this.listSize++] = element;
  },

  // 從列表中刪除元素
  remove: function(element) {
    var self = this;
    var curIndex = self.find(element);
    if(curIndex > -1) {
      self.dataStore.splice(curIndex, 1);
      --self.listSize;
      return true;
    }
    return false;
  },

  // 查找元素並回傳索引,找不到回傳 -1
  find: function(element) {
    var self = this;
    for(var i = 0, dataLen = self.dataStore.length; i < dataLen; i++) {
      if(self.dataStore[i] == element) return i;
    }
    return -1;
  },

  // 回傳列表元素個數
  length: function() {
    return this.listSize;
  },

  // 顯示列表中的元素
  toString: function(){
    return this.dataStore;
  },

  // 在指定元素後面插入一個元素
  insert: function(element, elementAfter){
    var self = this;
    var insertPos = self.find(elementAfter);
    if(insertPos > -1) {
      self.dataStore.splice(insertPos + 1, 0, element);
      ++self.listSize;
      return true;
    }
    return false;
  },

  // 清空列表
  clear: function() {
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = this.pos = 0;
  },

  // 判斷元素是否在列表中
  contains: function(element) {
    var self = this;
    for(var i = 0, ilen = self.dataStore.length; i < ilen; i++) {
      if(self.dataStore[i] == element) return true;
    }
    return false;
  },

  // 把當前位置移到第一個
  front: function(){
    this.pos = 0;
  },

  // 把當前位置移到最后一個
  end: function(){
    this.pos = this.listSize - 1;
  },

  // 當前位置前移一位
  prev: function(){
    if(this.pos > 0) --this.pos;
  },

  // 當前位置後移一位
  next: function(){
    if(this.pos < this.listSize - 1) ++this.pos;
  },

  // 回傳當前位置
  curPos: function(){
    return this.pos;
  },

  // 移動到指定位置
  moveTo: function(n) {
    this.pos = n;
  },

  // 回傳當前位置的元素
  getElement: function(){
    return this.dataStore[this.pos];
  }
};

設計思路重點

這個實作最值得學習的不是某個方法的寫法,而是「屬性 + 方法」的切分方式:listSize 讓我們不必每次都去問陣列長度,pos 則把「游標」這個概念獨立出來,使得 front、end、prev、next、moveTo 這一族走訪方法可以共用同一份狀態。

另外可以留意幾個細節:find() 與 contains() 都在迴圈前先把 length 存成區域變數,避免每次迭代都重新取值;insert() 用 splice 的第三個參數完成插入,比手寫搬移優雅得多;clear() 先 delete 再重建陣列,確保外部若持有舊參照不會誤用。

如果要在這個基礎上擴充,可以加上 sort()、以及基於 pos 的迭代器方法,讓列表能直接對應 for...of 語法。真正理解列表之後,再往堆疊與佇列推進,就會發現它們其實都是列表的特例——只是限制了存取的位置。

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