重读《学习JavaScript数据结构与算法

定场诗

伤情最是晚凉天，憔悴厮人不堪言；

邀酒摧肠三杯醉.寻香惊梦五更寒。

钗头凤斜卿有泪，荼蘼花了我无缘；

小楼寂寞新雨月.也难如钩也难圆。

前言

本章为重读《学习JavaScript数据结构与算法》的系列文章，该章节主要讲述数据结构-链表，以及实现链表的过程和原理。

链表

链表，为什么要有这种数据结构呢？当然，事出必有因！

数组-最常用、最方便的数据结构，But，当我们从数组的起点或中间插入或移动项的成本很高，因为我们需要移动数组元素。

链表，是存储有序的元素集合。链表中的元素在内存中并不是连续放置的，每个元素由一个存储自身的元素节点和一个指向下一个元素的引用(指针或链接)组成。

这个是重点，注意，圈起来，面试肯定考！

实现链表

我们要实现链表的结构以及对应的方法，大致为：元素插入、移除、获取链表长度、查询元素、是否为空等等...更详细可看代码实现逻辑。

数据结构越来越复杂喽...注意领会精神...

/**

class Node {

constructor(element) {

this.element = element

this.next = undefined

}

}

/**

function defaultEquals (a, b) {

return a === b

}

/**

class LinkedList {

constructor (equalsFn = defaultEquals) {

// 链表长度

this.count = 0

// 第一个元素引用

this.head = undefined

// 用于比较元素是否相等，默认为defaultEquals，允许传入自定义的函数来比较两个对象是否相等。

this.equalsFn = equalsFn

}

}

注意：equalsFn参数，在比较对象类元素时，需要传递自定义方法来比较两个对象的的值是否相等。

push()

向链表的尾部添加元素

/**

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 (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 (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 (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 (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 (element) {

// 获取索引位置

let index = this.indexOf(element)

// 移除指定索引位置的元素

return this.removeAt(index)

}

size()

获取链表长度

/**

size () {

return this.count

}

isEmpty()

判断链表是否为空

/**

isEmpty () {

return this.count === 0

}

getHead()

获取链表首位元素

getHead () {

if (this.head != null) {

return this.head.element

}

return undefined

}

clear()

清空链表

/**

clear () {

this.count = 0

this.head = undefined

}

toString()

链表字符串处理

/**

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!

后记

以上就是胡哥今天给大家分享的内容，喜欢的小伙伴记得收藏、转发、点击右下角按钮在看，推荐给更多小伙伴呦，欢迎多多留言交流...

胡哥有话说，一个有技术，有情怀的胡哥！京东开放平台首席前端攻城狮。与你一起聊聊大前端，分享前端系统架构，框架实现原理，最新最高效的技术实践！

长按扫码关注，更帅更漂亮呦！关注胡哥有话说公众号，可与胡哥继续深入交流呦！

相关知识

机器学习算法
JavaScript DOM 编程艺术 （第二版）学习之1
javascript dom 编程艺术pdf javascript dom编程艺术pdf下载网盘
实践计划进度etc.临时
数据结构
《JavaScript
计算机经典书籍电子书合集(适合计算机学生学习以及程序员笔试、面试)
Python机器学习基础教程
机器学习术语表——Beta
[机器学习基础][笔记] 一、鸢尾花分类

网址: 重读《学习JavaScript数据结构与算法 https://www.huajiangbk.com/newsview105915.html