You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
// insert() 在指定位置(position)插入节点insert(position,data){// position 新插入节点的位置// position = 0 表示新插入后是第一个节点// position = 1 表示新插入后是第二个节点// 对position进行越界判断,不能小于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 < position <= length 的情况// 初始化一些变量letcurrentNode=this.head;// 当前节点初始化为headletpreviousNode=null;// head的 上一个节点 为 nullletindex=0;// head 的index为0// 在 0 ~ position 之间遍历,不断地更新 currentNode 和 previousNode// 直到找到要插入的位置while(index++<position){previousNode=currentNode;currrentNode=currentNode.next;}// 在当前节点和当前节点的上一个节点之间插入新节点,即它们的改变指向// previous currentNode(position)newNode.next=currentNode;previous.next=newNode;}// 更新链表长度this.length++;returnnewNode;}
实现 getData() 方法
获取指定位置(position)的 data。
getData(position){// position 越界判断if(position<0||position>=this.length)returnnull;// 获取指定 position 节点的 dataletcurrentNode=this.head;letindex=0while(index++<position){currentNode=currentNode.next}// 返回 datareturncurrentNode.data}
链表和数组
链表和数组的实现机制完全不同。
数组
存储多个元素,数组(或列表)可能是最常用的数据结构。
几乎每一种编程语言都有默认实现数组结构,提供了一个便利的
[]
语法来访问数组元素。数组缺点:
数组的创建需要申请一段连续的内存空间(一整块内存),并且大小是固定的,当前数组不能满足容量需求时,需要扩容。 (一般情况下是申请一个更大的数组,比如 2 倍,然后将原数组中的元素复制过去)
在数组开头或中间位置插入数据的成本很高,需要进行大量元素的位移。
链表
不同于数组,链表中的元素在内存中不必是连续的空间。
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。
链表优点:
内存空间不必是连续的,可以充分利用计算机的内存,实现灵活的内存动态管理。
链表不必在创建时就确定大小,并且大小可以无限延伸下去。
链表在插入和删除数据时,时间复杂度可以达到 O(1),相对数组效率高很多。
链表缺点:
访问任何一个位置的元素时,需要从头开始访问。(无法跳过第一个元素访问任何一个元素)
无法通过下标值直接访问元素,需要从头开始一个个访问,直到找到对应的元素。
虽然可以轻松地到达下一个节点,但是回到前一个节点是很难的。
单向链表
单向链表类似于火车,有一个火车头,火车头会连接一个节点,节点上有乘客,并且这个节点会连接下一个节点,以此类推。
链表的数据结构
head 属性指向链表的第一个节点。
链表中的最后一个节点指向
null
。当链表中一个节点也没有的时候,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,添加基本属性,再逐步实现单向链表的常用方法。
实现 append() 方法
实现 toString() 方法
实现 insert() 方法
实现 getData() 方法
获取指定位置(position)的 data。
实现 indexOf() 方法
indexOf(data) 返回指定 data 的 index,如果没有,返回 -1。
实现 update() 方法
update(position, data) 修改指定位置节点的 data。
实现 removeAt() 方法
removeAt(position) 删除指定位置的节点。
实现 remove() 方法
remove(data) 删除指定 data 所在的节点。
实现 isEmpty() 方法
isEmpty() 判断链表是否为空。
实现 size() 方法
size() 获取链表的长度。
完整实现
The text was updated successfully, but these errors were encountered: