列表是我們日常生活中最常接觸的資料結構——購物前列的清單、考試後公布的排名榜,都是列表。在程式設計裡,列表也是入門資料結構的第一站。本文從抽象資料型別的定義出發,一步步實作一個完整的 List 類別。
當元素數量不多時,列表是很好的選擇:查找與排序的效率都還算不錯。反之,若資料量極大,就該考慮樹、雜湊表或資料庫等更合適的結構了。
設計抽象資料型別前,得先想清楚它該有哪些屬性、能做哪些操作。列表是一組有序的資料,每個成員稱為元素。在 JavaScript 中元素可以是任意型別,數量也沒有硬性上限,實際上只受程式記憶體限制。
依此,我們需要三個屬性:
1. listSize:目前列表中的元素個數。
2. pos:當前位置,也就是元素的索引。
3. dataStore:一個空陣列,用來實際存放元素。要取出目前位置的元素,寫成 dataStore[pos] 即可。
方法則如下表所示:

以下採用「建構函數 + 原型」的經典組合來實作:
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 語法。真正理解列表之後,再往堆疊與佇列推進,就會發現它們其實都是列表的特例——只是限制了存取的位置。