前言
在之前的文章《如何实现一个队列》中，我们使用数组结构、栈结构实现了队列，现在我们要寻找一种更优雅的方案来实现队列。
链表是一种有序的，零散的数据存储结构，区分为单项链表和双向链表。
- 单项链表：链表节点会存储一个下一个节点对象的引用地址，如
next属性；
- 双向链表：链表节点会同时存储指向上一个节点对象的引用（
prev）和下一个节点对象的引用（next）。
我们先来回忆下队列的特点：有序，队列元素遵循先进先出，后进后出的原则。
队列实现 - 链表
首先声明一个链表类，具备以下方法和属性。
| 属性或方法 | 描述 |
| add() | 添加队列元素的方法 |
| delete() | 删除队列元素的方法 |
| length | 获取队列元素长度的属性 |
创建链表类
// 定义链表节点类型 interface LinkedListNode { value: number; next: LinkedListNode | null; } // 链表类 class LinkedList { // 私有属性，表示队头节点 private head: LinkedListNode | null = null; // 私有属性，表示队尾节点 private tail: LinkedListNode | null = null; // 私有属性，用来表示队列的长度 private len: number = 0; /** * @method add * @description 添加队列元素，添加到队头位置 * @param n number */ add(n: number) { // 生成链表节点 const node: LinkedListNode = { value: n, next: null, }; // head节点特殊处理 if (this.head === null) { this.head = node; } // 获取当前tail节点 const tailNode = this.tail; // 当前tail节点存在，则将next指针，指向node if (tailNode) { tailNode.next = node; } // 更新tail节点的指向 this.tail = node; // 注意，这里队列长度单独计算的，长度+1 this.len++; } /** * @method delete * @description 出队 - 从队头出 * @returns number | null */ delete(): number | null { // 获取head节点 const headNode = this.head; // 特殊情况处理 if (headNode === null) return null; // 有了长度的为0的判断，就不用处理tail节点的指向了 if (this.len === 0) return null; // 获取头结点的值 const value = headNode.value; // 更新头结点的指向 this.head = headNode.next; // 队列长度 -1 this.len--; // 返回结果 return value; } /** * @description 返回队列的长度 */ get length(): number { return this.len; } }
性能测试
// 入队10W个元素 console.time('add - linkedList'); for (let i = 0; i < 10 * 10000; i++) { linkedListQueue.add(i); } console.log(linkedListQueue.length); console.timeEnd('add - linkedList'); console.time('delete - linkedList'); for (let i = 0; i < 10000; i++) { linkedListQueue.delete(); } console.timeEnd('delete - linkedList');
网络异常，图片无法展示
|
算法复杂度分析下：
- 空间复杂度就是O(n)O(n)O(n)，随着n的增大，链表空间长度线性增长；
- 时间复杂度
add方法 O(1)O(1)O(1)、delete方法O(1)O(1)O(1)，还是非常OK的。
可对比下上一篇文章《如何实现一个队列》中实现队列的两种方式的性能。
所以，性能对比下，使用链表实现队列的形式是最优的！
