JavaScript版数据结构与算法——基础篇（一）

标签：结构   node   程序   ons   内存   ever   简单   前端   define   这是之前学习记录的一篇文章，最近准备面试复习一下，内容做了些修修补补，如有错误欢迎指出 本文来自于学习 《JavaScript数据结构与算法(第3版)》 以及网路资料，如有不对请指正。作为软件开发工作者，可能你听过这么一句话：程序 = 数据结构 + 算法。可见数据结构和算法在我们的编码工作中是非常的重要的。如果我们使用了不恰当的数据结构或者算法，可能会影响我们程序的性能。总之，对于算法和数据结构，我们只需要撸起袖子加油学。 数组 数组——最简单的内存数据结构 数组存储一系列同一种数据类型的值。（ Javascript 中不存在这种限制） 对数据的随机访问，数组是更好的选择，否则几乎可以完全用 「链表」 来代替 在很多编程语言中，数组的长度是固定的，当数组被填满时，再要加入新元素就很困难。Javascript 中数组不存在这个问题。但是 Javascript 中的数组被实现成了对象，与其他语言相比，效率低下。数组的一些核心方法 方法 描述push 方法将一个或多个元素添加到数组的末尾，并返回该数组的新长度。(改变原数组)pop 方法从数组中删除最后一个元素，并返回该元素的值。(改变原数组)shift 方法从数组中删除第一个元素，并返回该元素的值，如果数组为空则返回 undefined 。(改变原数组)unshift 将一个或多个元素添加到数组的开头，并返回该数组的新长度(改变原数组)concat 连接两个或多个数组，并返回结果（返回一个新数组，不影响原有的数组。）every 对数组中的每个元素运行给定函数，如果该函数对每个元素都返回 true，则返回 true。若为一个空数组，，始终返回 true。 （不会改变原数组，[].every(callback)始终返回 true）some 对数组中的每个元素运行给定函数，如果任一元素返回 true，则返回 true。若为一个空数组，，始终返回 false。（不会改变原数组，）forEach 对数组中的每个元素运行给定函数。这个方法没有返回值，没有办法中止或者跳出 forEach() 循环，除了抛出一个异常（foreach不直接改变原数组，但原数组可能会被 callback 函数该改变。）map 对数组中的每个元素运行给定函数，返回每次函数调用的结果组成的数组（map不直接改变原数组，但原数组可能会被 callback 函数该改变。）sort 按照Unicode位点对数组排序，支持传入指定排序方法的函数作为参数（改变原数组）reverse 方法将数组中元素的位置颠倒，并返回该数组（改变原数组）join 将所有的数组元素连接成一个字符串indexOf 返回第一个与给定参数相等的数组元素的索引，没有找到则返回 -1lastIndexOf 返回在数组中搜索到的与给定参数相等的元素的索引里最大的值，没有找到则返回 -1slice 传入索引值，将数组里对应索引范围内的元素（浅复制原数组中的元素）作为新数组返回（原始数组不会被改变）splice 删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容(改变原数组)toString 将数组作为字符串返回valueOf 和 toString 类似，将数组作为字符串返回栈 栈是一种遵循后进先出（LIFO）原则的有序集合，新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。通俗来讲，就是你向一个桶里放书本或者盘子，你要想取出最下面的书或者盘子，你必须要先把上面的都先取出来。 栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录 (浏览器的返回按钮)。 代码实现 // 封装栈 function Stack() { // 栈的属性 this.items = [] // 栈的操作 // 1.将元素压入栈 Stack.prototype.push = function (element) { this.items.push(element) } // 2.从栈中取出元素 Stack.prototype.pop = function () { return this.items.pop() } // 3.查看栈顶元素 Stack.prototype.peek = function () { return this.items[this.items.length - 1] } // 4.判断是否为空 Stack.prototype.isEmpty = function () { return this.items.length === 0 } // 5.获取栈中元素的个数 Stack.prototype.size = function () { return this.items.length } // 6.toString()方法 Stack.prototype.toString = function () { let str = ‘‘ for (let i = 0; i this.length) return false let newNode = new Node(data) if (position == 0) { newNode.next = this.head this.head = newNode } else { let index = 0 let current = this.head let prev = null while (index++ = this.length) return null let index = 0 let current = this.head while (index++ = this.length) return false let index = 0 let current = this.head while (index++ = this.length) return null if (position == 0) { this.head = this.head.next } else { let index = 0 let current = this.head let prev = null while (index++ this.length) return false let newNode = new Node(data) if (this.length === 0) { this.head = newNode this.tail = newNode } else { if (position == 0) { this.head.prev = newNode newNode.next = this.head this.head = newNode } else if (position == this.length) { newNode.prev = this.tail this.tail.next = newNode this.tail = newNode } else { let current = this.head let index = 0 while( index++ = this.length) return null let current = this.head let index = 0 while (index++) { current = current.next } return current.data } doublyLinkedList.prototype.indexOf = function (data) { let current = this.head let index = 0 while (current) { if (current.data === data) { return index } current = current.next index++ } return -1 } doublyLinkedList.prototype.update = function (position, newData) { if (position = this.length) return false let current = this.head let index = 0 while(index++ = this.length) return null let current = this.head if (this.length === 1) { this.head = null this.tail = null } else { if (position === 0) { // 删除第一个节点 this.head.next.prev = null this.head = this.head.next } else if (position === this.length - 1) { // 删除最后一个节点 this.tail.prev.next = null this.tail = this.tail.prev } else { let index = 0 while (index++