(js描述的)数据结构[双向链表]（5）
一.单向链表的缺点
1.只能按顺序查找，即从上一个到下一个，不能反过来。
二.双向链表的优点
1.可以双向查找
三.双向链表的缺点
1.结构较单向链表复杂。
2.占用内存比单项链表多。
四.双向链表的结构
五.双向链表的代码实现
function DoublyLinkedList() {
// 内部节点类
function Node(data) {
this.data = data
this.next = null
this.prev = null
}
//属性
this.head = null
this.tail = null
this.length = 0
// 1.append方法
DoublyLinkedList.prototype.append = function(data) {
var node = new Node(data)
if (this.length == 0) {
this.head = node
this.tail = node
} else {
node.prev = this.tail
this.tail.next = node
this.tail = node
}
this.length++
}
//2.将链表转化成字符串形式
// 2.1 toString
DoublyLinkedList.prototype.toString = function() {
return this.backwardString()
}
// 2.2 forwardString
DoublyLinkedList.prototype.forwardString = function() {
var current = this.tail
var resultString = ''
while (current) {
resultString += current.data + ' '
current = current.prev
}
return resultString
}
// 2.3 backwardString
DoublyLinkedList.prototype.backwardString = function() {
var current = this.head
var resultString = ''
while (current) {
resultString += current.data + ' '
current = current.next
}
return resultString
}
// 3.insert方法
DoublyLinkedList.prototype.insert = function(position, data) {
//越界判断
if (position<0 || position > this.length) return false
var node = new Node(data)
if (this.length == 0) { //列表的长度为0
this.head = node
this.tail = node
} else { //列表的长度不为0
if (position == 0) { //插入第一个位置
node.next = this.head
this.head.prev = node
this.head = node
} else if (this.length == position) { //插入最后一个位置
node.prev = this.tail
this.tail.next = node
this.tail = node
} else { //插入其他位置
var current = this.head
var index = 0
while ( index++ < position) {
current = current.next
}
node.prev = current.prev
node.next = current
current.prev.next = node
current.prev = node
}
}
this.lengt++
}
//4. get方法
DoublyLinkedList.prototype.get = function(position) {
if (position<0 || position >= this.length) return false
if (this.length / 2 > position) {
var current = this.head
var index = 0
while(index++ < position) {
current = current.next
}
return current.data
} else {
var current = this.tail
var index = 0
while (index++ < this.length - position - 1) {
current = current.prev
}
return current.data
}
}
// 5. indexOf 方法
DoublyLinkedList.prototype.indexOf = function(data) {
var index = 0
var current = this.head
while (current) {
if (current.data === data) {
return index
}
current = current.next
index++
}
return -1
}
// 6.updata方法
DoublyLinkedList.prototype.updata = function(position,data) {
if (position< 0 || position >= this.length) return false
var index = 0
var current = this.head
while (index++ < position) {
current = current.next
}
current.data = data
return true
}
// 7.removeAt方法
DoublyLinkedList.prototype.removeAt = function(position) {
if (position < 0 || position >= this.length) return null
var current = this.head
if (this.length == 1) {
this.head =null
this.tail =null
} else {
if (position == this.length - 1) {
current = this.tail
this.tail.prev.next = null
this.tail = this.tail.prev
} else if(position == 0) {
this.head.next.prev = null
this.head = this.head.next
} else {
var index = 0
while (index++ < position) {
current = current.next
}
current.prev.next = current.next
current.next.prev = current.prev
}
}
this.length--
return current
}
// 8.remove方法
DoublyLinkedList.prototype.remove = function(data) {
var index = this.indexOf(data)
return this.removeAt(index)
}
// 9.isEmpty方法
DoublyLinkedList.prototype.isEmpty = function() {
return this.length == 0
}
// 10.size方法
DoublyLinkedList.prototype.size = function() {
return this.length
}
//11.获取链表第一个元素
DoublyLinkedList.prototype.getHead = function() {
return this.head
}
//12.获取链表最后元素
DoublyLinkedList.prototype.gettail = function() {
return this.tail
}
}