//双向链表
function DoubleLinkedList() {
function Node(value) {
this.value = value
this.next = null
this.prev = null
}
//链表头节点
this.head = null
//链表尾节点
this.fail = null
//链表长度
this.length = 0
//在链表尾部添加元素
DoubleLinkedList.prototype.append = function (value) {
var newElement = new Node(value)
if (!this.head) {
this.head = newElement
this.fail = newElement
} else {
var current = this.fail
while (current.next) {
current = current.next
}
newElement.prev = current
current.next = newElement
this.fail = current.next
}
this.length += 1
return true
}
//链表从前向后打印成字符串
DoubleLinkedList.prototype.forwardToString = function () {
var current = this.head
var result = ‘‘
while (current) {
result += current.value + ‘ ‘
current = current.next
}
return result
}
//链表从后向前打印成字符串
DoubleLinkedList.prototype.backwardToString = function () {
var current = this.fail
var result = ‘‘
while (current) {
result += current.value + ‘ ‘
current = current.prev
}
return result
}
//选择位置插入元素
DoubleLinkedList.prototype.insertTo = function (value, position) {
//越界判断
if (position >= this.length || position < 0) {
return false
}
var newElement = new Node(value)
var index = 0
var current = this.head
//判段插入元素的位置做不同的处理
if (position === 0) {
//插入链表头
current.prev = newElement
current.prev.next = current
this.head = current.prev
} else {
while (index < position) {
//插入位置的前一个元素
var pervElement = current
index++
current = current.next
}
newElement.prev = pervElement
pervElement.next = newElement
pervElement.next.next = current
current.prev = pervElement.next
}
this.length++
return true
}
//改变某个位置的值
DoubleLinkedList.prototype.update = function (value, position) {
if (position >= this.length || position < 0) {
return false
}
var index = 0
var current = this.head
while (index < position) {
index ++
current = current.next
}
current.value = value
return true
}
//获取某个位置的值
DoubleLinkedList.prototype.get = function (position) {
//越界判断
if (position >= this.length || position < 0) {
return false
}
var index = 0
var current = this.head
while (index < position) {
current = current.next
}
return current.value
}
//获取某个元素的索引
DoubleLinkedList.prototype.indexOf = function (value) {
var current = this.head
var index = 0
while (current) {
if (current.value == value) {
return index
}
index++
current = current.next
}
return -1
}
//删除某个位置的元素
DoubleLinkedList.prototype.removeTo = function (position) {
//越界判断
if (position >= this.length || position < 0) {
return false
}
var index = 0
var current = this.head
if (position == 0) {
current = current.next
current.prev = null
this.head = current
} else {
while (index < position) {
//删除元素的前一个元素
var prevElement = current
index++
current = current.next
}
prevElement.next = current.next
current.next.prev = prevElement
if (this.length - 1 == position) {
this.fail = prevElement
}
}
this.length--
}
//删除某个元素
DoubleLinkedList.prototype.remove = function (value) {
var index = this.indexOf(value)
return this.removeTo(index)
}
//查看链表是否为空
DoubleLinkedList.prototype.isEmpty = function () {
return this.length == 0
}
//查看链表的长度
DoubleLinkedList.prototype.size = function () {
return this.length
}
}
