数据结构之List | 让我们一块来学习数据结构

简介: 数据结构之List | 让我们一块来学习数据结构

列表[List]的定义

列表是一组有序的数据。每个列表中的数据项称为元素。在 JavaScript 中,列表中的元素 可以是任意数据类型。列表中可以保存多少元素并没有事先限定,实际使用时元素的数量 受到程序内存的限制。

不包含任何元素的列表称为空列表。列表中包含元素的个数称为列表的 length。在内部实 现上,用一个变量 listSize 保存列表中元素的个数。可以在列表末尾 append 一个元素, 也可以在一个给定元素后或列表的起始位置 insert 一个元素。使用remove 方法从列表中 删除元素,使用 clear 方法清空列表中所有的元素。

还可以使用 toString() 方法显示列表中所有的元素,使用 getElement() 方法显示当前元素。列表拥有描述元素位置的属性。列表有前有后(分别对应 front 和 end)。使用 next() 方 法可以从当前元素移动到下一个元素,使用 prev() 方法可以移动到当前元素的前一个元 素。还可以使用 moveTo(n) 方法直接移动到指定位置,这里的 n 表示要移动到第 n 个位置。 currPos 属性表示列表中的当前位置。

列表的抽象数据类型定义

属性/方法 描述
listSize 列表的元素个数
pos 列表的当前位置
length 返回列表中元素的个数
clear(方法) 清空列表中的所有元素
toString(方法) 返回列表的字符串形式
getElement(方法) 返回当前位置的元素
insert(方法) 在现有元素后插入新元素
append(方法) 在列表的末尾添加新元素
remove(方法) 从列表中删除元素
front(方法) 将列表的当前位置设移动到第一个元素
end(方法) 将列表的当前位置移动到最后一个元素
prev(方法) 将当前位置后移一位
next(方法) 将当前位置前移一位
currPos(方法) 返回列表的当前位置
moveTo(方法) 将当前位置移动到指定位置
contains(方法) 判断给定值是否在列表中
getElement(方法) 显示当前值

实现列表类

根据上面定义的列表抽象数据类型,可以直接实现一个 List 类。让我们从定义构造函数开 始,虽然它本身并不是列表抽象数据类型定义的一部分:

class List {
    constructor() {
        this.dataSource = [];
        this.listSize = 0;
        this.pos = 0;
    }
    clear() {}
    find() {}
    toString() {}
    insert() {}
    append() {}
    remove() {}
    front() {}
    end() {}
    prev() {}
    next() {}
    length() {}
    currPos() {}
    moveTo() {}
    getElement() {}
    contains() {}
}

append:给列表添加元素

append(element) {
    this.dataStore[this.listSize++] = element;
}

当新元素就位后,变量 listSize 加 1。

find:在列表中查找某一元素

find() 方法通过对数组对象 dataStore 进行迭代,查找给定的元素。如果找到,就返回该 元素在列表中的位置,否则返回 -1,这是在数组中找不到指定元素时返回的标准值。我们 可以在 remove() 方法中利用此值做错误校验。

find(element) {
    for (let i = 0, len = this.dataStore.length; i < len; ++i) {
        if (this.dataStore[i] == element) {
            return i;
        }
    }
    return -1;
}

remove:从列表中删除元素

remove() 方法是 List 类中较难实现的 一个方法。首先,需要在列表中找到该元素,然后删除它,并且调整底层的数组对象以填 补删除该元素后留下的空白。好消息是,可以使用数组的 splice() 方法简化这一过程。

remove(element) {
    const index = this.find(element);
    if (index === -1) {
        return false
    }
    this.dataStore.splice(index, 1);
    --this.listSize;
    return true;
}

length:列表中有多少个元素

length() 方法返回列表中元素的个数:

length() {
    return this.listSize;
}

toString:显示列表中的元素

现在是时候创建一个方法,用来显示列表中的元素了。

toString() {
    return this.dataStore.toString();
}

insert:向列表中插入一个元素

