单向链表的缺点
只能从头遍历到尾，过程单向，很难回到上一个节点
双向链表的优点
可以双向遍历，既可以从头遍历到尾，也可以从尾遍历到头，有效解决了单向链表的缺点，实际开发中双向链表应用比单向链表多，但是实现较困难
双向链表
双向链表的常见操作
append(element)：向链表尾部添加新的元素
insert(position，element)：向链表的指定位置添加元素
get(position)：获取元素的位置
indexOf(element)：返回元素的下标值，没有则返回 -1
updata(position)：修改某个位置的元素
removeAt(position)：移除指定位置的元素
remove(element)：移除指定的元素
isEmpty()：查看链表长度，返回布尔值
size()：返回链表的长度
getHead()：获取第一个节点数据
getTail()：获取最后一个节点数据
toString()：按字符串输出链表的值
forwardString()：从后往前遍历，并一字符串形式输出
backwardString()：从前往后遍历，并一字符串形式输出
//封装双向链表
function doubleLinkedList() {
//属性
this.head = null
this.tail = null
this.length = 0
function Node(data) {
this.data = data
this.prev = null
this.next = null
}
//append方法
doubleLinkedList.prototype.append = function (data) {
//创建新节点
var newNode = new Node(data)
//是否是第一个节点
if (this.length == 0) {
this.head = newNode
this.tail = newNode
} else {
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
}
this.length += 1
}
//insert方法
doubleLinkedList.prototype.insert = function (position, data) {
//越界判断
if (position < 0 || position > this.length) return false
//创建新节点
var newNode = new Node(data)
//判断链表是否为空
if (this.length == 0) {
this.head = newNode
this.tail = newNode
} else {
//判断position的情况
if (position == 0) {
this.head.prev = newNode
newNode.next = this.head
this.head = newNode
} else if (position == length) {
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
} else {
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
//修改指针
newNode.next = current
newNode.prev = current.prev
current.prev.next = newNode
current.prev = newNode
}
}
this.length += 1
return true
}
//get方法
doubleLinkedList.prototype.get = function (position) {
if (position < 0 || position >= this.length) return null
if (this.length / 2 > position) {//从前往后
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
}
else {//从后往前
var current = this.tail
var index = this.length - 1
while (index-- > position) {
current = current.prev
}
}
return current.data
}
//indexOf方法
doubleLinkedList.prototype.indexOf = function (data) {
var current = this.head
var index = 0
//查找
while (current) {
if (current.data == data) {
return index
}
current = current.next
index += 1
}
return -1
}
//updata方法
doubleLinkedList.prototype.updata = function (position, newData) {
//越界判断
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
}
}else{
var current = this.tail
var index = this.length - 1
while (index-- > position) {
current = current.prev
}
}
//修改data
current.data = newData
return true
}
//removeAt方法
doubleLinkedList.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 == 0){//删除的是第一个节点
this.head.next.prev = null
this.head = this.head.next
}
else if(position == this.length - 1){
current = this.tail
this.tail.prev.next = null
this.tail = this.tail.prev
}else{
var index = 0
while(index++ < position){
current = current.next
}
current.prev.next = current.next
current.next.prev = current.prev
}
}
this.length -= 1
return current.data
}
//remove方法
doubleLinkedList.prototype.remove = function(data){
return this.removeAt(this.indexOf(data))
}
//isEmpty方法
doubleLinkedList.prototype.isEmpty = function(){
return this.length == 0
}
//size方法
doubleLinkedList.prototype.size = function(){
return this.length
}
//getHead方法
doubleLinkedList.prototype.getHead = function(){
return this.head.data
}
//getTail方法
doubleLinkedList.prototype.getTail = function(){
return this.tail.data
}
//toString方法
doubleLinkedList.prototype.toString = function () {
var current = this.head
var res = ""
//遍历
while (current) {
res += current.data + " "
current = current.next
}
return res
}
//forwardString方法
doubleLinkedList.prototype.forwardString = function () {
var current = this.tail
var res = ""
//遍历
while (current) {
res += current.data + " "
current = current.prev
}
return res
}
//backwardString方法
doubleLinkedList.prototype.backwardString = function () {
return this.toString()
}
}
END
网友评论