DIV CSS 佈局教程網

用 JavaScript 模擬 List:一個可迭代、可增刪查改的清單資料結構
編輯:關於JavaScript     

JavaScript 的陣列已經很強,但動手實作一次 List,能讓你真正搞懂「游標(cursor)」與「迭代器」是怎麼運作的。本文實作一個具備 append、insert、remove、find、contains 與位置移動能力的 List 類。

完整實作

<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>List 結構</title>
<script>
function List() {
  this.listSize = 0;      // 元素數量
  this.pos = 0;           // 游標位置
  this.dataStore = [];    // 真正存放資料的地方

  // 公開方法
  this.clear     = clear;
  this.find      = find;
  this.toString  = toString;
  this.insert    = insert;
  this.append    = append;
  this.remove    = remove;
  this.front     = front;
  this.end       = end;
  this.prev      = prev;
  this.next      = next;
  this.length    = length;
  this.currPos   = currPos;
  this.moveTo    = moveTo;
  this.getElement = getElement;
  this.contains  = contains;

  function append(element) {
    this.dataStore[this.listSize++] = element;
  }

  function find(element) {
    for (var i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) return i;
    }
    return -1;
  }

  function remove(element) {
    var foundAt = this.find(element);
    if (foundAt != -1) {
      this.dataStore.splice(foundAt, 1);
      this.listSize--;
      return element;
    }
    return false;
  }

  function length() {
    return this.listSize;
  }

  function toString() {
    return this.dataStore;
  }

  function insert(element, after) {
    var insertPos = this.find(after);
    if (insertPos != -1) {
      this.dataStore.splice(insertPos + 1, 0, element);
      this.listSize++;
      return true;
    }
    return false;
  }

  function clear() {
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = 0;
    this.pos = 0;
  }

  function contains(element) {
    for (var i = 0; i < this.dataStore.length; i++) {
      if (this.dataStore[i] === element) return true;
    }
    return false;
  }

  function front() { this.pos = 0; }
  function end()   { this.pos = this.listSize - 1; }
  function prev()  { if (this.pos > 0) --this.pos; }
  function next()  { if (this.pos < this.listSize - 1) ++this.pos; }
  function currPos() { return this.pos; }
  function moveTo(pos) { this.pos = pos; }
  function getElement() { return this.dataStore[this.pos]; }
}

var list = new List();
list.append({ name: '夏廣成', sex: '男' });
list.append({ name: '江榮盛', sex: '男' });
list.append({ name: '杜強',   sex: '男' });
list.append({ name: '巧華',   sex: '女' });
list.append({ name: '方陽',   sex: '男' });

// 用游標走訪,移除不符合條件的項目
for (list.front(); list.currPos() < list.length(); list.next()) {
  var item = list.getElement();
  if (item.sex == '女') {
    list.remove(item);
  }
}

// 再走一遍,輸出結果
for (list.front(); list.currPos() < list.length(); list.next()) {
  console.log(list.getElement().name);
}
</script>
</head>
<body>
</body>
</html>

設計重點:游標與資料分離

這個 List 有兩個獨立狀態:dataStore 存資料,pos 存「目前指到哪裡」。front()、end()、prev()、next()、moveTo() 都只動游標不動資料,getElement() 則依游標取值。

這種設計等同於 C++ STL 的迭代器概念:把「怎麼存」和「走到哪」拆開,同一份資料就能被多種遍歷方式使用。

原始程式碼裡的兩個 bug

prev 與 next 被註釋掉了邊界檢查

原本寫成:

function prev() {
  // if (this.pos > 0) { --this.pos; }
}
function next() {
  // if (this.pos < this.listSize - 1) { ++this.pos; }
}

條件判斷被註釋掉,函式實際上什麼都不做,游標永遠停在 0。這代表第二段 for 迴圈只會輸出第一筆資料。上面已修正。

remove 會讓 for 迴圈跳過元素

用 for (... ; list.next()) 搭配 splice 移除,會有一個經典陷阱:splice 之後後面的元素全部往前補位,但游標又前進了一格,於是緊接在後的那一筆被跳過。若連續兩筆都是女性,第二筆就會漏掉。安全做法是移除後不前進:

for (list.front(); list.currPos() < list.length(); ) {
  var item = list.getElement();
  if (item.sex == '女') list.remove(item);  // 移除後停留原位
  else list.next();
}

clear 的 delete 用法

原始寫法用 delete this.dataStore 再重建陣列。這能運作,但 delete 用在物件屬性上會讓該屬性脫離引擎的快取優化(物件從「有固定形狀」退化成「字典模式」),在 V8 上是明顯的效能地雷。直接赋值即可:

function clear() {
  this.dataStore = [];
  this.listSize = 0;
  this.pos = 0;
}

現代寫法對照

今天的 JavaScript 有 Symbol.iterator,可以讓自訂結構支援 for...of:

class List {
  #items = [];

  append(el) { this.#items.push(el); return this; }
  get length() { return this.#items.length; }
  remove(el) {
    const i = this.#items.indexOf(el);
    if (i > -1) this.#items.splice(i, 1);
    return this;
  }
  filter(fn) { return new List().concat(this.#items.filter(fn)); }
  concat(arr) { this.#items.push(...arr); return this; }
  map(fn) { return this.#items.map(fn); }
  toString() { return this.#items; }

  // 讓它支援 for...of
  *[Symbol.iterator]() {
    for (const item of this.#items) yield item;
  }
}

var list = new List();
[{name:'夏廣成',sex:'男'}, {name:'巧華',sex:'女'}].forEach(o => list.append(o));

for (const item of list.filter(x => x.sex !== '女')) {
  console.log(item.name);
}

用 # 私有欄位包住內部陣列,外部就無法直接繞過方法竄改資料;用 generator 實作 Symbol.iterator,就能直接 for...of、[...list]、Array.from(list)。

做這個練習的價值

實務上你大概不會自己寫 List——陣列加 map/filter/reduce 就夠了。但手做一遍會讓你明白:

  • 游標與資料分離是迭代器的核心概念,理解之後才看得懂 generator 的 yield 在暫停什麼。
  • 邊界檢查不能省——front 之前再 prev、end 之後再 next,都會讓游標跑到無效位置。
  • 邊走邊改是危險動作,這是所有集合型別的共同陷阱,不限於自製 List。

這三點,都是你遲早在真實專案裡會遇上的問題。

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