定场诗
伤情最是晚凉天，憔悴厮人不堪言；
邀酒摧肠三杯醉.寻香惊梦五更寒。
钗头凤斜卿有泪，荼蘼花了我无缘；
小楼寂寞新雨月.也难如钩也难圆。
前言
本章为重读《学习JavaScript数据结构与算法》的系列文章，该章节主要讲述数据结构-链表，以及实现链表的过程和原理。
链表
链表，为什么要有这种数据结构呢？当然，事出必有因！
数组-最常用、最方便的数据结构，But，当我们从数组的起点或中间插入或移动项的成本很高，因为我们需要移动数组元素。
链表，是存储有序的元素集合。链表中的元素在内存中并不是连续放置的，每个元素由一个存储自身的元素节点和一个指向下一个元素的引用(指针或链接)组成。
这个是重点，注意，圈起来，面试肯定考！
实现链表
我们要实现链表的结构以及对应的方法，大致为：元素插入、移除、获取链表长度、查询元素、是否为空等等...更详细可看代码实现逻辑。
数据结构越来越复杂喽...注意领会精神...
/**
* Node 节点类，用于生成自身节点与下一个元素的引用
*/
class Node {
constructor(element) {
this.element = element
this.next = undefined
}
}
/**
* defaultEquals() 用于比较两个非对象类的值是否相等
*/
function defaultEquals (a, b) {
return a === b
}
/**
* LinkedList 链表
* 特点：链表存储有序的元素集合，但元素在内存中并不连续存放。每个元素有一个存储元素本身的节点和一个指向下一个元素的引用
*/
class LinkedList {
constructor (equalsFn = defaultEquals) {
// 链表长度
this.count = 0
// 第一个元素引用
this.head = undefined
// 用于比较元素是否相等，默认为defaultEquals，允许传入自定义的函数来比较两个对象是否相等。
this.equalsFn = equalsFn
}
}
注意：equalsFn参数，在比较对象类元素时，需要传递自定义方法来比较两个对象的的值是否相等。
push()
向链表的尾部添加元素
/**
* push() 添加元素到链表
* @param {*} element 待添加的元素
*/
push (element) {
let node = new Node(element)
let current
// 判断链表是否为空
if (this.head == null) {
this.head = node
} else {
// 查询最后的元素 - 特点 current.next == null
current = this.head
while (current.next != null) {
current = current.next
}
// 将最后元素的下一个元素引用指向node
current.next = node
}
this.count++
}
getElementAt()
获取指定索引位置的元素
/**
* getElementAt() 返回索引位置元素
* @param {Number} index 索引位置
* @returns {*} node
*/
getElementAt (index) {
// 判断索引是否有效
if (index < 0 || index > this.count) {
return undefined
}
let node = this.head
for (let i = 0; i < index && node != null; i++) {
node = node.next
}
return node
}
insert()
在任意索引位置插入元素
/**
* insert() 在任意位置插入元素
* @param {*} element 待插入的元素
* @param {Number} index 指定的索引位置
* @returns {Boolean}
*/
insert (element, index) {
// 判断是否为合法index
if (index < 0 || index > this.count) {
return false
}
// 实例化节点
let node = new Node(element)
// 插入-第一个位置
if (index === 0) {
let current = this.head
node.next = current
this.head = node
} else {
// 查找到指定索引位置的前一个元素
let previous = this.getElementAt(index - 1)
let current = previous.next
// 将上一个元素的next引用指向当前新添加的node，将node的next引用指向current，则完成插入
previous.next = node
node.next = current
}
// 链表长度+1
this.count++
return true
}
removeAt()
移除指定索引位置的元素
实现逻辑：判断是否为链表第一项，若为第一项，则将this.head指向第二个元素即可；如果不是第一项，则获取索引index位置的上一位置索引元素previous，以及下一位置索引元素current.next，将previous.next指向current.next即可
/**
* removeAt() 移除指定位置的元素
* @param {Number} index
* @returns {*} element 移除的元素
*/
removeAt (index) {
// 判断是否是合法索引
if (index < 0 || index > this.count) {
return undefined
}
let current = this.head
// 考虑是否是链表第一项
if (index === 0) {
this.head = current.next
} else {
// 方法一、 使用for循环迭代获取指定索引位置的元素
// 用于获取上一位置元素
// let previous
// for (let i = 0; i < index; i++) {
// previous = current
// current = current.next
// }
// // 跳过当前元素，将上一个元素的next指向下一个元素
// previous.next = current.next
// 方法二、借助getElementAt()方法
// 查询该索引位置的上一个元素
let previous = this.getElementAt(index - 1)
// 跳过中间元素，将上一个元素的next指向下一个元素
current = previous.next
previous.next = current.next
}
this.count--
return current.element
}
indexOf()
查询元素的索引位置
实现逻辑：迭代元素，比较每一个元素与目标元素是否相等；特别需要注意的是，对象类的值请传入自定义的方法进行比较是否相等s
/**
* indexOf() 查询元素的索引位置
* @param {*} element 待查询的元素
* @returns {Number} index 索引位置，不存在则返回-1
*/
indexOf (element) {
let current = this.head
for (let i = 0; i < this.count && current != null; i++) {
// 判断两个元素是否相同
if (this.equalsFn(element, current.element)) {
return i
}
current = current.next
}
return - 1
}
remove()
移除指定的元素
/**
* remove() 移除元素
* @param {*} element 待移除的元素
* @returns {*} element 移除的元素
*/
remove (element) {
// 获取索引位置
let index = this.indexOf(element)
// 移除指定索引位置的元素
return this.removeAt(index)
}
size()
获取链表长度
/**
* size() 返回链表长度
* @returns {Number} 链表长度
*/
size () {
return this.count
}
isEmpty()
判断链表是否为空
/**
* isEmpty() 判断链表是否为空
* @returns {Boolean}
*/
isEmpty () {
return this.count === 0
}
getHead()
获取链表首位元素
/**
* getHead() 获取链表首位元素
* @returns {*}
*/
getHead () {
if (this.head != null) {
return this.head.element
}
return undefined
}
clear()
清空链表
/**
* clear() 清空链表
*/
clear () {
this.count = 0
this.head = undefined
}
toString()
链表字符串处理
/**
* toString() 链表字符串化展示
* @returns {String}
*/
toString () {
// 判断是否为空
if (this.isEmpty()) {
return ''
}
let objStr = `${this.head.element}`
let current = this.head.next
for (let i = 1; i < this.count; i++) {
objStr = `${objStr},${current.element}`
current = current.next
}
return objStr
}
使用链表
let linkedList = new LinkedList()
console.log(linkedList.isEmpty()) // true
// push 尾部压入元素
linkedList.push(15)
linkedList.push(20)
/*
LinkedList {
count: 2,
head: Node {
element: 15,
next: Node {
element: 20,
next: undefined
}
},
equalsFn: [Function: defaultEquals]
}
*/
console.log(linkedList)
console.log(linkedList.isEmpty()) // false
// getElementAt() 指定索引位置的元素
let node = linkedList.getElementAt(1)
console.log(node)
// insert() 任意索引位置插入元素
linkedList.insert(22, 1)
linkedList.insert(33, 1)
console.log(linkedList.toString()) // 15,33,22,20
// removeAt() 移除指定索引位置的元素
console.log(linkedList.removeAt(1)) // 33
// remove() 移除元素
console.log(linkedList.remove(15)) // 15
console.log(linkedList.toString()) // 22,20
console.log(linkedList.getHead()) // 22
console.log(linkedList.size()) // 2
console.log(linkedList.toString()) // 22,20
console.log(linkedList.isEmpty()) // false
linkedList.clear()
console.log(linkedList.isEmpty()) // true
再次强调下：如果链表中存储的是对象类型值，请务必传入指定的比较函数equalsFn自行进行比较，You should know why!
后记
以上就是胡哥今天给大家分享的内容，喜欢的小伙伴记得收藏、转发、点击右下角按钮在看，推荐给更多小伙伴呦，欢迎多多留言交流...
胡哥有话说，一个有技术，有情怀的胡哥！京东开放平台首席前端攻城狮。与你一起聊聊大前端，分享前端系统架构，框架实现原理，最新最高效的技术实践！
长按扫码关注，更帅更漂亮呦！关注胡哥有话说公众号，可与胡哥继续深入交流呦！
胡哥有话说
网友评论