链表与数组链表与数组的实现机制是完全不同的。数组存储多个元素，数组（或列表）可能是最常用的数据结构。几乎每种编程语言都有数组结构的默认实现，提供方便的[]语法来访问数组元素。数组的缺点：数组的创建需要申请一块连续的内存空间（一整块内存），大小是固定的。当当前阵列不能满足容量需求时，需要进行扩容。（一般情况下，申请一个更大的数组，比如2倍，然后复制原数组中的元素）在数组的开头或中间插入数据的成本非常高，大量的元素位移是必需的。链表不同于数组，链表中的元素在内存中不必是连续的。链表的每个元素都包含一个存储元素本身的节点和一个指向下一个元素的引用（在某些语言中称为指针）。链表的优点：内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的动态内存管理。链表在创建时不必确定大小，大小可以无限扩展。链表在插入和删除数据时，时间复杂度可以达到O(1)，效率比数组高很多。链表的缺点：访问任意位置的元素时，需要从头开始。（不能跳过第一个元素访问任何元素）不能直接通过下标值访问元素，需要从头一个一个访问，直到找到对应的元素。虽然很容易到达下一个节点，但很难回到上一个节点。单向链表类似于火车。有机车，机车会连接到一个节点，节点上有乘客，这个节点会连接到下一个节点，以此类推。链表数据结构的head属性指向链表的第一个节点。链表中的最后一个节点指向空。当链表中没有节点时，head直接指向null。链表中的常用操作append(element)在链表尾部添加一个新项。insert(position,element)在链表的特定位置插入一个新项。get(position)获取对应位置的元素。indexOf(element)返回链表中元素的索引。如果链表中没有这样的元素，则返回-1。update(position,element)修改某个位置的元素。removeAt(position)从链接列表中的特定位置删除项目。remove(element)从链接列表中删除一个项目。如果链表不包含元素，isEmpty()返回trun，如果链表长度大于0则返回false。size()返回链表包含的元素个数，类似于数组的length属性。toString()由于链表项使用了Node类，所以需要重写继承自JavaScript对象的默认toString方法，使其只输出元素的值。单向链表的封装要创建一个单向链表类，首先要创建一个单向链表类LinkedList，添加基本属性，然后逐步实现单向链表的常用方法。classLinkedList{//初始化链表长度为0length=0;//初始head为null，head指向链表的第一个节点head=null;//内部类（链表中的节点）Node=class{data:next=null;constructor(data){this.data=data}};}实现append()方法//append()将数据附加到链表的末尾append(data){//1.创建一个新节点constnewNode=newthis.Node(data)//2.增加一个新节点if(this.length===0){//链表长度为0，只有head时this.head=newNode;}else{//当链表长度大于0时，在末尾添加一个新节点letcurrentNode=this.head//当currentNode.next不为空时//依次查找最后一个节点，即当节点的next为nullwhile(currentNode.next!==null){currentNode=currentNode.next;}//最后一个节点的next指向新节点currentNode.next=newNode;}//3.添加新节点后，链表长度+1this.length++}toString()methodtoString(){letcurrentNode=this.head;让结果='';//遍历所有节点，拼接成字符串，直到节点为nullwhile(currentNode){result+=currentNode.data+'';currentNode=currentNode.next;}returnresult;}实现insert()方法//insert()在指定位置(position)插入节点insert(position,data){//position为新插入节点的位置//position=0表示新插入的是第一个节点//position=1表示新插入的是第二个节点//判断位置越界，不能小于0或者大于长度链表if(position<0||position>this.length)returnfalse;//创建一个新节点constnewNode=newthis.Node(data)//插入节点if(position===0){//position=0//让新节点next指向原来的第一个节点，即headnewNode.next=this.head;//head赋值是newNodethis.head=newNode}else{//0