接下来要讨论的方法是 insert()。如果在List中间位置删除了一个元素,但是现在又想将 它放回原来的位置,该怎么办? insert() 方法需要知道将元素插入到什么位置,因此现在 我们假设插入是指插入到列表中某个元素之后。

insert(element, index) {
    const index = this.find(element);
    if (index === -1) {
        return false;
    }
    this.dataStore.splice(index + 1, 0, element);
    ++this.listSize;
    return true;
}

clear:清空列表中所有的元素

clear() {
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = this.pos = 0;
}

contains:判断给定值是否在列表中

当需要判断一个给定值是否在列表中时,contains()方法就变得很有用。

contains(element) {
    for (let i = 0, len = this.dataStore.length; i < len; ++i) {
        if (this.dataStore[i] == element) {
            return true;
        }
    }
    return false;
}

也可以使用之前实现的find方法

遍历列表

最后的一组方法允许用户在列表上自由移动

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;
    }
}
currPos() {
    return this.pos;
}
moveTo(position) {
    this.pos = position;
}
getElement() {
    return this.dataStore[this.pos];
}

使用迭代器访问列表

使用迭代器,可以不必关心数据的内部存储方式,以实现对列表的遍历。前面提到的方法 front()end()prev()next()currPos 就实现了 List 类的一个迭代器。以下是和使 用数组索引的方式相比,使用迭代器的一些优点。

访问列表元素时不必关心底层的数据存储结构。

当为列表添加一个元素时,索引的值就不对了,此时只用更新列表,而不用更新迭代器。

可以用不同类型的数据存储方式实现 List 类,迭代器为访问列表里的元素提供了一种 统一的方式。 了解了这些优点后,来看一个使用迭代器遍历列表的例子:

for(lists.front(); lists.currPos() < lists.length(); lists.next()) { 
    console.log(lists.getElement());
}

在 for 循环的一开始,将列表的当前位置设置为第一个元素。只要 currPos 的值小于列表 的长度,就一直循环,每一次循环都调用 next() 方法将当前位置向前移动一位。

同理,还可以从后向前遍历列表,代码如下:

for(lists.end(); lists.currPos() >= 0; lists.prev()) { 
    console.log(lists.getElement()); 
}

循环从列表的最后一个元素开始,当当前位置大于或等于 0 时,调用 prev() 方法后移 一位。

迭代器只是用来在列表上随意移动,而不应该和任何为列表增加或删除元素的方法一起 使用。

完整代码

class List {
    constructor() {
        this.dataStore = [];
        this.listSize = 0;
        this.pos = 0;
    }
    clear() {
        delete this.dataStore;
        this.dataStore = [];
        this.listSize = this.pos = 0;
    }
    find(element) {
        for (let i = 0, len = this.dataStore.length; i < len; ++i) {
            if (this.dataStore[i] == element) {
                return i;
            }
        }
        return -1;
    }
    toString() {
        return this.dataStore.toString();
    }
    insert(element, index) {
        const index = this.find(element);
        if (index === -1) {
            return false;
        }
        this.dataStore.splice(index + 1, 0, element);
        ++this.listSize;
        return true;
    }
    append(element) {
        this.dataStore[this.listSize++] = element;
    }
    remove(element) {
        const index = this.find(element);
        if (index === -1) {
            return false;
        }
        this.dataStore.splice(index, 1);
        --this.listSize;
        return true;
    }
    length() {
        return this.listSize;
    }
    contains(element) {
        for (let i = 0, len = this.dataStore.length; i < len; ++i) {
            if (this.dataStore[i] == element) {
                return true;
            }
        }
        return false;
    }
    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;
        }
    }
    currPos() {
        return this.pos;
    }
    moveTo(position) {
        this.pos = position;
    }
    getElement() {
        return this.dataStore[this.pos];
    }
}

参考资料

  • 数据结构与算法JavaScript描述

相关文章
|
2月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
61 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
2月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
57 0
数据结构与算法学习十五:哈希表
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明