本文共 12490 字,大约阅读时间需要 41 分钟。
如需转载, 请咨询作者, 并且注明出处.
有任何问题, 可以关注我的微博: , 或者添加我的微信: 372623326
前一节的篇幅有些多了, 所以我们将双向链表放在这篇中介绍.
双向链表介绍
单向链表:
双向链表
双向连接的图解:
img
双向链表的创建
我们来创建一个双向链表的类
// 创建双向链表的构造函数function DoublyLinkedList() { // 创建节点构造函数 function Node(element) { this.element = element this.next = null this.prev = null // 新添加的 } // 定义属性 this.length = 0 this.head = null this.tail = null // 新添加的 // 定义相关操作方法}
代码解析:
双向链表的操作和单向链表的方法都是类似的.
只是在实现的过程中, 需要考虑更多节点之间的关系, 所以变得比单向链表复杂了一些.
尾部追加数据
我们还是先来实现尾部追加数据的方法
// 在尾部追加数据DoublyLinkedList.prototype.append = function (element) { // 1.根据元素创建节点 var newNode = new Node(element) // 2.判断列表是否为空列表 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } // 3.length+1 this.length++}
代码解析:
正向反向遍历
链表的遍历
方法的相关实现:
// 正向遍历的方法DoublyLinkedList.prototype.forwardString = function () { var current = this.head var forwardStr = "" while (current) { forwardStr += "," + current.element current = current.next } return forwardStr.slice(1)}// 反向遍历的方法DoublyLinkedList.prototype.reverseString = function () { var current = this.tail var reverseStr = "" while (current) { reverseStr += "," + current.element current = current.prev } return reverseStr.slice(1)}// 实现toString方法DoublyLinkedList.prototype.toString = function () { return this.forwardString()}
完成上面的代码后, 测试append方法
// 1.创建双向链表对象var list = new DoublyLinkedList()// 2.追加元素list.append("abc")list.append("cba")list.append("nba")list.append("mba")// 3.获取所有的遍历结果alert(list.forwardString()) // abc,cba,nba,mbaalert(list.reverseString()) // mba,nba,cba,abcalert(list) // abc,cba,nba,mba
任意位置插入
向双向链表的任意位置插入数据会有一些复杂, 考虑的情况也会有一些多.
// 在任意位置插入数据DoublyLinkedList.prototype.insert = function (position, element) { // 1.判断越界的问题 if (position < 0 || position > this.length) return false // 2.创建新的节点 var newNode = new Node(element) // 3.判断插入的位置 if (position === 0) { // 在第一个位置插入数据 // 判断链表是否为空 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.head.prev = newNode newNode.next = this.head this.head = newNode } } else if (position === this.length) { // 插入到最后的情况 // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么? this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } else { // 在中间位置插入数据 // 定义属性 var index = 0 var current = this.head var previous = null // 查找正确的位置 while (index++ < position) { previous = current current = current.next } // 交换节点的指向顺序 newNode.next = current newNode.prev = previous current.prev = newNode previous.next = newNode } // 4.length+1 this.length++ return true}
代码深度解析, 代码比较复杂, 我们分成三种情况:
情况一: 将元素插入到头部(position === 0)
img
情况二: 将元素插入到尾部(position === length)
img
情况三: 将元素插入到中间位置
img
测试一下该方法
// 4.insert方法测试list.insert(0, "100")list.insert(2, "200")list.insert(6, "300")alert(list) // 100,abc,200,cba,nba,mba,300
课下思考: 代码性能能否改进一点呢?
位置移除数据
我们继续来做下一个功能: 通过下标值删除某个元素
// 根据位置删除对应的元素DoublyLinkedList.prototype.removeAt = function (position) { // 1.判断越界的问题 if (position < 0 || position >= this.length) return null // 2.判断移除的位置 var current = this.head if (position === 0) { if (this.length == 1) { this.head = null this.tail = null } else { this.head = this.head.next this.head.prev = null } } else if (position === this.length -1) { current = this.tail this.tail = this.tail.prev this.tail.next = null } else { var index = 0 var previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next current.next.prev = previous } // 3.length-1 this.length-- return current.element}
代码深度解析, 和插入一样, 可以分成三种情况:
情况一: 删除头部的元素
img
情况二: 删除尾部的元素
img
情况三: 删除中间位置的元素
img
测试removeAt方法
// 5.removeAt方法测试alert(list.removeAt(0)) // 100alert(list.removeAt(1)) // 200alert(list.removeAt(4)) // 300alert(list) // abc,cba,nba,mba
获取元素位置
下面完成下一个功能: 根据元素获取再链表中的位置
// 根据元素获取在链表中的位置DoublyLinkedList.prototype.indexOf = function (element) { // 1.定义变量保存信息 var current = this.head var index = 0 // 2.查找正确的信息 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.来到这个位置, 说明没有找到, 则返回-1 return -1}
代码解析:
代码测试:
// 6.indexOf方法测试alert(list.indexOf("abc")) // 0alert(list.indexOf("cba")) // 1alert(list.indexOf("nba")) // 2alert(list.indexOf("mba")) // 3
根据元素删除
有了上面的indexOf方法, 我们可以非常方便实现根据元素来删除信息
// 根据元素删除DoublyLinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index)}
代码解析:
测试代码:
// 7.remove方法测试alert(list.remove("abc")) // abcalert(list) // cba,nba,mba
其他方法实现
其他四个方法, 放在一起了
// 判断是否为空DoublyLinkedList.prototype.isEmpty = function () { return this.length === 0}// 获取链表长度DoublyLinkedList.prototype.size = function () { return this.length}// 获取第一个元素DoublyLinkedList.prototype.getHead = function () { return this.head.element}// 获取最后一个元素DoublyLinkedList.prototype.getTail = function () { return this.tail.element}
代码解析:
代码测试:
// 8.测试最后四个方法alert(list.getHead())alert(list.getTail())alert(list.isEmpty())alert(list.size())
给出双向链表的完整代码:
// 创建双向链表的构造函数function DoublyLinkedList() { // 创建节点构造函数 function Node(element) { this.element = element this.next = null this.prev = null // 新添加的 } // 定义属性 this.length = 0 this.head = null this.tail = null // 新添加的 // 定义相关操作方法 // 在尾部追加数据 DoublyLinkedList.prototype.append = function (element) { // 1.根据元素创建节点 var newNode = new Node(element) // 2.判断列表是否为空列表 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } // 3.length+1 this.length++ } // 在任意位置插入数据 DoublyLinkedList.prototype.insert = function (position, element) { // 1.判断越界的问题 if (position < 0 || position > this.length) return false // 2.创建新的节点 var newNode = new Node(element) // 3.判断插入的位置 if (position === 0) { // 在第一个位置插入数据 // 判断链表是否为空 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.head.prev = newNode newNode.next = this.head this.head = newNode } } else if (position === this.length) { // 插入到最后的情况 // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么? this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } else { // 在中间位置插入数据 // 定义属性 var index = 0 var current = this.head var previous = null // 查找正确的位置 while (index++ < position) { previous = current current = current.next } // 交换节点的指向顺序 newNode.next = current newNode.prev = previous current.prev = newNode previous.next = newNode } // 4.length+1 this.length++ return true } // 根据位置删除对应的元素 DoublyLinkedList.prototype.removeAt = function (position) { // 1.判断越界的问题 if (position < 0 || position >= this.length) return null // 2.判断移除的位置 var current = this.head if (position === 0) { if (this.length == 1) { this.head = null this.tail = null } else { this.head = this.head.next this.head.prev = null } } else if (position === this.length -1) { current = this.tail this.tail = this.tail.prev this.tail.next = null } else { var index = 0 var previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next current.next.prev = previous } // 3.length-1 this.length-- return current.element } // 根据元素获取在链表中的位置 DoublyLinkedList.prototype.indexOf = function (element) { // 1.定义变量保存信息 var current = this.head var index = 0 // 2.查找正确的信息 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.来到这个位置, 说明没有找到, 则返回-1 return -1 } // 根据元素删除 DoublyLinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index) } // 判断是否为空 DoublyLinkedList.prototype.isEmpty = function () { return this.length === 0 } // 获取链表长度 DoublyLinkedList.prototype.size = function () { return this.length } // 获取第一个元素 DoublyLinkedList.prototype.getHead = function () { return this.head.element } // 获取最后一个元素 DoublyLinkedList.prototype.getTail = function () { return this.tail.element } // 遍历方法的实现 // 正向遍历的方法 DoublyLinkedList.prototype.forwardString = function () { var current = this.head var forwardStr = "" while (current) { forwardStr += "," + current.element current = current.next } return forwardStr.slice(1) } // 反向遍历的方法 DoublyLinkedList.prototype.reverseString = function () { var current = this.tail var reverseStr = "" while (current) { reverseStr += "," + current.element current = current.prev } return reverseStr.slice(1) } // 实现toString方法 DoublyLinkedList.prototype.toString = function () { return this.forwardString() }}