前言:日常生活中我們經常使用列表。去購物前列下要買的東西,考完試後學校公布成績排名,這些都是列表。電腦裡同樣大量使用列表。那麼列表適合用在什麼場合,又不適合用在什麼場合?
答案是:當列表元素數量不多時很合適,因為對列表中的元素進行查找或排序時效率還算不錯;反之,元素數量龐大時就不適合了,這時該考慮雜湊表、樹或其他結構。
要設計列表的抽象資料型別,得先想清楚它應該具備哪些屬性、支援哪些操作。
列表是一組有序的資料,每個資料項稱為元素。在 JavaScript 中,列表元素可以是任意資料型別,且元素數量沒有事先約定,實際上限只受程式記憶體限制。
基于此,我們可以規劃出三個屬性:
listSize:保存列表中元素的個數。pos:列表的目前位置,也就是目前元素的索引。dataStore:初始化一個空陣列來保存元素;搭配 pos 即可取出目前元素,寫成 dataStore[pos]。方法則包含 append、remove、find、length、toString、insert、clear、contains,以及一組游標操作 front、end、prev、next、curPos、moveTo、getElement。

依據上述定義,我們可以用「建構函式 + 原型」的模式實作出 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;
},
// 查找列表中的元素,回傳索引
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;
},
/*
* 在指定元素後面插入一個元素
* @param element 要插入的元素
* @param elementAfter 插入到哪個元素之後
*/
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];
}
};
這個實作把「資料存放」與「游標位置」分開管理,因此 pos 可以獨立移動而不影響資料本身,這正是列表能靈活遍歷的原因。其中 find 採的是線性搜尋,時間複雜度 O(n),這也解釋了為何列表不適合大量資料——若元素必須保持有序且需頻繁查找,改用二分搜尋或哈希結構會快得多。
另外,contains 與 find 邏輯幾乎相同,實作上可以讓 contains 直接呼叫 find(element) > -1 來消除重複程式碼。掌握這種「先定義抽象型別、再逐步實作方法」的思維方式,比記住某個具體結構更有價值——之後設計自己的抽象類別時,就能沿用好習慣。