列表是一組**有序**的資料集合,每個資料項稱為元素。JS 中列表元素可為任意型別。核心操作:
listSize(元素數量)、pos(當前游標位置)、dataStore(底層陣列儲存)。append、remove、find、length、toString、insert、clear、contains、游標操作(front/end/prev/next/moveTo/getElement)。class List {
constructor() {
this.dataStore = [];
this.listSize = 0;
this.pos = 0;
}
// 在列表末尾添加元素
append(element) {
this.dataStore[this.listSize++] = element;
}
// 移除首個匹配元素,成功返回 true
remove(element) {
const index = this.find(element);
if (index > -1) {
this.dataStore.splice(index, 1);
this.listSize--;
return true;
}
return false;
}
// 查找元素索引,找不到返回 -1
find(element) {
for (let i = 0; i < this.dataStore.length; i++) {
if (this.dataStore[i] === element) return i;
}
return -1;
}
length() { return this.listSize; }
toString() { return this.dataStore.join(', '); }
// 在 existingElement 後插入新元素
insert(element, existingElement) {
const index = this.find(existingElement);
if (index > -1) {
this.dataStore.splice(index + 1, 0, element);
this.listSize++;
return true;
}
return false;
}
clear() {
this.dataStore = [];
this.listSize = this.pos = 0;
}
contains(element) {
return this.dataStore.includes(element);
}
// 游標操作
front() { this.pos = 0; }
end() { this.pos = this.listSize - 1; }
prev() { if (this.pos > 0) this.pos--; }
next() { if (this.pos < this.listSize - 1) this.pos++; }
curPos() { return this.pos; }
moveTo(position) { this.pos = position; }
getElement() { return this.dataStore[this.pos]; }
// 迭代器支援(ES6)
*[Symbol.iterator]() {
for (const item of this.dataStore) yield item;
}
}
const list = new List();
list.append('Apple');
list.append('Banana');
list.append('Cherry');
console.log(list.toString()); // Apple, Banana, Cherry
list.insert('Blueberry', 'Banana');
console.log(list.toString()); // Apple, Banana, Blueberry, Cherry
list.front();
console.log(list.getElement()); // Apple
list.next();
console.log(list.getElement()); // Banana
list.remove('Banana');
console.log(list.length()); // 3
console.log(list.contains('Blueberry')); // true
// 使用 for...of 迭代
for (const fruit of list) console.log(fruit);
| 操作 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| append | O(1) 平均 | O(1) |
| remove / find / contains | O(n) | O(1) |
| insert | O(n) | O(1) |
| 游標操作 | O(1) | O(1) |
sort)、多執行緒環境(JS 單執行緒)。ObservableList 發出變更事件,支援 MVVM 雙向綁定。