// 链表
function LinkedList() {
this.head = new Node("Head")
this.head.parent = this
this.tail = this.head
this.self = this
this.length = 1
this.isCycle = false
}
LinkedList.prototype = {
constructor: LinkedList,
// 查找某个名为 item 的节点
// 返回该节点
find: function (item) {
var currNode = this.head
while (currNode.element !== item) {
currNode = currNode.next
if (!currNode) {
console.error(item + " is not exits.")
break
}
}
return currNode
},
// 在 item 的后面插入元素 newElement
insert: function (item, newElement) {
var current = this.find(item)
var newNode = new Node(newElement)
newNode.parent = this
newNode.next = current.next
current.next = newNode
newNode.previous = current
if (newNode.next) {
newNode.next.previous = newNode
} else {
this.tail = newNode
}
this.length++
},
// 删除名为 item 的节点
// 返回要删除的节点
remove: function (item) {
var current = this.find(item)
// 如果没找到这个节点
if (!current) {
return
}
this.length--
// 如果要删除的节点是尾节点
if (!current.next) {
this.tail = current.previous
current.previous.next = null
return current
}
// 如果要删除的节点是头节点
if (!current.previous) {
this.head = current.next
current.next.previous = null
return current
}
// 如果要删除的节点是中间的节点
current.previous.next = current.next
current.next.previous = current.previous
return current
},
// 反序输出链表
reverse: function () {
// 循环链表状态下禁止使用反序
// if(this.isCycle){
// console.warn("you can't use the methods of reverse under ths state of isCycle.")
// return
// }
var currNode = this.head
var temp
while (currNode && currNode.element) {
temp = currNode.next
currNode.next = currNode.previous
currNode.previous = temp
currNode = currNode.previous
// 循环状态下检测是否检测到头
if (currNode == this.head) {
break
}
}
temp = this.head
this.head = this.tail
this.tail = temp
return this
},
// 生成循环链表
cyclen: function () {
if (this.isCycle) {
return
}
this.head.previous = this.tail
this.tail.next = this.head
this.isCycle = true
return this
},
// 按照 两个元素将链表拆开
// 禁止在非循环状态下使用
// item_0 为 head
// item_1 为 tail
seprate: function (item_0, item_1) {
var tempHead = this.find(item_0)
var tempTail = this.find(item_1)
if (!this.isCycle) {
console.warn("you can't use this methods whthout the state of isCycle")
return
}
if (!tempHead || !tempTail) {
console.warn("please enter right type of Node")
return
}
if (tempHead.next !== tempTail) {
console.warn("the 2 item must be near")
return
}
this.head = tempHead
this.tail = tempTail
this.head.previous = null
this.tail.next = null
return this
}
}
// 节点
function Node(element) {
this.parent = null
this.element = element
this.previous = null
this.next = null
}
var linklist = new LinkedList();
linklist.insert("Head", "One")
linklist.insert("One", "Two")
linklist.insert("Two", "Three")
linklist.insert("Three", "Four")
linklist.insert("Four", "Five")
linklist.cyclen().reverse()
// linklist.cyclen()
// linklist.reverse()
console.dir(linklist);
网友评论