TS数据结构与算法之单向链表实现队列

数组和链表都可以实现队列，但数组是连续存储，push 很快， shift 很慢。链表是非连续存储，
add 和 delete 都很快（但查找很慢，需要遍历整个链表）。但综合考虑链表实现队列会更高效

链表实现队列需要注意：

• 使用单向链表，需要同时记录 head 和 tail
• 要从 tail 入队，head 出队。否则tail出队不方便定位上一个元素
• 队列长度需要单独记录，不可实时遍历获取

功能实现

添加文件： queue-with-link-list.ts

定义节点类型

export interface LinkListNode {
  value: number;
  next: LinkListNode | null;
}

实现 MyLinkListQueue

/**
 * 单向链表实现队列
 */
export class MyLinkListQueue {
  private head: LinkListNode | null = null;
  private tail: LinkListNode | null = null;
  private len: number = 0;

  /**
   * 添加元素 入队列 尾部操作
   */
  add(n: number) {
    const newNode: LinkListNode = {
      value: n,
      next: null,
    };

    // 添加新节点
    if (!this.head) {
      this.head = newNode;
    } else if (this.tail) {
      this.tail.next = newNode;
    }

    // 更新 tail
    this.tail = newNode;

    // 更新队列长度
    this.len += 1;
  }

  /**
   * 移除元素 出队列 头部操作
   */
  delete(): number | undefined {
    if (!this.head) {
      return undefined;
    }

    // 取值
    const value = this.head.value;
    
    // 更新 head
    this.head = this.head.next;
    // 更新长度
    this.len -= 1;

    return value;
  }

  get length() {
    // length 需要单独存储不可实时遍历链表（否则时间复杂度是 O(n)）
    return this.len;
  }
}

添加功能测试

// 功能测试
export const link_list_queue_test = () => {
  const q = new MyLinkListQueue();
  console.info(q.length); // 0
  q.add(100);
  console.info(q.length); // 1
  q.add(200);
  console.info(q.length); // 2
  q.add(300);
  console.info(q.length); // 3
  console.log(q.delete()); // 100
  console.info(q.length); // 2
  console.log(q.delete()); // 200
  console.info(q.length); // 1
  console.log(q.delete()); // 300
  console.info(q.length);  // 0
};

单元测试

添加文件： tests/queue-with-link-list.test.ts

import { MyLinkListQueue, LinkListNode } from '../src/utils';

describe('单向链表实现队列单元测试', () => {
  test('空链表长度为0', () => {
    const q = new MyLinkListQueue();
    expect(q.length).toBe(0);
  });

  test('向队列添加3个值', () => {
    const q = new MyLinkListQueue();
    q.add(100);
    expect(q.length).toBe(1);
    q.add(200);
    expect(q.length).toBe(2);
    q.add(300);
    expect(q.length).toBe(3);
  });

  test('移除队列元素', () => {
    const q = new MyLinkListQueue();
    q.add(100);
    q.add(200);
    q.add(300);
    expect(q.length).toBe(3);
    expect(q.delete()).toBe(100);
    expect(q.length).toBe(2);
    expect(q.delete()).toBe(200);
    expect(q.length).toBe(1);
    expect(q.delete()).toBe(300);
    expect(q.length).toBe(0);
    expect(q.delete()).toBe(undefined);
  });
});

运行单元测试输出如下：

测试通过

 PASS  tests/queue-with-link-list.test.ts (9.272 s)
  单向链表实现队列单元测试
    ✓ 空链表长度为0 (2 ms)
    ✓ 向队列添加3个值 (20 ms)
    ✓ 移除队列元素 (1 ms)

数组和链表队列性能测试

// 性能测试 链表和数组分别操作 100000 次 入队出队操作
export const link_list_quey_performance_test = () => {
  // 链表队列
  const q1 = new MyLinkListQueue();
  console.time('q1-test');
  for (let i = 0; i < 10 * 10000; i ++) {
    q1.add(i);
  }
  for (let i = 0; i < 10 * 10000; i ++) {
    q1.delete();
  }
  console.timeEnd('q1-test');

  // 数组队列
  const q2 = [];
  console.time('q2-test');
  for (let i = 0; i < 10 * 10000; i ++) {
    q2.push(i);
  }
  for (let i = 0; i < 10 * 10000; i ++) {
    q2.shift();
  }
  console.timeEnd('q2-test');
};

输出结果如下：

• q1-test: 19 ms
• q2-test: 811 ms

性能分析

数组和链表实现队列，空间复杂度都是 O(n), add的时间复杂度： 链表O(1)，数组O(1)，
delete的时间复杂度 链表O(1)，数组O(n)。数据结构的选择要比算法优化更重要，
要有时间复杂度的敏感性，如length需要单独存储。