1 Star 1 Fork 0

CoderMonkey/data-struct-js

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
DoublyLinkedList.js 7.33 KB
一键复制 编辑 原始数据 按行查看 历史
import { LinkedList } from './LinkedList'
import {
isFunction,
} from '../common/toollib'
import {
LinkedListNode,
loopToFind,
needReversal,
doublyFindAt,
} from './LinkedListNode'
/**
* 双向链表
*
* @export DoublyLinkedList
* @class DoublyLinkedList
* @extends {LinkedList}
*/
export class DoublyLinkedList extends LinkedList {
constructor(customizedComparer = null) {
super(customizedComparer)
}
/**
* 向链表末尾添加数据
*
* @param {*} data 链表元素的数据
* @returns true
* @memberof DoublyLinkedList
*/
append(data) {
let newNode = new LinkedListNode(data)
// 1.判断链表是否为空
if (this.isEmpty) {
// 新元素既是首也是尾
this.__head = newNode
this.__tail = newNode
}
// 2.非空链表时,添加到尾部
else {
this.__tail.next = newNode
newNode.prev = this.__tail
this.__tail = newNode
}
// 3.计数加1
this.__count += 1
return true
}
/**
* 向链表指定位置插入元素
*
* @param {number} position 插入位置
* @param {*} data
* @returns 插入结果:true/false
* @memberof DoublyLinkedList
*/
insert(position, data) {
// 1.边界检查(插入位置)
if (position < 0 || position > this.__count) return false
let newNode = new LinkedListNode(data)
// 2.插入元素时链表为空
if (this.isEmpty) {
this.__head = newNode
this.__tail = newNode
}
// 3.链表非空
else {
// 3.1插入到链表头部
if (position === 0) {
newNode.next = this.__head
this.__head.prev = newNode
this.__head = newNode
}
// 3.2插入到链表尾部
else if (position === this.__count) {
this.__tail.next = newNode
newNode.prev = this.__tail
this.__tail = newNode
}
// 3.3以外
else {
let current = doublyFindAt(this.size, position, this.__head, this.__tail)
current.prev.next = newNode
newNode.prev = current.prev
newNode.next = current
current.prev = newNode
}
}
// 4.计数加1
this.__count += 1
return true
}
/**
* 删除链表指定位置元素
*
* @param {number} position 位置下标
* @returns 删除结果:true/false
* @memberof DoublyLinkedList
*/
removeAt(position) {
// 1.边界检查
if (position < 0 || position >= this.__count) return false
// 2.只有一个元素
if (this.size === 1) {
this.__head = null
this.__tail = null
}
// 3.多个元素的情况
else {
// 3.1 删首
if (position === 0) {
this.__head = current.next
current.next.prev = null
}
// 3.2 删尾
else if (position === this.__count - 1) {
this.__tail = this.__tail.prev
this.__tail.next = null
}
// 3.3 以外
else {
let current = doublyFindAt(this.size, position, this.__head, this.__tail)
current.prev.next = current.next
current.next.prev = current.prev
}
}
// 4.计数减1
this.__count -= 1
return true
}
/**
* 删除指定数据的元素
*
* @param {*} data 元素数据
* @returns 返回删除的元素数据
* @memberof DoublyLinkedList
*/
remove(data) {
// 1.根据指定数据取得下标值
let index = this.indexOf(data)
// 2.检查下标值是否正常取到
if (index === -1) return false
// 3.根据取到的下标,调用 removeAt 方法进行删除
return this.removeAt(index)
}
/**
* 更新指定位置元素
*
* @param {number} position 位置下标
* @param {*} data 更新的数据
* @returns 更新结果:成功true/失败false
* @memberof DoublyLinkedList
*/
update(position, data) {
// 1.边界检查
if (position < 0 || position >= this.__count) return false
// 2.找到指定下标位置元素(根据所处位置从头或从尾查找)
let targetNode = doublyFindAt(this.size, position, this.__head, this.__tail)
// 3.修改数据
targetNode.data = data
return true
}
/**
* 获取指定位置元素的数据
*
* @param {number} position 位置下标
* @returns 元素的数据
* @memberof DoublyLinkedList
*/
findAt(position) {
// 1.边界检查
if (position < 0 || position >= this.__count) return undefined
// 2.判断该位置处于链表前半部分还是后半部分
// 前半部分的时候,从 head 开始查找
// 后半部分的时候,从 tail 开始查找
const reversal = needReversal(this.size, position)
// 3.找到指定位置元素
const current = reversal ?
loopToFind(position, this.__tail, this.size - 1) :
loopToFind(position, this.__head, null)
// 4.返回该节点元素的数据部分
return current.data
}
/**
* 根据指定元素数据获取在链表中的位置下标
*
* @param {*} data
* @returns 位置下标
* @memberof DoublyLinkedList
*/
indexOf(data) {
let index = 0
let current = this.__head
// 根据指点数据查找节点元素
while (current) {
if (this.__comparator(current.data, data)) {
return index
}
current = current.next
index += 1
}
// 没有找到符合的节点元素
return -1
}
/**
* 从尾元素开始遍历
*
* @param {function} callback
* @memberof DoublyLinkedList
*/
backwardTraverse(callback) {
// 参数检查(回调函数)
if (!callback || !isFunction(callback)) return
// 起始元素设为 tail
let current = this.__tail
// 尾部起始,向前遍历
while (current) {
callback(current.data)
current = current.prev
}
}
/**
* 从首元素开始遍历
*
* @param {function} callback
* @memberof DoublyLinkedList
*/
forwardTraverse(callback) {
// 参数检查(回调函数)
if (!callback || !isFunction(callback)) return
// 起始元素设为 head
let current = this.__head
// 头部起始,向后遍历
while (current) {
callback(current.data)
current = current.next
}
}
/**
* 根据指定顺序,遍历双向链表
*默认为 forwardTravase
* @param {function} callback
* @param {boolean} [reversal=false]
* @memberof DoublyLinkedList
*/
traverse(callback, reversal = false) {
reversal
?
this.backwardTraverse(callback) :
this.forwardTraverse(callback)
}
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
JavaScript
1
https://gitee.com/coder-monkey/data-struct-js.git
git@gitee.com:coder-monkey/data-struct-js.git
coder-monkey
data-struct-js
data-struct-js
master

搜索帮助