前言
【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)
源代码有三个:ES6(单个单个的 class 类型的 js 文件) | JS + HTML(一个 js 配合一个 html)| JAVA (一个一个的工程)
全部源代码已上传 github,点击我吧,光看文章能够掌握两成,动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群,文章风格一如既往如此,就觉得手机上看起来比较方便,这样显得比较有条理,整理这些笔记加源码,时间跨度也算将近半年时间了,希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
链表
- 链表是最基础的动态数据结构
- 链表是非常重要的线性数据结构
- 以下三种,底层都是依托静态数组,靠 resize 解决固定容量问题。
- 动态数组:所谓动态,是从用户的角度上来看的。
- 栈
- 队列
- 链表是真正的动态数据结构
- 它是数据结构中的一个重点,
- 也有可能是一个难点,
- 它是最简单的一种动态数据结构,
- 其它更高级的动态数据结构有 二分搜索树、Trie、
- 平衡二叉树、AVL、红黑树等等,
- 熟悉了最简单的动态数据结构,
- 那么对于更高级的也会比较容易掌握了。
- 对于链表来说它涉及到了计算机领域一个非常重要的概念
- 更深入的理解引用(或者指针),
- 这个概念和内存相关,
- 在 JS 里面不需要手动的管理内存,
- 但是对链表这种数据结构更加深入的理解,
- 可以让你对 引用、指针甚至计算机系统中
- 和内存管理相关很多话题有更加深入的认识。
- 链表本身也是有它非常清晰的递归结构的,
- 只不过由于链表这种数据结构它本身是一种线性的数据结构,
- 所以依然可以非常容易的使用循环的方式来对链表进行操作,
- 但是链表本身由于它天生也是具有这种递归结构的性质,
- 所以它也能让你更加深入的理解递归机制相应的这种数据结构,
- 在学习更加复杂的数据结构的时候,
- 对递归这种逻辑机制深入的理解是必不可缺的。
- 链表这种数据结构本身就具有功能性
- 它可以用来组成更加复杂的数据结构,
- 比如 图结构、hash 表、栈(链表版)、队列(链表版),
- 所以他可以辅助组成其它数据结构。
什么是链表
- 数据存储在“节点”(Node)中
- 把数据存在一种单独的结构中,
- 这个结构通常管它叫做节点,
- 对于链表节点来说他通常只有两部分,
- 一部分就是存储真正的数据,
- 另一部分存储的是当前节点的下一个节点,
- 链表其实就像一个火车,每一个节点都是一节车厢,
- 在车厢中存储数据,而车厢和车厢之间还会进行连接,
- 以使得这些数据是整合在一起的,
- 这样用户可以方便的在所有的这些数据上进行查询等等其它的操作,
- 数据与数据之间连接就是用下面的这个 next 来完成的
class Node { e; //Element next; //Node }
- 链表的优点
- 真正的动态,不需要处理固定容量的问题,
- 它不像静态数组那样一下子 new 出来一片空间,
- 也根本不需要考虑这个空间是不是不够用,
- 也根本不用去考虑这个空间是不是开多了。
- 对于链表来说,你需要多少个数据。
- 你就可以生成多少个节点,
- 把它们挂接起来了,这就是所谓的动态。
- 链表的缺点
- 和数组相比,它丧失了随机访问的能力。
- 不能像数组那样给一个索引
- 就能直接访问对应索引位置的元素,
- 这是因为从底层机制上数组所开辟的空间
- 在内存里是连续分布的,
- 所以才能够直接去向索引对应的偏移
- 计算出相应的数据所存储的内存地址,
- 然后就能够直接用
O(1)
的复杂度取出这个元素, - 但是链表不同,链表由于是靠 next 一层一层连接的,
- 所以在计算机的底层,每一个节点他所在的内存的位置是不同的,
- 只能够靠这个 next 来一层一层的找到这个元素,
- 这就是链表最大的缺点。
数组和链表的对比
-
数组
- 数组最好永远索引有语意的情况,如
scores[2]
- 最大的优点:支持快速查询
- 数组最好永远索引有语意的情况,如
-
链表
- 链表不适合用于索引有语意的情况。
- 最大的优点:动态存储。
-
对比
- 数组也可以没有语意,并不是所有的时候索引是有语意的,
- 也并不是所有有语意的这样的一个标志就适合做索引,如身份证号,
- 将一个静态数组改变为一个动态数组,
- 就是在应付不方便使用索引的时候有关数据存储的问题,
- 对于这样的存储数据的需求使用链表是更合适的,
- 因为链表最大的优点是动态存储。
-
要清楚什么时候使用数组这样的静态数据结构,
- 什么时候使用链表这类的动态数据结构。
-
简单的代码示例
MyLinkedList
class MyLinkedListNode { constructor(element = null, next = null) { this.element = element; this.next = next; } // toString 2018-10-20-jwl toString() { return this.element.toString(); } } class MyLinkedList { constructor() {} }
在链表中进行添加、插入操作
- 链表是通过节点来装载元素
- 并且节点和节点之间会进行连接。
- 如果想访问这条链表中所有的节点,
- 那么就必须把链表的头给存储起来,
- 通常这个链表的头叫做的 head,
- 应该说在
MyLinkedList
中 - 应该有一个变量指向链表中的第一个节点。
- 给自定义数组添加元素是从数组尾部开始添加,
- 给链表添加元素是从数组头部开始添加,
- 因为自定义数组有维护一个 size,
- 这个 size 指向的是下一个待添加元素的位置,
- 所以你直接将 size 做索引直接赋值即可,
- 有 size 这个变量在跟踪数组的尾巴,
- 而对于链表来说 有设置一个链表的头这样的一个变量,
- 也就是说有一个变量在跟踪链表的头,
- 并没有一个变量去跟踪链表的尾巴,
- 所以在链表头部添加元素是非常方便。
- 添加操作原理
- 将一个新的元素挂接到链表头部,
- 同时不破坏现在链表的这个结构,
- 添加一个新元素 666,它的名字叫 node,
- 就只需要使用
node.next = head
, - 也就是将新添加的元素的 next 指向链表的头,
- 这个时候新添加的元素也成为新的链表头,
- 也就是
head = node
, - 这样 head 就会指向新的元素 666,也就是 node 这个节点,
- 如此一来就完成了将 node 这个节点插入了整个链表的头部,
- node 这个变量是在一个函数中声明的,
- 所以函数结束之后这个变量的作用域也就结束了,
- 链表的 head 也等于 node,
- 链表中就新增了一个新元素。
- 在链表头部添加元素非常简单,
- 只需要创建节点,让节点的 next 指向 head,
- 然后让 head 重新指向这个节点,也就是让 head 变成新的元素,
- 因为链表是从头部添加元素的。
- 在链表中间添加元素,
- 定义一个 prev 的变量指向中间元素的前一个元素,
- 然后让新增加的元素这样,
node.next = prev.next
, - 之后这样,
prev.next = node
, - 这样一来就在 prev 这个元素和原本 prev 的下一个元素之间
- 插入了一个新元素,叫做 node,
- 整个过程就是将 prev 的 next(下一个元素)的引用
- 传递给新元素的 next(下一个元素),
- 然后将 prev 的 next(下一个元素)变更为这个新元素,
- 最后就将新元素插入到中间了。
- 这个过程的关键是找到待添加的节点的前一个节点,
- 这个就是 prev 变量要做的事情。
- 在链表的操作中很多时候顺序非常重要,
- 如在链表中插入一个元素,在指定的元素后面插入一个元素,
- 并且不影响整个链表结构,和在链表中间添加元素一样,
- 把原本的
node.next = prev.next
和prev.next = node
- 的顺序变一下,
prev.next = node
在前, node.next = prev.next
在后,这样一来逻辑就不成立了,- 链表不仅断开了,而且新节点的 next 指向的是自己,死循环了,
- 所以一样的代码,顺序颠倒了,得到的结果就是错误的。
- 在链表的 index(0-based)位置添加元素 e
- 通过索引来操作链表,在链表中不是一个常用的操作,
- 因为在选择使用链表的时候通常就选择不使用索引了,
- 但是这个需求在面试等一些考题中出现的概率很大,
- 所以他的主要作用更多的是一个练习。
学习方式
- 如果刚接触链表,对链表不熟悉,
- 然后很多这种操作在脑子里不能非常快的反应出来,
- 不清楚他的意义是什么,那你可以使用纸笔来稍微画一下,
- 每一步程序逻辑的执行意味着当前这个链表变成了什么样子,
- 这个过程能够帮助你更加深入的理解程序,
- 包括在调试的时候来看你的程序到底为什么出了错误时,
- 非常非常有帮助的,不要犯懒,为了更加深入的理解你的程序,
- 不能只盯着你的代码去想,一定要写写画画,
- 必要的时候甚至根据你的程序进行具体的调试,
- 这些都是非常重要非常有帮助的。
代码示例 (class: MyLinkedList)
-
MyLinkedList
class MyLinkedListNode { constructor(element = null, next = null) { this.element = element; this.next = next; } // toString 2018-10-20-jwl toString() { return this.element.toString(); } } class MyLinkedList { constructor() { this.head = null; this.size = 0; } // 获取链表中实际的节点个数 getSise() { return this.size; } // 判断链表是否为空 isEmpty() { return this.size === 0; } // 在链表头添加节点 addFirst(element) { let node = new MyLinkedListNode(element, null); node.next = this.head; this.head = node; this.size++; } // 在链表指定索引处插入节点 insert(index, element) { if (index < 0 || index > this.size) { throw new Error('add error. index < 0 or index > size'); } if (index === 0) { this.addFirst(element); } else { // 第一个prev就是head let prev = this.head; // 变量i(索引)之所以要从 1 开始,因为索引为0的那个节点就是head,循环就不需要从0开始了, // 小于index是因为要找到指定索引位置的前一个节点 // 循环是因为 要继续找到指定索引处的节点的前一个节点 for (var i = 1; i < index; i++) { // 不停的切换引用,直到找到对应索引处节点的下一个节点 prev = prev.next; } let node = new MyLinkedListNode(element, null); node.next = prev.next; prev.next = node; this.size++; } } // 扩展:在链表最后一个节点的位置添加节点 addLast(element) { this.insert(this.size, element); } }
给链表设立虚拟头节点
- 在链表中进行指定索引处插入元素时
- 对链表头插入元素与对链表其它位置插入元素的逻辑有区别,
- 所以就导致每次操作都需要对索引进行判断,
- 如果你是在索引 0 的位置插入元素,那么就没有 prev(前一个元素),
- 自然就不可以使用
node.next = prev.next
和prev.next = node
了, - 那时候你可以直接使用
node.next = head
和head = node
, - 不过已经有了向链表头添加元素的方法了,
- 所以向头部插入元素时根本就不需要这么做,
- 这时候可以通过给链表设立虚拟头节点来解决这个问题。
- 为什么对链表头插入元素那么特殊?
- 因为插入元素时,必需要找到该索引位置的节点之前的一个节点(prev),
- 而链表头(head)之前并没有任何节点,所以逻辑上就会特殊一些。
- 不过在链表的具体实现中有一个非常常用的技巧,
- 可以把链表头的这种特殊的操作与其它的操作一起统一起来,
- 其实这个方法的想法很简单,既然它没有链表头之前的节点,
- 那就自己造一个链表头之前的节点,
- 这个链表头之前的节点不会用来存储任何元素,存储的数据为空,
- 这个空节点就称之为整个链表头的 head,也可以叫它 dummyHead,
- 因为它就是一个假的 head,它也是为链表设立的虚拟头节点,
- 这样一来 链表的第一个元素就是 dummyHead 的 next 所对应的那个节点,
- 因为 dummyHead 这个位置的元素是根本不存在的,
- 对用户来讲也是根本没有意义的,
- 这只是为了编写逻辑方便而出现的一个虚拟的头节点,
- 所以一个这样的内部机制对用户来说也是不可见的,
- 用户不知道链表中有没有虚拟的头节点,
- 这和自定义的循环队列有点像,自定义循环队列中有一个不可用的空间,
- 有意识地去浪费一个空间,为了编写逻辑更加的方便,
- 从而也让性能在整体上得到了提升。
- 有了 dummyHead 之后就不需要处理头节点这个特殊的操作
- 因为当你在头部插入元素时,可以这样
node.next = dummyHead.next
、dummyHead.next = node
,- 这样你就解决了每次插入时都要进行一次逻辑判断了,
- 这样一来就说明了链表中所有的节点都有前一个节点了,
- 在初始的时候 dummyHead 指向的是索引为 0 的元素前一个位置的节点。
- 链表操作的实际原理
- 在没有使用虚拟头节点之前,一直都是在链表头 head 这个地方不停的添加节点,
- 然后将 head 这个变量不停的指向新添加的节点
node.next = head.next;head = node;
。 - 在使用了虚拟头节点之后,
- 一直是在链表虚拟头 dummyHead 这个地方后面一个位置不停的插入新节点,
- dummyHead 从未变动过,永远在链表的第一个位置,
node.next = dummyHead.next; dummyHead.next = node;
,- 但是
dummyHead.next
才是链表中第一个实际记录的节点, - 用户会不知道虚拟节点的存在,因为 dummyHead 并不算在链表的实际节点中,
- 也就是 size 中不会维护 dummyHead,dummyHead 的存在是为了维护一致的插入操作。
代码示例 (class: MyLinkedList)
-
MyLinkedList
class MyLinkedListNode { constructor(element = null, next = null) { this.element = element; this.next = next; } // toString 2018-10-20-jwl toString() { return this.element.toString(); } } class MyLinkedList { constructor() { this.dummyHead = new MyLinkedListNode(null, null); this.size = 0; } // 获取链表中实际的节点个数 getSise() { return this.size; } // 判断链表是否为空 isEmpty() { return this.size === 0; } // 在链表头添加节点 addFirst(element) { // let node = new MyLinkedListNode(element, null); // node.next = this.head; // this.head = node; // this.size ++; // 改用虚拟头节点 insert(0, element); } // 在链表指定索引处插入节点 insert(index, element) { if (index < 0 || index > this.size) { throw new Error('add error. index < 0 or index > size'); } // 第一个prev就是dummyHead let prev = this.dummyHead; // 之前变量i(索引)之所以要从 1 开始,因为索引为0的那个节点就是head,循环就不需要从0开始了, // 现在索引之所以要从 0 开始, 因为初始化时 多增加了一个虚拟的头节点 // (因为这个索引为0的节点并不是dummyHead,dummyHead这个节点并不记录为链表中的实际节点), // 小于index是因为要找到指定索引位置的前一个节点 // 循环是因为 要继续找到指定索引处的节点的前一个节点 for (var i = 0; i < index; i++) { // 不停的切换引用,直到找到对应索引处节点的下一个节点 prev = prev.next; } let node = new MyLinkedListNode(element, null); node.next = prev.next; prev.next = node; this.size++; } // 扩展:在链表最后一个节点的位置添加节点 addLast(element) { this.insert(this.size, element); } }
在链表中进行遍历、查询、修改操作
- 如果要找指定索引元素的前一个节点
- 那么就要从
dummyHead
开始遍历, - 如果要找指定索引元素的那个节点,
- 那么就要从
dummyHead.next
开始遍历。
- 那么就要从
代码示例(class: MyLinkedList, class: Main)
-
MyLinkedList
class MyLinkedListNode { constructor(element = null, next = null) { this.element = element; this.next = next; } // toString 2018-10-20-jwl toString() { return this.element.toString(); } } class MyLinkedList { constructor() { this.dummyHead = new MyLinkedListNode(null, null); this.size = 0; } // 获取链表中实际的节点个数 getSize() { return this.size; } // 判断链表是否为空 isEmpty() { return this.size === 0; } // 在链表头添加节点 addFirst(element) { // let node = new MyLinkedListNode(element, null); // node.next = this.head; // this.head = node; // this.size ++; // 改用虚拟头节点 this.insert(0, element); } // 在链表指定索引处插入节点 insert(index, element) { if (index < 0 || index > this.size) { throw new Error('add error. index < 0 or index > size'); } // 第一个prev就是dummyHead let prev = this.dummyHead; // 之前变量i(索引)之所以要从 1 开始,因为索引为0的那个节点就是head,循环就不需要从0开始了, // 现在索引之所以要从 0 开始, 因为初始化时 多增加了一个虚拟的头节点 // (因为这个索引为0的节点并不是dummyHead,dummyHead这个节点并不记录为链表中的实际节点), // 小于index是因为要找到指定索引位置的前一个节点 // 循环是因为 要继续找到指定索引处的节点的前一个节点 for (var i = 0; i < index; i++) { // 不停的切换引用,直到找到对应索引处节点的下一个节点 prev = prev.next; } let node = new MyLinkedListNode(element, null); node.next = prev.next; prev.next = node; this.size++; } // 扩展:在链表最后一个节点的位置添加节点 addLast(element) { this.insert(this.size, element); } // 获取指定索引位置的元素 get(index) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 如果你要找指定索引节点的前一个节点 就使用dummyHead // 如果你要找到指定索引节点 就使用dummyHead.next // 因为duumyHead并不是第一个节点,因为它是一个虚拟节点, // dummyHead.next才是真正被记录的第一个节点。 let node = this.dummyHead.next; for (var i = 0; i < index; i++) { node = node.next; } return node.element; } // 获取头节点的元素 getFirst() { return this.get(0); } // 获取尾节点的元素 getLast() { return this.get(this.size - 1); } // 设置指定索引位置的元素值 set(index, element) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 从第一个真正被记录的节点开始,从0开始 let node = this.dummyHead.next; // 索引为 0 时,实际上切换到的节点 它的索引为 1 // i < index ,当索引为 index-1 时, 实际上切换到的节点 它的索引为index for (let i = 0; i < index; i++) { // 每一次切换 都只是改变引用 // 不的在链表中找下一个节点 node = node.next; } node.element = element; } // 所有节点中是否有包含该元素 contains(element) { let node = this.dummyHead; while (node.next !== null) { if (node.next.element === element) return true; // 不停的向下切换 node = node.next; } return false; } // 输出链表中的信息 // @Override toString 2018-10-21-jwl toString() { let arrInfo = `LinkedList: size = ${this.size},\n`; arrInfo += `data = front [`; let node = this.dummyHead.next; while (node.next !== null) { arrInfo += `${node.element}->`; node = node.next; } arrInfo += 'NULL] tail'; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
Main
class Main { constructor () { /this.alterLine("MyLinkedList Area"); let mylinkedList = new MyLinkedList(); for (let i = 1; i <= 5 ; i++) { mylinkedList.addFirst(i); console.log(mylinkedList.toString()); } mylinkedList.insert(2, 88888); console.log(mylinkedList.toString()); } // 将内容显示在页面上 show (content) { document.body.innerHTML += `${content}<br /><br />`; } // 展示分割线 alterLine (title) { let line = `--------------------${title}----------------------` console.log(line); document.body.innerHTML += `${line}<br /><br />`; } }
在链表中进行删除操作
- 链表元素的删除
- 假设要删除索引为 2 位置的元素
- 就是要索引为 2 位置的元素的前一个元素,
- 还要索引为 2 位置的元素的后一个元素,
- 让前一个元素的 next 等于后一个元素,
- 也就是前一个元素的 next 等于索引为 2 的元素的 next。
- 也就是让 prev 指向待删除的那个节点的前一个节点,
- prev 这个节点的 next 就是要删除的那个节点 delNode,
- 然后让
prev.next = delNode.next
, - 这样就让待删除的那个节点的前一个节点的 next,
- 也就是直接指向了待删除的那个节点的后一个节点了,
- 然后让
delNode.next = null
就完成了删除, - 千万不要这样
delNode = delNode.next
, - 这个并不是删除,而是将待删除节点的引用指向了下一个节点,
- 通过设置为 null 才是真正的与当前链表脱离关系。
代码示例(class: MyLinkedList, class: Main)
-
MyLinkedList
class MyLinkedListNode { constructor(element = null, next = null) { this.element = element; this.next = next; } // toString 2018-10-20-jwl toString() { return this.element.toString(); } } class MyLinkedList { constructor() { this.dummyHead = new MyLinkedListNode(null, null); this.size = 0; } // 获取链表中实际的节点个数 getSize() { return this.size; } // 判断链表是否为空 isEmpty() { return this.size === 0; } // 在链表头添加节点 addFirst(element) { // let node = new MyLinkedListNode(element, null); // node.next = this.head; // this.head = node; // this.size ++; // 改用虚拟头节点 this.insert(0, element); } // 在链表指定索引处插入节点 insert(index, element) { if (index < 0 || index > this.size) { throw new Error('add error. index < 0 or index > size'); } // 第一个prev就是dummyHead let prev = this.dummyHead; // 之前变量i(索引)之所以要从 1 开始,因为索引为0的那个节点就是head,循环就不需要从0开始了, // 现在索引之所以要从 0 开始, 因为初始化时 多增加了一个虚拟的头节点 // (因为这个索引为0的节点并不是dummyHead,dummyHead这个节点并不记录为链表中的实际节点), // 小于index是因为要找到指定索引位置的前一个节点 // 循环是因为 要继续找到指定索引处的节点的前一个节点 for (var i = 0; i < index; i++) { // 不停的切换引用,直到找到对应索引处节点的下一个节点 prev = prev.next; } let node = new MyLinkedListNode(element, null); node.next = prev.next; prev.next = node; this.size++; } // 扩展:在链表最后一个节点的位置添加节点 addLast(element) { this.insert(this.size, element); } // 获取指定索引位置的元素 get(index) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 如果你要找指定索引节点的前一个节点 就使用dummyHead // 如果你要找到指定索引节点 就使用dummyHead.next // 因为duumyHead并不是第一个节点,因为它是一个虚拟节点, // dummyHead.next才是真正被记录的第一个节点。 let node = this.dummyHead.next; for (var i = 0; i < index; i++) { node = node.next; } return node.element; } // 获取头节点的元素 getFirst() { return this.get(0); } // 获取尾节点的元素 getLast() { return this.get(this.size - 1); } // 设置指定索引位置的元素值 set(index, element) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 从第一个真正被记录的节点开始,从0开始 let node = this.dummyHead.next; // 索引为 0 时,实际上切换到的节点 它的索引为 1 // i < index ,当索引为 index-1 时, 实际上切换到的节点 它的索引为index for (let i = 0; i < index; i++) { // 每一次切换 都只是改变引用 // 不的在链表中找下一个节点 node = node.next; } node.element = element; } // 所有节点中是否有包含该元素 contains(element) { let node = this.dummyHead; while (node.next !== null) { if (node.next.element === element) return true; // 不停的向下切换 node = node.next; } return false; } // 删除指定索引位置的节点 remove(index) { // 验证索引的合法性 if (index < 0 || index >= this.size) { throw new Error('remove error. index < 0 or index > this.size'); } let node = this.dummyHead; for (let i = 0; i < index; i++) { node = node.next; } // 待删除的节点 let delNode = node.next; // 给待删除那个节点的前一个的节点的next引用替换为 // 但删除的这个节点的next node.next = delNode.next; // 或者这样也行 // node.next = node.next.next; // 临时存储待删除的那个节点里的元素 let element = delNode.element; // 清空 待删除的节点 delNode = null; this.size--; return element; } // 扩展:移除链表头的元素 removeFirst() { return this.remove(0); } // 扩展:移除链表尾部的元素 removeLast() { return this.remove(this.size - 1); } // 输出链表中的信息 // @Override toString 2018-10-21-jwl toString() { let arrInfo = `LinkedList: size = ${this.size},\n`; arrInfo += `data = front [`; let node = this.dummyHead.next; while (node.next !== null) { arrInfo += `${node.element}->`; node = node.next; } arrInfo += 'NULL] tail'; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
Main
class Main { constructor() { this.alterLine('MyLinkedList Area'); let mylinkedList = new MyLinkedList(); for (let i = 1; i <= 5; i++) { mylinkedList.addFirst(i); console.log(mylinkedList.toString()); } mylinkedList.insert(2, 88888); console.log(mylinkedList.toString()); mylinkedList.remove(2); console.log(mylinkedList.toString()); mylinkedList.removeFirst(); console.log(mylinkedList.toString()); mylinkedList.removeLast(); console.log(mylinkedList.toString()); } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}<br /><br />`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}<br /><br />`; } }
链表的时间复杂度分析
- 增:
O(n)
:在只对链表头进行操作时为O(1)
- 删:
O(n)
:在只对链表头进行操作时为O(1)
- 改:
O(n)
- 查:
O(n)
:只查链表头的元素时为O(1)
- 链表增删改查的时间复杂度
- 整体上要比数组增删改查的时间复杂度要差,
- 因为数组有一个优势,
- 你有索引的话你就可以快速访问,
- 而链表没有这样的优势
- 但是链表的优势是,
- 如果你只对链表头进行增删的操作,
- 那么它的时间复杂度是 O(1)级别的,
- 而且它整体是动态的,所以不会大量的浪费内存空间。 6.链表适合做的事情
- 不去修改、也不去查任意的元素,
- 就算查,也只能查链表头的元素,
- 查的时候,只有那样才是 O(1)级别的时间复杂度,
- 并且增加删除的时候只对链表头进行操作,
- 只有在这种时候才会和数组整体的时间复杂度是一样的,
- 不过链表整体是动态的,不会去大量的浪费内存空间,
- 所以它具有一定的优势。
- 链表还有诸多的改进的方式
- 所以应用链表在一些情况下仍然是有它的优势的,
- 最最重要的是 链表本身是一种最最基础的动态数据结构,
- 对这种动态数据结构要深刻的理解和掌握,
- 对于学习更重要的动态数据结构是有巨大的帮助,
- 比如说二叉树、平衡二叉树、AVL、红黑树等等。
### 添加操作 O(n)
addLast(e)
:O(n)
- 会从头遍历到尾,
- 找到最后一个节点之后才能添加元素
addFirst(e)
:O(1)
- 直接从头部添加元素
insert(index, e)
:O(n/2) = O(n)
- 会去遍历链表中每一个节点,
- 检索到合适的位置才会添加这个元素。
删除操作 O(n)
removeLast()
:O(n)
- 会去遍历链表中每一个节点,
- 找到最后一个节点后才会删除
removeFirst()
:O(1)
- 直接从头部删除这个节点
remove(index)
:O(n/2) = O(n)
- 会去遍历链表中每一个节点,
- 检索到合适的位置才会移除这个元素
修改操作 O(n)
set(index, e)
:O(n)
- 会去遍历链表中每一个节点,
- 找到了合适位置的节点后,
- 才会修改元素
查找操作 O(n)
get(index)
:O(n)
- 会去遍历链表中每一个节点,
- 找到了合适位置的节点后,
- 返回这个元素。
contains(e)
:O(n)
- 会去遍历链表中每一个节点,
- 返回 是否有相同元素的 bool 值。
find(e)
:O(n)
- 这个方法对链表来说是没有用的,
- 就算你拿到了那个索引你也不能快速访问。
使用链表来实现栈
- 对链表进行添加操作时
- 时间复杂度为
O(n)
, - 但是在只对链表头进行操作时为
O(1)
- 时间复杂度为
- 对链表进行删除操作时
- 时间复杂度为
O(n)
, - 但是在只对链表头进行操作时为
O(1)
- 时间复杂度为
- 对链表进行查询操作时
- 时间复杂度为
O(n)
, - 但是在只查链表头的元素时为
O(1)
- 时间复杂度为
- 这些特性很符合栈的需求
- 栈是后进先出的,并且栈只查栈顶的元素,
- 所以可以使用链表来实现栈这样的数据结构。
链表实现的栈
MyLinkedListStack
的接口。void push(E e)
:添加一个元素E pop()
:移除一个元素E peek()
:查看栈顶的元素int getSize()
:获取栈中实际的元素个数boolean isEmpty()
:判断栈是否为空
代码示例
-
(class: MyLinkedList,class: MyLinkedListStack, class: Main)
-
MyLinkedList
class MyLinkedListNode { constructor(element = null, next = null) { this.element = element; this.next = next; } // toString 2018-10-20-jwl toString() { return this.element.toString(); } } class MyLinkedList { constructor() { this.dummyHead = new MyLinkedListNode(null, null); this.size = 0; } // 获取链表中实际的节点个数 getSize() { return this.size; } // 判断链表是否为空 isEmpty() { return this.size === 0; } // 在链表头添加节点 addFirst(element) { // let node = new MyLinkedListNode(element, null); // node.next = this.head; // this.head = node; // this.size ++; // 改用虚拟头节点 this.insert(0, element); } // 在链表指定索引处插入节点 insert(index, element) { if (index < 0 || index > this.size) { throw new Error('add error. index < 0 or index > size'); } // 第一个prev就是dummyHead let prev = this.dummyHead; // 之前变量i(索引)之所以要从 1 开始,因为索引为0的那个节点就是head,循环就不需要从0开始了, // 现在索引之所以要从 0 开始, 因为初始化时 多增加了一个虚拟的头节点 // (因为这个索引为0的节点并不是dummyHead,dummyHead这个节点并不记录为链表中的实际节点), // 小于index是因为要找到指定索引位置的前一个节点 // 循环是因为 要继续找到指定索引处的节点的前一个节点 for (var i = 0; i < index; i++) { // 不停的切换引用,直到找到对应索引处节点的下一个节点 prev = prev.next; } let node = new MyLinkedListNode(element, null); node.next = prev.next; prev.next = node; this.size++; } // 扩展:在链表最后一个节点的位置添加节点 addLast(element) { this.insert(this.size, element); } // 获取指定索引位置的元素 get(index) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 如果你要找指定索引节点的前一个节点 就使用dummyHead // 如果你要找到指定索引节点 就使用dummyHead.next // 因为duumyHead并不是第一个节点,因为它是一个虚拟节点, // dummyHead.next才是真正被记录的第一个节点。 let node = this.dummyHead.next; for (var i = 0; i < index; i++) { node = node.next; } return node.element; } // 获取头节点的元素 getFirst() { return this.get(0); } // 获取尾节点的元素 getLast() { return this.get(this.size - 1); } // 设置指定索引位置的元素值 set(index, element) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 从第一个真正被记录的节点开始,从0开始 let node = this.dummyHead.next; // 索引为 0 时,实际上切换到的节点 它的索引为 1 // i < index ,当索引为 index-1 时, 实际上切换到的节点 它的索引为index for (let i = 0; i < index; i++) { // 每一次切换 都只是改变引用 // 不的在链表中找下一个节点 node = node.next; } node.element = element; } // 所有节点中是否有包含该元素 contains(element) { let node = this.dummyHead; while (node.next !== null) { if (node.next.element === element) return true; // 不停的向下切换 node = node.next; } return false; } // 删除指定索引位置的节点 remove(index) { // 验证索引的合法性 if (index < 0 || index >= this.size) { throw new Error('remove error. index < 0 or index > this.size'); } let node = this.dummyHead; for (let i = 0; i < index; i++) { node = node.next; } // 待删除的节点 let delNode = node.next; // 给待删除那个节点的前一个的节点的next引用替换为 // 但删除的这个节点的next node.next = delNode.next; // 或者这样也行 // node.next = node.next.next; // 临时存储待删除的那个节点里的元素 let element = delNode.element; // 清空 待删除的节点 delNode = null; this.size--; return element; } // 扩展:移除链表头的元素 removeFirst() { return this.remove(0); } // 扩展:移除链表尾部的元素 removeLast() { return this.remove(this.size - 1); } // 输出链表中的信息 // @Override toString 2018-10-21-jwl toString() { let arrInfo = `LinkedList: size = ${this.size},\n`; arrInfo += `data = front [`; let node = this.dummyHead.next; while (node.next !== null) { arrInfo += `${node.element}->`; node = node.next; } arrInfo += 'NULL] tail'; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
MyLinkedListStack
class MyLinkedListStack { constructor() { this.myLinkedList = new MyLinkedList(); } // 入栈 push(element) { this.myLinkedList.addFirst(element); } // 出栈 pop() { return this.myLinkedList.removeFirst(); } // 查看栈顶元素 peek() { return this.myLinkedList.getFirst(); } // 查看栈中实际元素的个数 getSize() { return this.myLinkedList.getSize(); } // 判断栈是否为空 isEmpty() { return this.myLinkedList.isEmpty(); } // 输出栈中信息 // @Override toString 2018-10-21-jwl toString() { let arrInfo = `LinkedListStack: size = ${this.getSize()},\n`; arrInfo += `data = stack top [`; let node = this.myLinkedList.dummyHead.next; for (var i = 1; i < this.getSize(); i++) { arrInfo += `${node.element},`; node = node.next; } if (!this.isEmpty()) { arrInfo += `${node.element}`; } arrInfo += ']'; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
Main
class Main { constructor() { this.alterLine('MyLinkedListStack Area'); let myLinkedListStack = new MyLinkedListStack(); for (let i = 1; i <= 5; i++) { myLinkedListStack.push(i); console.log(myLinkedListStack.toString()); } console.log(myLinkedListStack.peek()); this.show(myLinkedListStack.peek()); for (let i = 0; i < 5; i++) { console.log(myLinkedListStack.toString()); myLinkedListStack.pop(); } } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}<br /><br />`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}<br /><br />`; } } window.onload = function() { // 执行主函数 new Main(); };
自定义数组栈对比自定义链表栈
- 自定义数组栈与自定义链表栈的性能相差很少
- 但是随着操作的次数增长,数组栈会慢慢强过链表栈,
- 自定义链表栈中有太多的 new 操作,
- new 操作在有一些系统上比较耗费性能的,
- 因为它在不停的在内存中寻找可以开辟空间的地方来进行开辟空间,
- 自定义数组栈中有比较多的扩容操作,
- 所以这个比较是相对比较复杂的,
- 和你的语法、操作系统、编译器、解释器都有关系,
- 不过他们的时间复杂度都是
O(1)
级别的, - 所以他们之间的性能差异无非就 1-2 倍这样,
- 在最极端的情况下 3-5 倍就已经很难了,
- 不会有几百倍的巨大的差异,因为毕竟他们的时间复杂度一样。
代码示例
-
(class: MyLinkedList, class: MyLinkedListStack, class: MyArray, class: MyStack, class: Main)
-
MyLinkedList
class MyLinkedListNode { constructor(element = null, next = null) { this.element = element; this.next = next; } // toString 2018-10-20-jwl toString() { return this.element.toString(); } } class MyLinkedList { constructor() { this.dummyHead = new MyLinkedListNode(null, null); this.size = 0; } // 获取链表中实际的节点个数 getSize() { return this.size; } // 判断链表是否为空 isEmpty() { return this.size === 0; } // 在链表头添加节点 addFirst(element) { // let node = new MyLinkedListNode(element, null); // node.next = this.head; // this.head = node; // this.size ++; // 改用虚拟头节点 this.insert(0, element); } // 在链表指定索引处插入节点 insert(index, element) { if (index < 0 || index > this.size) { throw new Error('add error. index < 0 or index > size'); } // 第一个prev就是dummyHead let prev = this.dummyHead; // 之前变量i(索引)之所以要从 1 开始,因为索引为0的那个节点就是head,循环就不需要从0开始了, // 现在索引之所以要从 0 开始, 因为初始化时 多增加了一个虚拟的头节点 // (因为这个索引为0的节点并不是dummyHead,dummyHead这个节点并不记录为链表中的实际节点), // 小于index是因为要找到指定索引位置的前一个节点 // 循环是因为 要继续找到指定索引处的节点的前一个节点 for (var i = 0; i < index; i++) { // 不停的切换引用,直到找到对应索引处节点的下一个节点 prev = prev.next; } let node = new MyLinkedListNode(element, null); node.next = prev.next; prev.next = node; this.size++; } // 扩展:在链表最后一个节点的位置添加节点 addLast(element) { this.insert(this.size, element); } // 获取指定索引位置的元素 get(index) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 如果你要找指定索引节点的前一个节点 就使用dummyHead // 如果你要找到指定索引节点 就使用dummyHead.next // 因为duumyHead并不是第一个节点,因为它是一个虚拟节点, // dummyHead.next才是真正被记录的第一个节点。 let node = this.dummyHead.next; for (var i = 0; i < index; i++) { node = node.next; } return node.element; } // 获取头节点的元素 getFirst() { return this.get(0); } // 获取尾节点的元素 getLast() { return this.get(this.size - 1); } // 设置指定索引位置的元素值 set(index, element) { // 判断索引合法性 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size'); } // 从第一个真正被记录的节点开始,从0开始 let node = this.dummyHead.next; // 索引为 0 时,实际上切换到的节点 它的索引为 1 // i < index ,当索引为 index-1 时, 实际上切换到的节点 它的索引为index for (let i = 0; i < index; i++) { // 每一次切换 都只是改变引用 // 不的在链表中找下一个节点 node = node.next; } node.element = element; } // 所有节点中是否有包含该元素 contains(element) { let node = this.dummyHead; while (node.next !== null) { if (node.next.element === element) return true; // 不停的向下切换 node = node.next; } return false; } // 删除指定索引位置的节点 remove(index) { // 验证索引的合法性 if (index < 0 || index >= this.size) { throw new Error('remove error. index < 0 or index > this.size'); } let node = this.dummyHead; for (let i = 0; i < index; i++) { node = node.next; } // 待删除的节点 let delNode = node.next; // 给待删除那个节点的前一个的节点的next引用替换为 // 但删除的这个节点的next node.next = delNode.next; // 或者这样也行 // node.next = node.next.next; // 临时存储待删除的那个节点里的元素 let element = delNode.element; // 清空 待删除的节点 delNode = null; this.size--; return element; } // 扩展:移除链表头的元素 removeFirst() { return this.remove(0); } // 扩展:移除链表尾部的元素 removeLast() { return this.remove(this.size - 1); } // 输出链表中的信息 // @Override toString 2018-10-21-jwl toString() { let arrInfo = `LinkedList: size = ${this.size},\n`; arrInfo += `data = front [`; let node = this.dummyHead.next; while (node.next !== null) { arrInfo += `${node.element}->`; node = node.next; } arrInfo += 'NULL] tail'; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
MyLinkedListStack
class MyLinkedListStack { constructor() { this.myLinkedList = new MyLinkedList(); } // 入栈 push(element) { this.myLinkedList.addFirst(element); } // 出栈 pop() { return this.myLinkedList.removeFirst(); } // 查看栈顶元素 peek() { return this.myLinkedList.getFirst(); } // 查看栈中实际元素的个数 getSize() { return this.myLinkedList.getSize(); } // 判断栈是否为空 isEmpty() { return this.myLinkedList.isEmpty(); } // 输出栈中信息 // @Override toString 2018-10-21-jwl toString() { let arrInfo = `LinkedListStack: size = ${this.getSize()},\n`; arrInfo += `data = stack top [`; let node = this.myLinkedList.dummyHead.next; for (var i = 1; i < this.getSize(); i++) { arrInfo += `${node.element},`; node = node.next; } if (!this.isEmpty()) { arrInfo += `${node.element}`; } arrInfo += ']'; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
MyArray
class MyArray { // 构造函数,传入数组的容量capacity构造Array 默认数组的容量capacity=10 constructor(capacity = 10) { this.data = new Array(capacity); this.size = 0; } // 获取数组中的元素实际个数 getSize() { return this.size; } // 获取数组的容量 getCapacity() { return this.data.length; } // 判断数组是否为空 isEmpty() { return this.size === 0; } // 给数组扩容 resize(capacity) { let newArray = new Array(capacity); for (var i = 0; i < this.size; i++) { newArray[i] = this.data[i]; } // let index = this.size - 1; // while (index > -1) { // newArray[index] = this.data[index]; // index --; // } this.data = newArray; } // 在指定索引处插入元素 insert(index, element) { // 先判断数组是否已满 if (this.size == this.getCapacity()) { // throw new Error("add error. Array is full."); this.resize(this.size * 2); } // 然后判断索引是否符合要求 if (index < 0 || index > this.size) { throw new Error( 'insert error. require index < 0 or index > size.' ); } // 最后 将指定索引处腾出来 // 从指定索引处开始,所有数组元素全部往后移动一位 // 从后往前移动 for (let i = this.size - 1; i >= index; i--) { this.data[i + 1] = this.data[i]; } // 在指定索引处插入元素 this.data[index] = element; // 维护一下size this.size++; } // 扩展 在数组最前面插入一个元素 unshift(element) { this.insert(0, element); } // 扩展 在数组最后面插入一个元素 push(element) { this.insert(this.size, element); } // 其实在数组中添加元素 就相当于在数组最后面插入一个元素 add(element) { if (this.size == this.getCapacity()) { // throw new Error("add error. Array is full."); this.resize(this.size * 2); } // size其实指向的是 当前数组最后一个元素的 后一个位置的索引。 this.data[this.size] = element; // 维护size this.size++; } // get get(index) { // 不能访问没有存放元素的位置 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size.'); } return this.data[index]; } // 扩展: 获取数组中第一个元素 getFirst() { return this.get(0); } // 扩展: 获取数组中最后一个元素 getLast() { return this.get(this.size - 1); } // set set(index, newElement) { // 不能修改没有存放元素的位置 if (index < 0 || index >= this.size) { throw new Error('set error. index < 0 or index >= size.'); } this.data[index] = newElement; } // contain contain(element) { for (var i = 0; i < this.size; i++) { if (this.data[i] === element) { return true; } } return false; } // find find(element) { for (var i = 0; i < this.size; i++) { if (this.data[i] === element) { return i; } } return -1; } // findAll findAll(element) { // 创建一个自定义数组来存取这些 元素的索引 let myarray = new MyArray(this.size); for (var i = 0; i < this.size; i++) { if (this.data[i] === element) { myarray.push(i); } } // 返回这个自定义数组 return myarray; } // 删除指定索引处的元素 remove(index) { // 索引合法性验证 if (index < 0 || index >= this.size) { throw new Error('remove error. index < 0 or index >= size.'); } // 暂存即将要被删除的元素 let element = this.data[index]; // 后面的元素覆盖前面的元素 for (let i = index; i < this.size - 1; i++) { this.data[i] = this.data[i + 1]; } this.size--; this.data[this.size] = null; // 如果size 为容量的四分之一时 就可以缩容了 // 防止复杂度震荡 if (Math.floor(this.getCapacity() / 4) === this.size) { // 缩容一半 this.resize(Math.floor(this.getCapacity() / 2)); } return element; } // 扩展:删除数组中第一个元素 shift() { return this.remove(0); } // 扩展: 删除数组中最后一个元素 pop() { return this.remove(this.size - 1); } // 扩展: 根据元素来进行删除 removeElement(element) { let index = this.find(element); if (index !== -1) { this.remove(index); } } // 扩展: 根据元素来删除所有元素 removeAllElement(element) { let index = this.find(element); while (index != -1) { this.remove(index); index = this.find(element); } // let indexArray = this.findAll(element); // let cur, index = 0; // for (var i = 0; i < indexArray.getSize(); i++) { // // 每删除一个元素 原数组中就少一个元素, // // 索引数组中的索引值是按照大小顺序排列的, // // 所以 这个cur记录的是 原数组元素索引的偏移量 // // 只有这样才能够正确的删除元素。 // index = indexArray.get(i) - cur++; // this.remove(index); // } } // @Override toString 2018-10-17-jwl toString() { let arrInfo = `Array: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`; arrInfo += `data = [`; for (var i = 0; i < this.size - 1; i++) { arrInfo += `${this.data[i]}, `; } if (!this.isEmpty()) { arrInfo += `${this.data[this.size - 1]}`; } arrInfo += `]`; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
MyStack
class MyStack { constructor(capacity = 10) { this.myArray = new MyArray(capacity); } // 入栈 push(element) { this.myArray.push(element); } // 出栈 pop() { return this.myArray.pop(); } // 查看栈顶的元素 peek() { return this.myArray.getLast(); } // 栈中实际元素的个数 getSize() { return this.myArray.getSize(); } // 栈是否为空 isEmpty() { return this.myArray.isEmpty(); } // 查看栈的容量 getCapacity() { return this.myArray.getCapacity(); } // @Override toString 2018-10-20-jwl toString() { let arrInfo = `Stack: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`; arrInfo += `data = [`; for (var i = 0; i < this.myArray.size - 1; i++) { arrInfo += `${this.myArray.data[i]}, `; } if (!this.isEmpty()) { arrInfo += `${this.myArray.data[this.myArray.size - 1]}`; } arrInfo += `] stack top is right!`; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
Main
class Main { constructor() { this.alterLine('Stacks Comparison Area'); let myStack = new MyStack(); let myLinkedListStack = new MyLinkedListStack(); let performanceTest = new PerformanceTest(); let myStackInfo = performanceTest.testStack(myStack, 100000); let myLinkedListStackInfo = performanceTest.testStack( myLinkedListStack, 100000 ); this.alterLine('MyStack Area'); console.log(myStackInfo); this.show(myStackInfo); this.alterLine('MyLinkedListStack Area'); console.log(myLinkedListStackInfo); this.show(myLinkedListStackInfo); } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}<br /><br />`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}<br /><br />`; } } class Student { constructor(studentName, studentScore) { this.name = studentName; this.score = studentScore; } toString() { let studentInfo = `Student(name: ${this.name}, score: ${this.score})`; return studentInfo; } } window.onload = function() { // 执行主函数 new Main(); };
使用链表来实现队列
- 对链表进行添加操作时
- 时间复杂度为
O(n)
, - 只对链表头进行操作时为
O(1)
, - 对链表尾部进行操作时为
O(n)
- 时间复杂度为
- 对链表进行删除操作时
- 时间复杂度为
O(n)
, - 只对链表头进行操作时为
O(1)
, - 对链表尾部进行操作时为
O(n)
- 时间复杂度为
- 对链表进行查询操作时
- 时间复杂度为
O(n)
, - 只查链表头的元素时为
O(1)
, - 查链表尾部的元素时为
O(n)
- 时间复杂度为
- 队列中的操作
- 在线性结构的一端插入元素,
- 在另外一端删除元素,
- 所以必然会在线性结构的两端同时操作,
- 此时就会有一端的操作的复杂度是
O(n)
级别, - 这个问题在用自定义数组实现时也遇到了,
- 也正因为如此产生了循环队列,
- 通过改进使用数组来实现队列的方式,
- 所以链表也可以进行改进。
- 改进链表
- 不能使用之前的链表来进行队列的实现,
- 设置一个 head 变量指向链表的头部第一个节点,
- 设置一个 tail 变量指向链表的尾部第一个节点,
- 有了 tail 这个变量,那么在链表的尾部添加一个元素非常容易,
- 有了 head 和 tail 之后在两端添加节点是非常容易的,
- 但是无法使用
O(1)
去删除尾部的节点, - 从 tail 这一端删除元素并不容易,
- 但是如果将 head 作为队首,将 tail 作为队尾,
- 队列操作是从队尾进队首出的,
- 只需要从队尾 tail 插入元素,从队首 head 删除元素,
- 这样一来就可以实现队列的功能。
- 链表中不再有插入的功能所以不需要 dummyHead
- 但是由于没有 dummyHead,所以需要注意链表为空的情况。
- 让自定义动态数组队列与自定义链表队列进行对比
- 自定义动态数组队列的性能最差
- 自定义动态数组循环队列与自定义链表队列的性能相近。
- 与链表相关的有一个非常重要的内容
- 就是递归,因为链表本身具有天然的递归性质,
- 同时它又是一种非常简单的数据结构,
- 所以链表是一种非常好的
- 研究学习递归的逻辑机制的的数据结构。
代码示例
-
( class: MyArray, class: MyQueue, class: MyLoopQueue, class: MyLinkedListQueue, class: Main)
-
MyArray
class MyArray { // 构造函数,传入数组的容量capacity构造Array 默认数组的容量capacity=10 constructor(capacity = 10) { this.data = new Array(capacity); this.size = 0; } // 获取数组中的元素实际个数 getSize() { return this.size; } // 获取数组的容量 getCapacity() { return this.data.length; } // 判断数组是否为空 isEmpty() { return this.size === 0; } // 给数组扩容 resize(capacity) { let newArray = new Array(capacity); for (var i = 0; i < this.size; i++) { newArray[i] = this.data[i]; } // let index = this.size - 1; // while (index > -1) { // newArray[index] = this.data[index]; // index --; // } this.data = newArray; } // 在指定索引处插入元素 insert(index, element) { // 先判断数组是否已满 if (this.size == this.getCapacity()) { // throw new Error("add error. Array is full."); this.resize(this.size * 2); } // 然后判断索引是否符合要求 if (index < 0 || index > this.size) { throw new Error( 'insert error. require index < 0 or index > size.' ); } // 最后 将指定索引处腾出来 // 从指定索引处开始,所有数组元素全部往后移动一位 // 从后往前移动 for (let i = this.size - 1; i >= index; i--) { this.data[i + 1] = this.data[i]; } // 在指定索引处插入元素 this.data[index] = element; // 维护一下size this.size++; } // 扩展 在数组最前面插入一个元素 unshift(element) { this.insert(0, element); } // 扩展 在数组最后面插入一个元素 push(element) { this.insert(this.size, element); } // 其实在数组中添加元素 就相当于在数组最后面插入一个元素 add(element) { if (this.size == this.getCapacity()) { // throw new Error("add error. Array is full."); this.resize(this.size * 2); } // size其实指向的是 当前数组最后一个元素的 后一个位置的索引。 this.data[this.size] = element; // 维护size this.size++; } // get get(index) { // 不能访问没有存放元素的位置 if (index < 0 || index >= this.size) { throw new Error('get error. index < 0 or index >= size.'); } return this.data[index]; } // 扩展: 获取数组中第一个元素 getFirst() { return this.get(0); } // 扩展: 获取数组中最后一个元素 getLast() { return this.get(this.size - 1); } // set set(index, newElement) { // 不能修改没有存放元素的位置 if (index < 0 || index >= this.size) { throw new Error('set error. index < 0 or index >= size.'); } this.data[index] = newElement; } // contain contain(element) { for (var i = 0; i < this.size; i++) { if (this.data[i] === element) { return true; } } return false; } // find find(element) { for (var i = 0; i < this.size; i++) { if (this.data[i] === element) { return i; } } return -1; } // findAll findAll(element) { // 创建一个自定义数组来存取这些 元素的索引 let myarray = new MyArray(this.size); for (var i = 0; i < this.size; i++) { if (this.data[i] === element) { myarray.push(i); } } // 返回这个自定义数组 return myarray; } // 删除指定索引处的元素 remove(index) { // 索引合法性验证 if (index < 0 || index >= this.size) { throw new Error('remove error. index < 0 or index >= size.'); } // 暂存即将要被删除的元素 let element = this.data[index]; // 后面的元素覆盖前面的元素 for (let i = index; i < this.size - 1; i++) { this.data[i] = this.data[i + 1]; } this.size--; this.data[this.size] = null; // 如果size 为容量的四分之一时 就可以缩容了 // 防止复杂度震荡 if (Math.floor(this.getCapacity() / 4) === this.size) { // 缩容一半 this.resize(Math.floor(this.getCapacity() / 2)); } return element; } // 扩展:删除数组中第一个元素 shift() { return this.remove(0); } // 扩展: 删除数组中最后一个元素 pop() { return this.remove(this.size - 1); } // 扩展: 根据元素来进行删除 removeElement(element) { let index = this.find(element); if (index !== -1) { this.remove(index); } } // 扩展: 根据元素来删除所有元素 removeAllElement(element) { let index = this.find(element); while (index != -1) { this.remove(index); index = this.find(element); } // let indexArray = this.findAll(element); // let cur, index = 0; // for (var i = 0; i < indexArray.getSize(); i++) { // // 每删除一个元素 原数组中就少一个元素, // // 索引数组中的索引值是按照大小顺序排列的, // // 所以 这个cur记录的是 原数组元素索引的偏移量 // // 只有这样才能够正确的删除元素。 // index = indexArray.get(i) - cur++; // this.remove(index); // } } // @Override toString 2018-10-17-jwl toString() { let arrInfo = `Array: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`; arrInfo += `data = [`; for (var i = 0; i < this.size - 1; i++) { arrInfo += `${this.data[i]}, `; } if (!this.isEmpty()) { arrInfo += `${this.data[this.size - 1]}`; } arrInfo += `]`; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
MyQueue
class MyQueue { constructor(capacity = 10) { this.myArray = new MyArray(capacity); } // 入队 enqueue(element) { this.myArray.push(element); } // 出队 dequeue() { return this.myArray.shift(); } // 查看队首的元素 getFront() { return this.myArray.getFirst(); } // 查看队列中实际元素的个数 getSize() { return this.myArray.getSize(); } // 查看 队列当前的容量 getCapacity() { return this.myArray.getCapacity(); } // 查看队列是否为空 isEmpty() { return this.myArray.isEmpty(); } // 输出队列中的信息 // @Override toString 2018-10-20-jwl toString() { let arrInfo = `Queue: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`; arrInfo += `data = front [`; for (var i = 0; i < this.myArray.size - 1; i++) { arrInfo += `${this.myArray.data[i]}, `; } if (!this.isEmpty()) { arrInfo += `${this.myArray.data[this.myArray.size - 1]}`; } arrInfo += `] tail`; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
MyLoopQueue
class MyLoopQueue { constructor(capacity = 10) { // 初始化新数组 this.data = new Array(capacity); // 初始化 队首、队尾的值 (索引) this.front = this.tail = 0; // 队列中实际元素个数 this.size = 0; } // 扩容 resize(capacity) { let newArray = new Array(capacity); let index = 0; for (let i = 0; i < this.size; i++) { // 索引可能会越界,于是就要取余一下, // 如果越界了,就从队首开始 index = (this.front + i) % this.getCapacity(); newArray[i] = this.data[index]; } this.data = newArray; this.front = 0; this.tail = this.size; } // 入队 enqueue(element) { // 判断队列中是否已满 if ((this.tail + 1) % this.getCapacity() === this.front) { this.resize(this.getCapacity() * 2); } this.data[this.tail] = element; this.tail = (this.tail + 1) % this.getCapacity(); this.size++; } // 出队 dequeue() { // 判断队列是否为空 if (this.isEmpty()) { throw new Error("can't dequeue from an empty queue."); } let element = this.data[this.front]; this.data[this.front] = null; this.front = (this.front + 1) % this.getCapacity(); this.size--; // 当size 为容量的四分之一时就缩容一倍 if (this.size === Math.floor(this.getCapacity() / 4)) { this.resize(Math.floor(this.getCapacity() * 2)); } return element; } // 查看队首的元素 getFront() { if (this.isEmpty()) { throw new Error('queue is empty.'); } return this.data[front]; } // 查看实际的元素个数 getSize() { return this.size; } // 查看容量 getCapacity() { return this.data.length; } // 队列是否为空 isEmpty() { // return this.size === 0; return this.front == this.tail; } // 输出循环队列中的信息 // @Override toString 2018-10-20-jwl toString() { let arrInfo = `LoopQueue: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`; arrInfo += `data = front [`; for (var i = 0; i < this.myArray.size - 1; i++) { arrInfo += `${this.myArray.data[i]}, `; } if (!this.isEmpty()) { arrInfo += `${this.myArray.data[this.myArray.size - 1]}`; } arrInfo += `] tail`; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
MyLinkedListQueue
class MyLinkedListQueue { constructor() { this.front = this.tail = null; this.size = 0; } // 入队 enqueue(element) { // 判断队尾是否为空 if (this.tail === null) { // 第一个节点 即是尾也是头 this.tail = new MyLinkedListNode(element, null); this.front = this.tail; } else { let node = new MyLinkedListNode(element, null); this.tail.next = node; this.tail = node; } this.size++; } // 出队 dequeue() { // 判断队首是否为空 if (this.front === null) { throw new Error('front is empty.'); } let delNode = this.front; let element = delNode.element; this.front = this.front.next; delNode = null; if (this.front === null) // 如果头为空了,那么尾部也为空 this.tail = null; this.size--; return element; } // 查看队首的元素 getFront() { // 判断队首是否为空 if (this.front === null) { throw new Error('front is empty.'); } return this.front.element; } // 查看队列中实际元素的个数 getSize() { return this.size; } // 判断队列是否为空 isEmpty() { return this.size === 0; } // 输出队列中的信息 // @Override toString 2018-10-21-jwl toString() { let arrInfo = `LinkedListQueue: size = ${this.getSize()},\n`; arrInfo += `data = front [`; let node = this.front; for (var i = 1; i < this.getSize(); i++) { arrInfo += `${node.element},`; node = node.next; } if (!this.isEmpty()) { arrInfo += `${node.element}`; } arrInfo += '] tail'; // 在页面上展示 document.body.innerHTML += `${arrInfo}<br /><br /> `; return arrInfo; } }
-
Main
class Main { constructor() { this.alterLine('MyLinkedListQueue Area'); let myLinkedListQueue = new MyLinkedListQueue(); for (let i = 1; i <= 5; i++) { myLinkedListQueue.enqueue(i); console.log(myLinkedListQueue.toString()); } console.log(myLinkedListQueue.getFront()); this.show(myLinkedListQueue.getFront()); for (let i = 0; i < 5; i++) { console.log(myLinkedListQueue.toString()); myLinkedListQueue.dequeue(); } } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}<br /><br />`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}<br /><br />`; } } class Student { constructor(studentName, studentScore) { this.name = studentName; this.score = studentScore; } toString() { let studentInfo = `Student(name: ${this.name}, score: ${this.score})`; return studentInfo; } } window.onload = function() { // 执行主函数 new Main(); };