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 的迭代器概念:把「怎麼存」和「走到哪」拆開,同一份資料就能被多種遍歷方式使用。
原本寫成:
function prev() {
// if (this.pos > 0) { --this.pos; }
}
function next() {
// if (this.pos < this.listSize - 1) { ++this.pos; }
}
條件判斷被註釋掉,函式實際上什麼都不做,游標永遠停在 0。這代表第二段 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();
}
原始寫法用 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 就夠了。但手做一遍會讓你明白:
yield 在暫停什麼。front 之前再 prev、end 之後再 next,都會讓游標跑到無效位置。這三點,都是你遲早在真實專案裡會遇上的問題。