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

题目如下

• 链表和数组哪个实现队列更快？

补充

• 数组是连续存储，push很快，shift很慢
• 链表是非连续存储，add和delete都很快（但查找很慢）
• 链表实现队列要更快

思路如下

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

/**
 * @description 用链表实现队列
 * @author sola-grj
 * 空间复杂度O(n)
 * add 时间复杂度 链表O(1) 数组O(1)
 * delete时间复杂度 链表O(1) 数组O(n)
 * 数据结构的选择，要比算法优化更重要
 */

interface IListNode {
    value: number;
    next: IListNode | null;
}

export class ListToQueue {
  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 {
    return this.len
  }
}

单元测试

/**
 * @description 链表实现队列 test
 * @author sola-grj
 */

import { ListToQueue } from './queue-with-list'

describe('链表实现队列', () => {
    it('add and length', () => {
        const q = new ListToQueue()
        expect(q.length).toBe(0)

        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.length).toBe(3)
    })
    it('delete', () => {
        const q = new ListToQueue()
        expect(q.delete()).toBeNull()

        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.delete()).toBe(100)
        expect(q.delete()).toBe(200)
        expect(q.delete()).toBe(300)
        expect(q.delete()).toBeNull()
    })
})