【前端算法】链表和数组实现队列的区别

简介: 比较链表和数组实现队列的性能

链表和数组,哪个实现队列更快?

  • 数组是连续存储,push很快,shift很慢
  • 链表是非连续存储,add和delete都很快(但查找很慢)
  • 结论:链表实现队列更快

链表实现队列

  • 单向链表,但要同时记录head和tail
  • 要从tail入队,从head出队,否则出队时tail不好单位
  • length要实时记录,不可遍历链表获取

代码实现

interface ILinkNode {
  value: number
  next: ILinkNode | null
}

class Myqueue {
  private len:number = 0
  private head:ILinkNode | null = null
  private tail:ILinkNode | null = null

  /**
   * 入队,在tail位置
   */
  add(n:number) {

    const linkNode: ILinkNode = {
      value: n,
      next: null
    }

    // 处理head,如果head是null,说明当前队列是个空的
    if (this.head == null) {
      this.head = linkNode
    } 

    // 处理tail
    const tailNode:ILinkNode | null = this.tail

    if (tailNode) {
      tailNode.next = linkNode
    }

    // 将新的节点,作为队尾部
    this.tail = linkNode

    // 记录长度+1
    this.len++;
  }

  /**
   * 出队,在head位置
   */
  delete(): number | null {

    // 获取当前head,如果是null,说明是个空队列,返回null
    const headNode: ILinkNode | null= this.head
    if (headNode == null) return null;
    if (this.len <= 0) return null;

    // 当不是空队列时,取值
    const value:number = headNode.value

    // 处理head,让head指针指向下一个元素, 当前被删除的节点由js的gc处理
    this.head = headNode.next

    // 记录长度-1
    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) // 3
console.log(q.delete()) // 100
console.log(q.length) // 2
console.log(q.delete()) // 200
console.log(q.length) // 1
console.log(q.delete()) // 300
console.log(q.length) // 0

单元测试

describe('链表实现队列', () => {
    it('add And length',() => {
        const q = new Myqueue()
        expect(q.length).toBe(0)
        
        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.length).toBe(3)
    })
    
    it('delete',() => {
        const q = new Myqueue()
        expect(q.delete()).toBeNull()
        
        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.delete()).toBe(100)
        wxpect(q.delete()).toBe(200)
        wxpect(q.delete()).toBe(300)
        wxpect(q.delete()).toBeNull()
    })
})

性能测试

// 这是链表实现的队列
const q = new Myqueue();
console.time('link with queue');
for (let i = 0; i < 10 * 10000; i++) {
  q.add(i);
}
for (let i = 0; i < 10 * 10000; i++) {
  q.delete();
}
console.timeEnd('link with queue');

// 这个是由之前2个栈实现的队列
const q1 = new MyQueue1();
console.time('stack with queue');
for (let i = 0; i < 10 * 10000; i++) {
  q1.add(i);
}
for (let i = 0; i < 10 * 10000; i++) {
  q1.delete();
}
console.timeEnd('stack with queue');

// 这个是纯数组操作
const arr = [];
console.time('link with array');
for (let i = 0; i < 10 * 10000; i++) {
  arr.push(i);
}
for (let i = 0; i < 10 * 10000; i++) {
  arr.shift();
}
console.timeEnd('link with array');

打印结果:

link with queue: 14.319ms
stack with queue: 35.966s
link with array: 9.087s

由此可见在20万数据循环操作下,链表实现的队列最快,是栈队列的2572倍,是数组的643倍。这个数值具体看设备算力,这里只做参考。

性能分析

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

总结:

  • 数据结构的选择,要比算法优化更重要
  • 要有时间复杂度的敏感性,如length不能遍历查找
相关文章
|
2月前
|
监控 前端开发 JavaScript
前端工程化和传统前端开发的区别是什么?
前端工程化相比传统前端开发,在开发模式、代码组织与管理、构建与部署流程、团队协作、性能优化以及技术选型等方面都有了显著的改进和提升,能够更好地应对现代前端应用开发的复杂性和高要求。
|
5月前
|
前端开发 JavaScript 开发者
【前端开发者的福音】彻底改变你编码习惯的神奇数组迭代技巧——从基础到进阶,解锁 JavaScript 数组迭代的N种姿势!
【8月更文挑战第23天】在Web前端开发中,数组是JavaScript中最常用的数据结构之一,掌握高效的数组迭代方法至关重要。本文详细介绍了多种数组迭代技巧:从基础的`for`循环到ES6的`for...of`循环,再到高阶方法如`forEach`、`map`、`filter`、`reduce`及`some`/`every`等。这些方法不仅能提高代码的可读性和维护性,还能有效优化程序性能。通过具体的示例代码,帮助开发者更好地理解和运用这些迭代技术。
50 0
|
5月前
|
前端开发 UED 开发者
颠覆你的前端知识:防抖与节流的区别及实战解析!
【8月更文挑战第23天】在Web前端开发中,处理用户界面交互产生的事件可能会影响性能。为此,我们有两种优化方法:防抖(debounce)和节流(throttle)。防抖确保函数仅在事件停止触发一段时间后执行一次,适用于如搜索自动补全场景。而节流则确保函数按固定时间间隔执行,不管用户操作频率如何。本篇技术博客将深入解析两者差异并提供示例代码,帮助开发者更好地理解和应用这些技巧以提升应用性能和用户体验。
92 0
|
3月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
126 64
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
66 5
|
3月前
|
JavaScript 前端开发 算法
前端优化之超大数组更新:深入分析Vue/React/Svelte的更新渲染策略
本文对比了 Vue、React 和 Svelte 在数组渲染方面的实现方式和优缺点,探讨了它们与直接操作 DOM 的差异及 Web Components 的实现方式。Vue 通过响应式系统自动管理数据变化,React 利用虚拟 DOM 和 `diffing` 算法优化更新,Svelte 通过编译时优化提升性能。文章还介绍了数组更新的优化策略,如使用 `key`、分片渲染、虚拟滚动等,帮助开发者在处理大型数组时提升性能。总结指出,选择合适的框架应根据项目复杂度和性能需求来决定。
|
3月前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
|
3月前
|
JSON 前端开发 数据格式
@RequestMapping运用举例(有源码) 前后端如何传递参数?后端如何接收前端传过来的参数,传递单个参数,多个参数,对象,数组/集合(有源码)
文章详细讲解了在SpringMVC中如何使用`@RequestMapping`进行路由映射,并介绍了前后端参数传递的多种方式,包括传递单个参数、多个参数、对象、数组、集合以及JSON数据,并且涵盖了参数重命名和从URL中获取参数的方法。
268 0
@RequestMapping运用举例(有源码) 前后端如何传递参数?后端如何接收前端传过来的参数,传递单个参数,多个参数,对象,数组/集合(有源码)
|
3月前
|
JavaScript 前端开发 应用服务中间件
Vue开发中,在实现单页面应用(SPA)前端路由时的hash模式和history模式的区别及详细介绍
Vue开发中,在实现单页面应用(SPA)前端路由时的hash模式和history模式的区别及详细介绍
53 0
|
3月前
|
存储 前端开发 API
前端开发中,Web Storage的存储数据的方法localstorage和sessionStorage的使用及区别
前端开发中,Web Storage的存储数据的方法localstorage和sessionStorage的使用及区别
143 0