定义

链表和数组一样可以存储一些列的数据结构，但是链表和实现机制完全不同

区别

数组

• 要存储多个元素，数组可能是最常见的数据结构
  缺点：
• 在创建阶段需要申请一段连续的内存空间(一整块的内存)，并且大小都是固定的(大多数编程语言大小都是固定的)，
  所以当当前数组不能满足容量需求时，需要扩容（一般情况下申请一个更大的数组，比如两倍，然后将原有的数组元素复制过去）
• 而且在数组开头或者中间位置插入数据的成本很高，需要进行大量元素的位移
• 尽管我们学过js的array的一些插入数组的方法帮我们做这件事，但是背后的原理一样

链表

• 也是存储多个元素，另外一种选择是链表
• 不同于数组结构，链表中的元素在数组中不必是连续空间（不需要给一整块内存空间）
• 链表的每一个元素都由一个存储 元素本身的节点 和一个 指向下一个元素的引用（有些语言称为指针或者链接组成）

链表相对数组的优点

• 内存空间不是必要连续的，可以充分的应用计算机内存实现灵活的内存动态管理
• 链表不必在创建时确定大小，并且大小可以无限延续下去
• 链表在插入和删除数据时，时间复杂度是O(1),相对数组操作效率高很多

链表相对数组的缺点

• 链表访问任何一个位置元素时，都要从头开始访问（无法跳过第一个元素去访问后面的元素）
• 无法通过下标直接访问，需要从头一个一个访问，直到找到对应元素

如果需要频繁操作前面或者中间插入元素，可以使用链表结构
如果仅仅是读下表索引这种 一般都是使用数组结构

image.png

链表常见的操作

• append(element) 向列表尾部添加一个新的项
• insert(position,element) 向列表的特定位置插入一个新的项
• get(position) 获取对应位置的元素
• indexOf(element) 返回元素在列表中的索引，如果列表中没有该元素则返回-1
• update(position) 修改某个位置的元素
• remove(element) 从列表中移除一项
• isEmpty() 如果链表中不包含任何元素返回true，如果链表长度大于0 返回false
• size() 返回链表包含元素的个数，类似于数组length
• toString() 由于列表项使用了Node类，就要重新写继承自js对象默认的toSting方法，让其只输出元素的值