萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 數據結構與算法:列表(List)抽象數據類型完整實現

列表 ADT 定義

列表是一組**有序**的資料集合,每個資料項稱為元素。JS 中列表元素可為任意型別。核心操作:

  • 屬性:listSize(元素數量)、pos(當前游標位置)、dataStore(底層陣列儲存)。
  • 方法:append、remove、find、length、toString、insert、clear、contains、游標操作(front/end/prev/next/moveTo/getElement)。

ES6 Class 完整實現

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);

複雜度分析

操作時間複雜度空間複雜度
appendO(1) 平均O(1)
remove / find / containsO(n)O(1)
insertO(n)O(1)
游標操作O(1)O(1)

適用場景與限制

  • 適合:元素數量較少(< 10,000)、頻繁插入/刪除中間位置、需要游標遍歷的場景。
  • 不適合:大量資料頻繁查找(建議用 Map/Set/索引)、高效能排序(建議用陣列 sort)、多執行緒環境(JS 單執行緒)。

擴展方向

  • 雙向鏈表實現(O(1) 插入刪除、雙向遍歷)。
  • 加入排序列表(插入時自動維持有序)。
  • 實作 ObservableList 發出變更事件,支援 MVVM 雙向綁定。
copyright © 萬盛學電腦網 all rights reserved