## 前言在日常生活中，我们经常会用到列表： - 代办事项列表 - 购物清单 - 十佳榜单 - 等等... 在计算机程序当中也会使用到列表去做一些事情，例如：**当不需要在一个很长的序列中查找元素，或者对其进行排序是，列表显得尤为有用。反之，如果数据结构非常复杂，列表就没那么大用途了** 本文会创建一个简单的列表类，对列表的抽象数据定义，然后实现抽象数据类型(ADT) ## 列表数据的定义列表是一组有序的数据。每个列表中的数据被称为*元素*，可以是任何数据类型。列表对长度并没有事先限定，但是在实际使用时*元素*的数量会收到程序的显示。不包含任何元素的列表称之为**空列表** 在我们实现一个列表类的时候，我们应该去考虑两个问题一个列表应该需要那些属性，可以在列表上执行那些操作？包含的属性 - `listSize`: 一个列表的长度 - `pos`: 列表当前位置 - `length`: 返回列表元素中元素的个数可以做的操作 - `append`: 在列表末尾追加一个元素 - `insert`: 在某个元素后插入一个元素 - `remove`: 删除列表某一个元素 - `clear`: 清空列表中所有元素 - `toString`: 显示列表中的所有元素 - `getElement`: 显示当前元素 - `front`: 将列表的当前位置移动到第一个元素 - `end`: 将列表的当前位置移动到最后一个元素 - `prev`: 当前位置向后移一位 - `next`: 当前位置向前移一位 - `hasNext`: 判断是否有后一位 - `hasPrev`: 判断是否有前一位 - `currPos`: 返回列表的当前位置 - `moveTo`: 将当前位置移动到指定位置那我们了解到了上面列表的定义，我们要开始实现这个列表了 ## 实现列表类根据上面定义的属性及方法，我们可以直接实现一个 `list` 类。让我们开始定义这个 `list` 类吧 ```js class List { constructor() { this.listSize = 0 this.pos = 0 this.dataStore = [] // 初始化一个空数组来保存列表元素 } } const list = new List() ``` 这样我们就定一个一个简单的列表类，接下来我们需要给他再添加一个方法，使这个列表更加完整 ## append: 给列表添加元素我们要实现的第一个方法 `append()` 我们需要考虑两个问题 1. 这个方法往哪里追加 2. 我追加成功之后应该做什么 ```js class List { constructor() {...} append(element) { // element 需要追加的原序 // element 需要追加到 dataStroe 中的元素 // listSize 当前列表长度 this.dataStore[this.listSize++] = element } } const list = new List() list.append('append') console.log(list.dataStore) // [ 'append' ] ``` 当 `append` 追加的新元素成功后，变量 `listSize` 加 1。 ## remove：从列表中删除某个元素 - find: 在列表中查找某一项 `remove()` 方法是 `cList` 类中比较难实现的一个方法。同理，我们在实现之前，需要先去考虑这个怎么去实现 1. 我们如何去找到需要删除的那个元素 2. 我们应该怎么去删除他，并且填补被删除元素的空位 ```js class List { constructor() { ... } append(element) { ... } // 因为需要找到当前元素，我们先实现 find() 方法 find(element) { // 循环遍历当前 dataStore 中的每一项查找到当前被查找元素的下标类似于，反之返回 -1 // 有点类似 indexOf() findIndex() 方法 for(let i = 0; i < this.dataStore.length; i++) { if(this.dataStore[i] === element) { return i } } return -1 } // 既然第一步我们实现了，我们开始实现第二步，如何删除，并且填补被删除元素的空位 splice() 可以帮我们 remove(element) { // 通过 find() 方法对 dataStore 进行遍历，找到下标 const index = this.find(element) if(index > -1) { this.dataStore.splice(index, 1); --this.listSize // 这里因为 dataStore 长度发生了改变，变量 listSize 也应该减 1 以获取当前列表最新的长度 // 删除成功返回 true 反之返回 false return true } return false } } ``` ## length: 列表中有多少个元素 `length()` 返回列表元素中元素的个数 ```js class List { constructor() { ... } append(element) { ... } find(element) { ... } remove(element) { ... } length() { return this.listSize } } ``` ## toString: 显示列表中的元素 `toString()` 方法是用来显示列表中的元素 ```js class List { constructor() { ... } append(element) { ... } find(element) { ... } remove(element) { ... } length() { ... } toString() { return this.dataStore } } ``` 严格来说，该方法返回的是一个**数组**，而不是**字符串**，它的目的是为了显示列表当前的状态，因此返回 `dataStore` 就足够了 ## insert: 像列表中插入一个元素当前的这个 `insert` 方法我们应该想一下他的作用，想某一个元素的后一位或者列表首位插入一个元素应该考虑什么问题？ 1. 如何知道将元素插入到什么位置 ```js class List { constructor() { ... } append(element) { ... } find(element) { ... } remove(element) { ... } length() { ... } toString() { ... } insert(element, after) { // after 元素需要插入到谁之后 const insertIndex = this.find(after) // 判断 after 是否在该列表中 if(insertIndex > -1) { // 通过 splice 截取 // insertIndex + 1 需要插入到元素之后 this.dataStore.splice(insertIndex + 1, 0, element) ++this.listSize return true } return false } } ``` 当前 `insert()` 方法实现中，用到了 `find()` 方法，`find()` 方法会查找 `after` 参数在列表内的位置，找到后使用 `splice()` 将新元素成功插入该位置之后，然后将变量 `listSize` 加一并返回 `true` ## clear: 清空列表中所有元素 ```js class List { constructor() { ... } append(element) { ... } find(element) { ... } remove(element) { ... } length() { ... } toString() { ... } insert(element, after) { ... } clear() { delete this.dataStore this.dataStore = [] this.listSize = 0 this.pos = 0 } } ``` `clear()` 方法是用 `delete` 操作符删除 `dataStore`, 接着再创建一个空数组。说白了就是重置列表 ## contains: 判断给定值是否在列表中当需要判断一个给定值是否在列表中时，`contains()` 方法就会变得很有用。该方法与 `find()` 方法逻辑一样，只是 `find()` 方法返回下标，`contains()` 返回 `true` or `false` ```js class List { constructor() { ... } append(element) { ... } find(element) { ... } remove(element) { ... } length() { ... } toString() { ... } insert(element, after) { ... } clear() { ... } contains(element) { for(let i = 0; i < this.dataStore.length; i++) { if(this.dataStore[i] === element) { return true } } return false } } ``` ## 遍历列表最后一组方法允许用户在列表上自由移动，最后一个方法 `getElement()` 返回列表的当前元素 ```js class List { constructor() { ... } append(element) { ... } find(element) { ... } remove(element) { ... } length() { ... } toString() { ... } insert(element, after) { ... } clear() { ... } contains(element) { ... } front() { return this.pos = 0 } end() { this.pos = this.listSize - 1 } prev() { --this.pos } next() { if(this.pos < this.listSize) { ++this.pos } } currpos() { return this.pos } moveTo(position) { this.pos = position } getElement() { return this.dataStore[this.pos] } hasNext() { return this.pos < this.listSize } hasPrev() { return this.pos >= 0 } } ``` 让我们创建一个由姓名组成的列表，来展示怎么使用这些方法 ```js const names = new List() names.append('Wei') names.append('Jiang') names.append('Zhang') names.append('Hou') // 移动列表中的第一个元素并且显示它 names.front() // 0 console.log(names.getElement()) // Wei // 接下来向前移动一个单位并且显示它 names.next() console.log(names.getElement()) // Jiang // 向前移动两次，向后移动一次，显示当前元素 names.next() names.next() names.prev() console.log(names.getElement()) // Zhang ``` 上面代码展示的这些行为时迭代器的概念，也是我们接下来要讨论的。 ## 使用迭代器访问元素使用迭代器，可以不必关心数据内部存储方式，以实现对列表的遍历。前面提到的方法 `front()` 、`end()` 、`prev()` 、`next()` 和 `currPos()` 就实现了 `cList` 类的一个迭代器。以下是和使用数组索引的方式相比，使用迭代器的一些优点。 - 访问列表元素时不必关心底层的数据存储结构 - 当为列表添加一个元素时，索引的值就不对了，此时只有更新列表，而不用更新迭代器 - 可以用不同类型的数据存储方式实现 `cList` 类，迭代器为访问列表里的元素提供了一种统一的方式了解这些优点后，来看一个使用迭代器遍历列表的例子 ```js for (names.front(); names.hasNext(); names.next()) { console.log(names.getElement()) } ``` 在 `for` 循环的一开始，将列表的当前位置设为第一个元素。只要 `currPos` 的值小于列表的长度，就会一直循环，每一次循环都会调用 `next()` 方法将当前位置向前移动一位。同理，还可以从后向前遍历列表，代码如下 ```js for (names.end(); names.hasNext(); names.prev()) { console.log(names.getElement()) } ``` 循环从列表的最后一个元素开始，当当前位置大于或等于 0 时，调用 `prev()` 方法后移一位迭代器只是用来列表上随意移动，而不应该和任何为列表增加或删除元素的方法一起使用。 ## 列表 demo 为了展示如何使用列表，将会实现一个关于自助查询系统，我们以图书馆为例 ### 使用列表管理图书租赁 ```js // 声明图书店有哪些图书 const books = [ '飘', '悲惨世界', '百年孤独', '尘埃落定', '老人与海', '平凡的世界', '三体', '西游记', '红楼梦', '白鹿原', '不能承受的生命之轻', '目送', ] // 将每一个图书保存到 bookList 列表中 const bookList = new List() for (let i = 0; i < books.length; i++) { const book = books[i] bookList.append(book) } // 写一个函数来展示图书店里现有的图书清单 const displayList = (list) => { for (list.front; list.hasNext(); list.next()) { console.log(list.getElement()) // 展示 dataStore 中的每一个元素 } } ``` `displayList()` 函数对于原声的数据类型没什么问题，比如由字符串组成的列表。但是它用不了自定义类型，比如我们将在子啊面定义的 `Customer` 对象。让我们对它少做修改，让它可以发现列表是有 `Customer` 对象组成的，这样就可以对其进行显示了。下面是从新定义的 `displayList()` 函数 ```js const displayList = (list) => { for (list.front; list.hasNext(); list.next()) { if (list.getElement() instanceof Customer) { console.log(list.getElement()['name'] + ', ' + list.getElement()['book']) } else { console.log(list.getElement()) } } } ``` 对于列表中的每一个元素，都使用 `instanceof` 操作符判断元素是否是 `Customer` 对象。如果是，就使用 `name` 和 `book` 做索引，得到用户查询到相应书籍的值，如果不是，返回该元素即可。现在已经有了列表 `books` 还需要创建一个 `customers`，用来保存在系统中查询出书籍的用户。 ```js const customers = new List() // 该列表包含 `Customer` 对象，该对象有用户的姓名和查询出来的数据组成，下面是 Customer 对象的构造函数 class Customer { constructor(name, book) { this.name = name this.book = book } } ``` 接下来，需要创建一个允许客户查询书籍的函数，该函数有两个参数： - 客户姓名 - 客户想要查询的书籍如果该书籍目前可以租赁，该方法会从图书馆的图书清单中删除该元素，同时加入客户列表 `customers` 这个操作会用到列表的 `contains()` 方法。 ```js const checkOut = (name, book, bookList, customersList) => { if (bookList.contains(book)) { const c = new Customer(name, book) customers.append(c) bookList.remove(book) } else { console.log(book + ' is not available.') } } ``` 该方法首先查询想要租赁的书籍是否存在，如果存在就创建一个新的 `Customer` 对象，该方法包含书籍名称以及客户姓名。然后将该对象加入到客户列表，并且从图书馆列表中删除该影片。如果影片不存在，抛出一段提示接下来我们用代码测试一下 `checkOut()` 函数 ```js const books = [ '飘', '三体', '目送', '西游记', '红楼梦', '白鹿原', '悲惨世界', '百年孤独', '尘埃落定', '老人与海', '平凡的世界', '不能承受的生命之轻', ] const bookList = new List() for (let i = 0; i < books.length; i++) { const book = books[i] bookList.append(book) } displayList(bookList) checkOut('weihuijie', '不能承受的生命之轻', bookList, customers) displayList(customers) // 输出显示《不能承受的生命之轻》从图书馆列表中删除了，跟着又被加入了客户的列表中 ``` 本 demo 只是实现了一些简单租赁功能，大家也可以加入一些其他功能，使其更加完整。 ## 完整代码 ```js class List { constructor() { this.listSize = 0 this.pos = 0 this.dataStore = [] } append(element) { this.dataStore[this.listSize++] = element } find(element) { for (let i = 0; i < this.dataStore.length; i++) { if (this.dataStore[i] === element) { return i } } return -1 } remove(element) { const index = this.find(element) if (index > -1) { this.dataStore.splice(index, 1) --this.listSize return true } return false } length() { return this.listSize } toString() { return this.dataStore } insert(element, after) { const insertIndex = this.find(after) if (insertIndex > -1) { this.dataStore.splice(insertIndex + 1, 0, element) ++this.listSize return true } return false } clear() { delete this.dataStore this.dataStore = [] this.listSize = 0 this.pos = 0 } contains(element) { for (let i = 0; i < this.dataStore.length; i++) { if (this.dataStore[i] === element) { return true } } return false } front() { return (this.pos = 0) } end() { this.pos = this.listSize - 1 } prev() { --this.pos } next() { if (this.pos < this.listSize) { ++this.pos } } currpos() { return this.pos } moveTo(position) { this.pos = position } getElement() { return this.dataStore[this.pos] } hasNext() { return this.pos < this.listSize } hasPrev() { return this.pos >= 0 } } const books = [ '飘', '三体', '目送', '西游记', '红楼梦', '白鹿原', '悲惨世界', '百年孤独', '尘埃落定', '老人与海', '平凡的世界', '不能承受的生命之轻', ] class Customer { constructor(name, book) { this.name = name this.book = book } } const bookList = new List() const customers = new List() for (let i = 0; i < books.length; i++) { const book = books[i] bookList.append(book) } const checkOut = (name, book, bookList, customersList) => { if (bookList.contains(book)) { const c = new Customer(name, book) customersList.append(c) bookList.remove(book) } else { return book + ' is not available.' } } const displayList = (list) => { for (list.front(); list.hasNext(); list.next()) { if (list.getElement() instanceof Customer) { return list.getElement()['name'] + ', ' + list.getElement()['book'] } else { return list.getElement() } } } console.log(displayList(bookList), 'bookList') checkOut('weihuijie', '不能承受的生命之轻', bookList, customers) console.log(displayList(customers), 'customers') ``` ## 结语以上是对列表整体的描述，首先通过列表的定义，以及如何一步步实现列表，对每一个方法以及属性做梳理，希望看完会对列表会有一些理解，以上也是本人对知识的一个积累参考文献：书籍: 《数据结构与算法 JavaScript 描述》

数据接口之列表