JavaScript 的数据结构和算法 - 链表代码篇
JavaScript 版本的链表实现
这篇文章主要是针对上一篇文章的代码实践,更多相关介绍请 移步。
构建
整个链表是基于 JavaScript 的类来实现的
constructor() {
/**
* @type {LinkedListNode}
*/
this.head = null
/**
* @type {LinkedListNode}
*/
this.tail = null
/**
* The size of Linked list
* @type {number}
*/
this.count = 0
}
根据数组来构建链表
/**
* Building Linked list by array.
* @param {array} array
*/
build(array) {
this.count = array.length
for (let i = 0; i < array.length; i++) {
const newNode = new LinkedListNode(array[i])
this.__insertToEnd(newNode)
}
}
主要的方法实现
大的来说,这儿主要就实现两个方法,插入和删除。
/**
* Append element to the end of the linked list
* @param value
* @returns {LinkedList}
*/
append(value) {
const newNode = new LinkedListNode(value)
this.__insertToEnd(newNode)
this.count++
return this
}
删除这儿会稍微麻烦一点儿,需要逐个去查找(默认会出现重复项)
/**
* Delete element when it equal the pass value.
* @param value
* @returns {null}
*/
delete(value) {
if (!this.head) {
return null
}
let deleteNode = null
// Delete element when position is head.
while (this.head && this.head.value === value) {
deleteNode = this.head
this.head = this.head.next
this.count--
}
let currentNode = this.head
// Delete element when item's position is between head and tail.
if (currentNode !== null) {
while (currentNode.next) {
if (value === currentNode.next.value) {
deleteNode = currentNode.next
currentNode.next = currentNode.next.next
this.count--
} else {
currentNode = currentNode.next
}
}
}
// Delete element when item's position is tail.
if (value === this.tail.value) {
this.tail = currentNode
this.count--
}
return deleteNode
}
结束语
另外,有个 __insertToEnd
作为内部方法,感兴趣的可以去看看源码。还有就是本系列文章是利用 AVA 做为测试框架的,如果有人感兴趣的话,后续会另外开一篇文章详细介绍。
源码详见 https://github.com/MasterShu/JavaScript-Da...
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: