本文共 10406 字,大约阅读时间需要 34 分钟。
如需转载, 请咨询作者, 并且注明出处.
有任何问题, 可以关注我的微博: , 或者添加我的微信: 372623326
链表和数组一样, 可以用于存储一系列的元素, 但是链表和数组的实现机制完全不同.
这一章中, 我们就来学习一下另外一种非常常见的用于存储数据的线性结构: 链表.
我们先来认识一下链表, 看一下它大概的机制和原理, 以及和数组的对比.
链表和数组
[]
语法来访问它的元素。Array
类方法可以帮我们做这些事,但背后的原理依然是这样)。什么是链表?
什么是链表呢?
其实上面我们已经简单的提过了链表的结构, 我们这里更加详细的分析一下.
链表类似于火车: 有一个火车头, 火车头会连接一个节点, 节点上有乘客, 并且这个节点会连接下一个节点, 以此类推.
链表的火车结构:
img
链表的数据结构
img
给火车加上数据后的结构
img
前面我们已经认识了链表结构, 现在通过代码来封装自己的链表吧.
创建链表类
我们先来创建一个链表类
// 封装链表的构造函数function LinkedList() { // 封装一个Node类, 用于保存每个节点信息 function Node(element) { this.element = element this.next = null } // 链表中的属性 this.length = 0 // 链表的长度 this.head = null // 链表的第一个节点 // 链表中的方法}
代码解析:
链表常见操作
append(element)
:向列表尾部添加一个新的项insert(position, element)
:向列表的特定位置插入一个新的项。remove(element)
:从列表中移除一项。indexOf(element)
:返回元素在列表中的索引。如果列表中没有该元素则返回-1
。removeAt(position)
:从列表的特定位置移除一项。isEmpty()
:如果链表中不包含任何元素,返回true
,如果链表长度大于0则返回false
。size()
:返回链表包含的元素个数。与数组的length
属性类似。toString()
:由于列表项使用了Node
类,就需要重写继承自JavaScript对象默认的toString
方法,让其只输出元素的值。尾部追加数据
向链表尾部追加数据可能有两种情况:
append方法实现
// 链表尾部追加元素方法LinkedList.prototype.append = function (element) { // 1.根据新元素创建节点 var newNode = new Node(element) // 2.判断原来链表是否为空 if (this.head === null) { // 链表尾空 this.head = newNode } else { // 链表不为空 // 2.1.定义变量, 保存当前找到的节点 var current = this.head while (current.next) { current = current.next } // 2.2.找到最后一项, 将其next赋值为node current.next = newNode } // 3.链表长度增加1 this.length++}
代码解读:
首先需要做的是将element传入方法, 并根据element创建一个Node节点.
场景一: 链表本身是空的, 比如这种情况下我们插入了一个15作为元素.
img
场景二: 链表中已经有元素了, 需要向最后的节点的next中添加节点.
img
最后, 一定不要忘记将链表的length+1.
toString方法
我们先来实现一下链表的toString方法, 这样会方便测试上面的添加代码
// 链表的toString方法LinkedList.prototype.toString = function () { // 1.定义两个变量 var current = this.head var listString = "" // 2.循环获取链表中所有的元素 while (current) { listString += "," + current.element current = current.next } // 3.返回最终结果 return listString.slice(1)}
方法解读:
测试append方法
// 测试链表// 1.创建链表var list = new LinkedList()// 2.追加元素list.append(15)list.append(10)list.append(20)// 3.打印链表的结果alert(list)
任意位置插入
接下来实现另外一个添加数据的方法: 在任意位置插入数据.
// 根据下标删除元素LinkedList.prototype.insert = function (position, element) { // 1.检测越界问题: 越界插入失败 if (position < 0 || position > this.length) return false // 2.找到正确的位置, 并且插入数据 var newNode = new Node(element) var current = this.head var previous = null index = 0 // 3.判断是否列表是否在第一个位置插入 if (position == 0) { newNode.next = current this.head = newNode } else { while (index++ < position) { previous = current current = current.next } newNode.next = current previous.next = newNode } // 4.length+1 this.length++ return true}
代码解读:
代码1的位置, 我们处理了越界问题, 基本传入位置信息时, 都需要进行越界的判断. 如果越界, 返回false, 表示数据添加失败. (因为位置信息是错误的, 所以数据肯定是添加失败的)
代码2的位置, 我们定义了一些变量, 后续需要使用它们来保存信息.
代码3的位置进行了判断, 这是因为添加到第一个位置和其他位置是不同的.
添加到第一个位置:
img
添加到其他位置:
img
img
最后, 不要忘记length+1
返回true, 表示元素插入成功了.
测试insert的方式插入数据:
// 4.测试insert方法list.insert(0, 100)list.insert(4, 200)list.insert(2, 300)alert(list) // 100,15,300,10,20,200
位置移除数据
移除数据有两种常见的方式:
我们这里先完成根据位置移除数据的方式
// 根据位置移除节点LinkedList.prototype.removeAt = function (position) { // 1.检测越界问题: 越界移除失败, 返回null if (position < 0 || position >= this.length) return null // 2.定义变量, 保存信息 var current = this.head var previous = null var index = 0 // 3.判断是否是移除第一项 if (position === 0) { this.head = current.next } else { while (index++ < position) { previous = current current = current.next } previous.next = current.next } // 4.length-1 this.length-- // 5.返回移除的数据 return current.element}
代码解析:
代码1部分, 还是越界的判断. (注意: 这里越界判断中的等于length也是越界的, 因为下标值是从0开始的)
代码2部分还是定义了一些变量, 用于保存临时信息
代码3部分进行判断, 因为移除第一项和其他项的方式是不同的
移除第一项的信息:
img
移除其他项的信息:
img
img
测试removeAt方法
// 5.测试removeAt方法list.removeAt(0)list.removeAt(1)list.removeAt(3)alert(list) // 15, 10, 20
获取元素位置
我们来完成另一个功能: 根据元素获取它在链表中的位置
// 根据元素获取链表中的位置LinkedList.prototype.indexOf = function (element) { // 1.定义变量, 保存信息 var current = this.head index = 0 // 2.找到元素所在的位置 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.来到这个位置, 说明没有找到, 则返回-1 return -1}
代码解析:
indexOf方法测试
// 6.测试indexOf方法alert(list.indexOf(15)) // 0alert(list.indexOf(10)) // 1alert(list.indexOf(20)) // 2alert(list.indexOf(100)) // -1
根据元素删除
有了上面的indexOf方法, 我们可以非常方便实现根据元素来删除信息
// 根据元素删除信息LinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index)}
代码解析:
代码测试:
// 7.测试remove方法list.remove(15)alert(list) // 10,20
其他方法实现
isEmpty方法
// 判断链表是否为空LinkedList.prototype.isEmpty = function () { return this.length == 0}
size方法
// 获取链表的长度LinkedList.prototype.size = function () { return this.length}
获取第一个元素节点: (单向链表比较方便的操作)
// 获取第一个节点LinkedList.prototype.getFirst = function () { return this.head.element}
方法测试:
// 8.测试其他方法alert(list.isEmpty()) // falsealert(list.size()) // 2alert(list.getFirst()) // 10
我们给出一份完成的LinkedList代码
// 封装链表的构造函数function LinkedList() { // 封装一个Node类, 用于保存每个节点信息 function Node(element) { this.element = element this.next = null } // 链表中的属性 this.length = 0 this.head = null // 链表尾部追加元素方法 LinkedList.prototype.append = function (element) { // 1.根据新元素创建节点 var newNode = new Node(element) // 2.判断原来链表是否为空 if (this.head === null) { // 链表尾空 this.head = newNode } else { // 链表不为空 // 2.1.定义变量, 保存当前找到的节点 var current = this.head while (current.next) { current = current.next } // 2.2.找到最后一项, 将其next赋值为node current.next = newNode } // 3.链表长度增加1 this.length++ } // 链表的toString方法 LinkedList.prototype.toString = function () { // 1.定义两个变量 var current = this.head var listString = "" // 2.循环获取链表中所有的元素 while (current) { listString += "," + current.element current = current.next } // 3.返回最终结果 return listString.slice(1) } // 根据下标删除元素 LinkedList.prototype.insert = function (position, element) { // 1.检测越界问题: 越界插入失败 if (position < 0 || position > this.length) return false // 2.定义变量, 保存信息 var newNode = new Node(element) var current = this.head var previous = null index = 0 // 3.判断是否列表是否在第一个位置插入 if (position == 0) { newNode.next = current this.head = newNode } else { while (index++ < position) { previous = current current = current.next } newNode.next = current previous.next = newNode } // 4.length+1 this.length++ return true } // 根据位置移除节点 LinkedList.prototype.removeAt = function (position) { // 1.检测越界问题: 越界移除失败, 返回null if (position < 0 || position >= this.length) return null // 2.定义变量, 保存信息 var current = this.head var previous = null var index = 0 // 3.判断是否是移除第一项 if (position === 0) { this.head = current.next } else { while (index++ < position) { previous = current current = current.next } previous.next = current.next } // 4.length-1 this.length-- // 5.返回移除的数据 return current.element } // 根据元素获取链表中的位置 LinkedList.prototype.indexOf = function (element) { // 1.定义变量, 保存信息 var current = this.head index = 0 // 2.找到元素所在的位置 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.来到这个位置, 说明没有找到, 则返回-1 return -1 } // 根据元素删除信息 LinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index) } // 判断链表是否为空 LinkedList.prototype.isEmpty = function () { return this.length == 0 } // 获取链表的长度 LinkedList.prototype.size = function () { return this.length } // 获取第一个节点 LinkedList.prototype.getFirst = function () { return this.head.element }}