双向链表对比单向链表有何优势？
单向链表每次只能从头开始查询数据，双向链表可以从尾到头查询数据，效率更高，还可用二分法辅助
function doublyLinkedList() {
// 默认属性
this.head = null
this.tail = null
this.length = 0
// 声明节点类
function node(data) {
this.data = data
this.prev = null
this.next = null
}
// 声明双向链表的追加方法
this.append = function (data) {
const newNode = new node(data)
if (this.length === 0) {
this.head = newNode
this.tail = newNode
} else {
// tail代表链表尾部 无需循环
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
}
this.length += 1
}
// 声明双向链表的插入方法 你传入5 代表下标为4
this.insert = function (position, data) {
const newNode = new node(data)
if (position < 0 || position > this.length) return false
if (this.length === 0) {
this.head = newNode
this.tail = newNode
} else {
if (position === 0) {
this.head.prev = newNode
newNode.next = this.head
this.head = newNode
} else if (position === this.length) { //插到最后
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
} else {
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
newNode.prev = current.prev
newNode.next = current
current.prev.next = newNode
current.prev = newNode
}
this.length += 1
return true
}
}
// 声明方法:获取对应位置的值
this.get = function (position) {
if (position < 0 || position >= this.length) return false //为什么这里的position不能等于链表长度：最后一次循环current会获得一个不存在的下标为4的节点
// 采用二分计算法 提高效率
if (position <= (this.length / 2)) {
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
return current.data
} else {
let current = this.tail
let index = this.length - 1 //这里拿length的时候记得减一 因为下标永远比长度少一位
while (index-- > position) {
current = current.prev
}
return current.data
}
}
// 声明方法：获取传入数据的下标
this.indexOf = function (data) {
let index = 0
// 这里也可以用二分
let current = this.head
while (index++ < (this.length - 1)) {
if (current.data === data) {
return index - 1
}
current = current.next
}
}
//声明方法：用传入数据修改指定位置的数据
this.update = function (position, data) {
if (position < 0 || position >= this.length) return null
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
return current.data = data
}
// 声明方法：删除指定位置节点
this.removeAt = function (position) {
if (position < 0 || position >= this.length) return null
// 可以二分
let current = this.head
if (this.length === 1) {
this.head = null;
this.tail = null
} else {
let index = 0
while (index++ < position) {
current = current.next
}
if (position === 0) {
this.head = current.next
current.next.prev = null
} else if (position === (this.length - 1)) {
this.tail = current.prev
current.prev.next = null
} else {
current.prev.next = current.next
current.next.prev = current.prev
}
}
this.length -= 1
return current.data //返回被删除的节点
}
// 声明方法：删除含有指定data的节点
this.remove = function (data) {
let position = this.indexOf(data)
return this.removeAt(position)
}
// 声明方法：判断链表是否为空
this.isEmpty = function () {
return this.length === 0
}
// 声明方法：删除含有指定data的节点
this.size = function () {
return this.length
}
// 声明双向链表的正向转字符串方法
this.forwardToString = function () {
let current = this.head
let listStr = ''
while (current) {
listStr += current.data + ' '
current = current.next
}
return listStr
}
// 声明双向链表的逆向转字符串方法
this.backToString = function () {
let current = this.tail
let listStr = ''
while (current) {
listStr += current.data + ' '
current = current.prev
}
return listStr
}
// 声明双向链表的转字符串方法
this.toString = function () {
return this.forwardToString()
}
}
// 创建实例
const doubly = new doublyLinkedList()
doubly.append('张三')
doubly.append('李四')
doubly.append('王五')
doubly.append('六')
doubly.append('七')
doubly.append('八')
// console.log(doubly.toString()) // 张三 李四 王五
// console.log(doubly.forwardToString()) // 张三 李四 王五
// console.log(doubly.backToString()) // 王五 李四 张三
doubly.insert(1, '插入的人')
console.log(doubly.toString()) // 张三 插入的人 李四 王五
console.log(doubly.get(6)) // 王五
console.log(doubly.length)
console.log(doubly.indexOf('王五')) // 3
doubly.update(2, '更新后的李四')
console.log(doubly.toString()) //张三 插入的人 更新后的李四 王五 六 七 八
doubly.removeAt(1)
console.log(doubly.toString()) //张三 更新后的李四 王五 六 七 八
总结
1、画图理解！
2、伪代码理解！
3、注意细节，每一个判断都尤为重要
