一、理论知识
链表和数组
- 数组:
- 要存储多个元素，数组（或列表）可能是最常用的数据结构。
- 我们之前说过, 几乎每一种编程语言都有默认实现数组结构, 这种数据结构非常方便，提供了一个便利的
[]语法来访问它的元素。 - 但是数组也有很多缺点:
- 数组的创建通常需要申请一段连续的内存空间(一整块的内存), 并且大小是固定的(大多数编程语言数组都是固定的), 所以当当前数组不能满足容量需求时, 需要扩容. (一般情况下是申请一个更大的数组, 比如2倍. 然后将原数组中的元素复制过去)
- 而且在数组开头或中间位置插入数据的成本很高, 需要进行大量元素的位移.（尽管我们已经学过的JavaScript的
Array类方法可以帮我们做这些事，但背后的原理依然是这样）。
- 链表
- 要存储多个元素, 另外一个选择就是使用链表.
- 但不同于数组, 链表中的元素在内存中不必是连续的空间.
- 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成.
- 相对于数组, 链表有一些优点:
- 内存空间不是比是连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理.
- 链表不必在创建时就确定大小, 并且大小可以无限的延伸下去.
- 链表在插入和删除数据时, 时间复杂度可以达到O(1). 相对数组效率高很多.
- 相对于数组, 链表有一些缺点:
- 链表访问任何一个位置的元素时, 都需要从头开始访问.(无法跳过第一个元素访问任何一个元素).
- 无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的问题.
什么是链表?
什么是链表呢?
- 其实上面我们已经简单的提过了链表的结构, 我们这里更加详细的分析一下.
- 链表类似于火车: 有一个火车头, 火车头会连接一个节点, 节点上有乘客, 并且这个节点会连接下一个节点, 以此类推.
- 链表的火车结构:
img
- 链表的数据结构
给火车加上数据后的结构
链表常见操作
append(element)：向列表尾部添加一个新的项
insert(position, element)：向列表的特定位置插入一个新的项。
remove(element)：从列表中移除一项。
indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
removeAt(position)：从列表的特定位置移除一项。
-
isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
size()：返回链表包含的元素个数。与数组的length属性类似。
toString()：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。