閱讀《資料結構與演算法 JavaScript 描述 第二版》之列表

語言: CN / TW / HK

列表的抽象資料型別定義

  • 一組有序的資料。
  • 列表中每一項稱之為元素
  • 不包含元素的列表稱之為空列表
  • 列表有前後(prev/next)
  • 有移動的概念 moveTo
  • 迭代設計方法

與書本上不同的是,我們使用原型進行實現, 也就是 List 資料結構的所有方法掛載到 List 的原型上,當然只是實現了基本功能,沒有程式設計邊界處理。

實現列表類 List

  • List 類

js function List() { this.listSize = 0; this.pos = 0; this.dataStore = []; } 看起 看,其是一個簡單版本的 List 列表,就是三個屬性,下面就是定義操作這三個屬性了。

  • 屬性:listSize 列表長度

js List.prototype.length = function() { return this.dataStore; }

  • 屬性: length 長度

js List.prototype.length = function() { return this.dataStore; }

  • 方法:append 新增一個元素到列表中

js // 新增一個元素 List.prototype.append = function(element) { this.dataStore[this.listSize++] = element; }

  • 方法:find 查詢一個元素的位置

```js List.prototype.find = function(element) { for( let i = 0; i < this.dataStore.length; ++i) { if(this.dataStore[i] == element) { return i } }

return -1; } ```

  • 方法:remove 一個函式

```js List.prototype.remove = function(element) { let foundAt = this.find(element);

if(foundAt > -1) { this.dataStore.splice(foundAt, 1); --this.listSize; return true; } return false } ```

  • 方法:在指定位置(after) 插入元素 element

```js List.prototype.insert = function (element, after) { let insertPos = this.find(after);

if (insertPos > -1) { this.dataStore.splice(insertPos + 1, 0, element); ++this.listSize; return true; }

return false; }; ```

  • 方法:clear 清空資料

js List.prototype.clear = function() { delete this.dataStore; this.dataStore.length = 0; this.listSize = this.pos = 0; }

  • 方法:contains 判斷給定值是否在列表中

```js List.prototype.contains = function (element) { for (let i = 0; i < this.dataStore.length; ++i) { if (this.dataStore[i] == element) { return true; } }

return false; }; ```

使用迭代器訪問列表

  • 方法:front 節點 pos 放在 start 位置

js List.prototype.front = function() { this.pos = 0; }

  • 方法:end 節點 pos 放在 end 位置

js List.prototype.end = function() { this.pos = this.listSize - 1; }

  • 方法:prev 節點 pos 位置前移一個位置

js List.prototype.prev = function () { --this.pos; };

  • 方法:next 節點 pos 位置後移一個位置

js List.prototype.next = function () { if (this.pos < this.listSize) { ++this.pos; } };

  • 方法: currPos 節點當前位置

js List.prototype.currPos = function () { return this.pos }

  • 方法: moveTo 移動到當前節點

js List.prototype.moveTo = function (position) { this.pos = position }

  • 方法:getElement 獲取指定元素 this.pos

js List.prototype.getElement = function () { return this.dataStore[this.pos] }

  • 方法:有下一個

js ist.prototype.hasNext = function() { return this.pos < this.listSize }

  • 方法:有上一個

js List.prototype.hasPrev = function() { return this.pos >= 0 }

其實這些行為就是一個迭代器的概念。

小結

  • 列表與陣列的類似,但是列表不是內建支援,這裡使用 JS 原型 + 閱讀有各種實用方法的實現。
  • 這裡沒有展示使用例項,熟悉 資料結構 api 的基本設計。
  • 理解 JavaScript 原型鏈程式設計,以及列表的迭代 api 設計。