双向链表,跟单向链表比起来,多了previous跟tail,prev主要用于给当前节点指向上一个节点,tail类比head,用于标记最后一个节点,tail的next指向null
双向链表如图
代码
class Node {
constructor(data) {
this.element = data
this.previous = null
this.next = null
}
}
class DoublyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
};
append(element) {
let newNode = new Node(element)
//双向链表的插入
if (this.length == 0) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
newNode.previous = this.tail
this.tail = newNode
}
this.length += 1
};
forwardString() {
let current = this.head;
let forwardStr = ''
while (current) {
forwardStr += current.element + " "
current = current.next
}
return forwardStr
};
reverseString() {
let current = this.tail
let reverseStr = ''
while (current) {
reverseStr += current.element + " "
current = current.previous
}
return reverseStr
}
toString() {
return this.forwardString()
};
insert(position, element) {
if (position < 0 || position > this.length) return false
var newNode = new Node(element)
if (position == 0) {
if (this.length == 0) {
this.head = newNode
this.tail = newNode
} else {
this.head.previous = newNode
newNode.next = this.head
this.head = newNode
}
} else if (this.length == position) {
//尾部插入
newNode.previous = this.tail
this.tail.next = newNode
this.tail = newNode
} else {
let [index, current, prev] = [0, this.head, null]
//0 2
while (index++ < position) {
prev = current
current = current.next
}
newNode.next = current
newNode.previous = prev
current.previous = newNode
prev.next = newNode
}
this.length++
return true
};
removeAt(position, element) {
if (position < 0 || position > this.length) return false
// 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
}
}
let doublyLinkedList = new DoublyLinkedList()
doublyLinkedList.append("aaa")
doublyLinkedList.append("bbb")
doublyLinkedList.append("ccc")
doublyLinkedList.append("ddd")
doublyLinkedList.append("eee")
doublyLinkedList.append("fff")
doublyLinkedList.insert(6, "push")
doublyLinkedList.insert(0, 'l')
doublyLinkedList.insert(2, 'j')
doublyLinkedList.insert(2, 'd')
console.log(doublyLinkedList.toString())//l aaa d j bbb ccc ddd eee fff
