JavaScript 实现链表(LinkedList)
2019-03-14 本文已影响0人
没头脑很不高兴
单向链表
function Node(element) {
this.element = element
this.next = null
}
class LinkedList {
constructor() {
this.head = new Node("head")
}
find(item) {
let currentNode = this.head
while (currentNode.element !== item) {
currentNode = currentNode.next
}
return currentNode
}
insert(newElement, item) {
const newNode = new Node(newElement)
const currentNode = this.find(item)
newNode.new = currentNode.next
currentNode.next = newNode
}
display() {
let currentNode = this.head
while (currentNode.next !== null) {
console.log(currentNode.next.element)
currentNode = currentNode.next
}
}
findPrevious(item) {
let currentNode = this.head
while (currentNode.next !== null && currentNode.next.element !== item) {
currentNode = currentNode.next
}
return currentNode
}
remove(item) {
const previousNode = this.findPrevious(item)
if (previousNode.next !== null) {
previousNode.next = previousNode.next.next
}
}
}
const cities = new LinkedList()
cities.insert("Conway", "head")
cities.insert("Russellville", "Conway")
cities.insert("Carlisle", "Russellville")
cities.insert("Alma", "Carlisle")
cities.display()
cities.remove("Carlisle")
console.log('-------------')
cities.display()
双向链表
class Node {
constructor(element) {
this.element = element
this.next = null
this.previous = null
}
}
class LinkedList {
constructor() {
this.head = new Node('head')
}
find(item) {
let currentNode = this.head
while (currentNode.element !== item) {
currentNode = currentNode.next
}
return currentNode
}
insert(newElement, item) {
const newNode = new Node(newElement)
const currentNode = this.find(item)
newNode.next = currentNode.next
newNode.previous = currentNode
currentNode.next = newNode
}
display() {
let currentNode = this.head
while (currentNode.next !== null) {
console.log(currentNode.next.element)
currentNode = currentNode.next
}
}
remove(item) {
const currentNode = this.find(item)
if (currentNode !== null) {
// 父节点的子节点换成当前节点的下节点
currentNode.previous.next = currentNode.next
// 子节点的父节点换成当前节点的父节点
currentNode.next.previous = currentNode.previous
// 销毁这个节点
currentNode.next = null
currentNode.previous = null
}
}
findLastNode() {
let currentNode = this.head
while (currentNode.next !== null) {
currentNode = currentNode.next
}
return currentNode
}
// 反序显示双向链表的元素
displayReverse() {
// 将第一个父节点换成最后一个
let currentNode = this.head
currentNode = this.findLastNode()
while (currentNode !== null) {
console.log('----', currentNode.element)
currentNode = currentNode.previous
}
}
}
未完待续