一、区分单/双向链表
单向链表相连的过程是单向的,只能从一个方向遍历
- 可以获取当前节点的下一个节点,但是很难回到上一个节点,但是实际开发中经常会有类似的需求
双向链表可以从两个方向遍历
- 一个节点既有向前连接的引用,也有向后连接的引用
- 每次插入和删除的时候,需要处理四个引用,比单向链表更加复杂
- 相对于单向链表,占用的内存空间相对更大
双向链表的特点
- 使用一个head和tail分别指向头部和尾部的节点
- 每个节点分别包括前指针/后指针/保存的元素
- 双向链表第一个节点的前指针指向null
- 双向链表最后一个节点的后指针指向null
二、双向链表常见的操作
在单向链表的基础上进行补充:
forwardString()
:返回正向遍历的节点字符串形式
backwordString
:返回反向遍历的节点字符串形式
三、封装双向链表
1、按照位置插入数据(insert)方法图解:
- position=0
- position=length
- 0<position<length
2、按照位置删除元素
- 删除头部元素
- 删除尾部元素
- 删除中间元素
四、代码实现
/**
* 封装双向链表
*/
function DoudlyLinkedList() {
// 属性
this.head = null
this.tail = null
this.length = 0
// 内部类(用于创建节点)
function Node(data) {
this.data = data
this.prev = null
this.next = null
}
// 尾部追加数据
DoudlyLinkedList.prototype.append = function (data) {
// 创建节点
let newNode = new Node(data)
// 判断添加之前是否为空链表
if (this.head == null) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
}
// 修改长度
this.length += 1
}
// 正向遍历的方法
DoudlyLinkedList.prototype.forwardString = function () {
let flag = this.head
let result = ''
while (flag) {
result += flag.data + ' '
flag = flag.next
}
return result
}
// insert
DoudlyLinkedList.prototype.insert = function (position, data) {
// position判断
if (position < 0 || position > this.length) return false
// 创建节点
let newNode = new Node(data)
// 判断插入位置
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 {
let index = 0
let flag = this.head
this.previous = null
while (index < position) {
previous = flag
flag = flag.next
index++
}
newNode.next = flag
newNode.prev = previous
flag = prev = newNode
previous.next = newNode
}
this.length += 1
return true
}
// removeAt
DoudlyLinkedList.prototype.removeAt = function (position) {
if (position < 0 || position >= this.length) return null
// 判断移除的位置
let flag = this.head
if (position == 0) {
if (this.length == 0) {
this.head = null
this.tail = null
} else {
this.head = this.head.next
this.head.prev = null
}
} else if (position == this.length - 1) {
flag = this.tail
this.tail = this.tail.prev
this.tail.next = null
} else {
let index = 0
let previous = null
while (index < position) {
previous = flag
flag = flag.next
index++
}
previous.next = flag.next
flag.next.prev = previous
}
this.length -= 1
return flag.data
}
// 获取元素的位置
DoudlyLinkedList.prototype.indexOf = function (data) {
let flag = this.head
let index = 0
while (flag) {
if (flag.data == data) {
return index
}
index++
flag = flag.next
}
return -1
}
// 根据元素删除
DoudlyLinkedList.prototype.remove = function (data) {
let index = this.indexOf(data)
return this.removeAt(index)
}
// 判断是否为空
DoudlyLinkedList.prototype.isEmpty = function () {
return this.length == 0
}
// 获取链表长度
DoudlyLinkedList.prototype.size = function () {
return this.length
}
// 获取第一个元素
DoudlyLinkedList.prototype.getHead = function () {
return this.head.data
}
// 获取最后一个元素
DoudlyLinkedList.prototype.getTail = function () {
return this.tail.data
}
}
let Dlist = new DoudlyLinkedList()
Dlist.append('a')
Dlist.append('b')
Dlist.append('c')
Dlist.append('d')
console.log(Dlist.forwardString()) // a b c d
console.log(Dlist.insert(1, 'ok'))
console.log(Dlist.insert(Dlist.length, 'no'))
console.log(Dlist.insert(0, 'first'))
console.log(Dlist.forwardString()) // first a ok b c d no
console.log(Dlist.removeAt(1)) // a
console.log(Dlist.forwardString()) // first ok b c d no
console.log(Dlist.indexOf('no')) // 5
console.log(Dlist.remove('first')) // first
console.log(Dlist.forwardString()) // ok b c d no
console.log(Dlist.isEmpty()) // false
console.log(Dlist.size()) // 5
console.log(Dlist.getHead()) // ok
console.log(Dlist.getTail()) // no
文章评论