天问博客
指南
文章
Hello
指南
文章
Hello

前边有一章介绍了 用两个栈实现一个队列，本文就介绍一下怎么 用链表实现队列 ？

数据结构与算法 · 用链表实现队列

一、思路

  1. 记录链表的 head 、 tail
  2. 入队，在 tail 位置入队
  3. 出队，在 head 位置出队
  4. 队列的 length 单独记录存储

二、链表实现队列

  • TS 代码演示
interface IListNode { value: number next: IListNode | null } class MyQueue { private head: IListNode | null = null private tail: IListNode | null = null private len = 0 // 入队，在 tail 位置入队 add(n: number) { const newNode: IListNode = { value: n, next: null } // 处理 head if (this.head===null) { this.head = newNode } // 处理 tail const tailNode = this.tail if (tailNode) { tailNode.next = newNode } this.tail = newNode // 记录长度 this.len++ } // 出队，在 head 位置出队 delete():number | null { const headNode = this.head if (headNode===null) return null if (this.len<=0) return null // 取值 const value = headNode.value // 处理 head this.head = headNode.next // 记录长度 this.len-- return value } get length(): number { // length 需要单独记录存储，不能遍历链表获取，否则时间复杂度太高 O(n) return this.len } } const q = new MyQueue() q.add(100) q.add(200) q.add(300) console.log(q.length) console.log(q.delete()) console.log(q.length) console.log(q.delete()) console.log(q.length) console.log(q.delete()) console.log(q.length) console.log(q.delete()) console.log(q.length) console.log(q.delete()) console.log(q.length)

三、性能测试

使用数组的 push 、shift 操作模拟队列，来对比用链表实现的队列，进行 10万次 入队、出队模拟测试。

const q1 = new MyQueue() console.time('queue with list') for (let i = 0; i < 10 * 10000; i++) { q1.add(i) } for (let i = 0; i < 10 * 10000; i++) { q1.delete() } console.timeEnd('queue with list') const q2 = [] console.time('queue with array') for (let i = 0; i < 10 * 10000; i++) { q2.push(i) } for (let i = 0; i < 10 * 10000; i++) { q2.shift() } console.timeEnd('queue with array')
len = 0 // 入队，在 tail 位置入队 add(n) { const newNode = { value: n, next: null } // 处理 head if (this.head===null) { this.head = newNode } // 处理 tail const tailNode = this.tail if (tailNode) { tailNode.next = newNode } this.tail = newNode // 记录长度 this.len++ } // 出队，在 head 位置出队 delete() { const headNode = this.head if (headNode===null) return null if (this.len<=0) return null // 取值 const value = headNode.value // 处理 head this.head = headNode.next // 记录长度 this.len-- return value } get length() { // length 需要单独记录存储，不能遍历链表获取，否则时间复杂度太高 O(n) return this.len }

}

// 性能测试 function run() { const q1 = new MyQueue() console.time('queue with list') let s1 = performance.now() for (let i = 0; i < 10 * 10000; i++) { q1.add(i) } for (let i = 0; i < 10 * 10000; i++) { q1.delete() } document.querySelector('.box1-ms').innerText = performance.now() - s1 + ' ms'

const q2 = [] let s2 = performance.now() for (let i = 0; i < 10 * 10000; i++) { q2.push(i) } for (let i = 0; i < 10 * 10000; i++) { q2.shift() } document.querySelector('.box2-ms').innerText = performance.now() - s2 + ' ms'

}

通过运行得知 用数组模拟队列 的方法远不如 用链表实现队列 的方法的执行效率。

四、算法复杂度

  • 空间复杂度都是 O(n)
  • add 时间复杂度：链表 O(1); 数组 O(1)
  • delete 时间复杂度：链表 O(1); 数组 O(n)

总结：数据量越大越能突显算法的重要性。

《数据结构与算法》系列

  1. 什么是算法复杂度
  2. 堆(heap)、栈(stack)、队列(queue)
  3. 把一个数组旋转k步
  4. 判断字符串是否括号匹配
  5. 数组、栈、链表、队列结构与对比
  6. 用两个栈实现一个队列
  7. 反转单向链表
  8. 用链表实现队列
  9. 二分查找
  10. 查找两数之和

欢迎访问：天问博客