基于单向链表实现高性能队列及性能对比分析
数据结构选型：数组与链表的队列实现对比
在实现队列（Queue）这一基础数据结构时，开发者通常面临两种底层存储方式的选择：数组或链表。队列的核心特性是先进先出（FIFO, First-In-First-Out），这意味着元素从队尾（Rear）进入，从队头（Front）离开。
理论性能分析
- 数组实现：内存连续分布。在队尾追加元素（如
push）的时间复杂度为 O(1)，但在队头移除元素（如shift）时，底层引擎需要将后续所有元素向前移动一位以填补空缺，时间复杂度退化为 O(n)。 - 链表实现：内存非连续分布。通过维护头尾指针，在队尾添加节点和在队头移除节点均只需修改指针指向，无需移动其他数据，时间复杂度稳定在 O(1)。
结论：在频繁进行出队操作的场景下，基于链表实现的队列在性能上具有显著优势。
链表队列的核心设计
使用单向链表构建队列时，需要关注以下设计细节：
- 维护
front（队头）和rear（队尾）两个指针，分别用于出队和入队操作。 - 入队时更新
rear指针，出队时更新front指针。 - 使用独立的变量缓存队列长度（
size），避免每次获取长度时遍历整个链表（O(n) 开销）。
TypeScript 代码实现
以下是使用 TypeScript 重构后的链表队列实现。代码优化了节点定义与指针操作逻辑，引入了泛型支持，并采用了更语义化的命名。
/**
* 链表节点定义
*/
interface ListNode<T> {
val: T;
next: ListNode<T> | null;
}
/**
* 基于单向链表实现的队列
*/
export class LinkedListQueue<T> {
private front: ListNode<T> | null = null;
private rear: ListNode<T> | null = null;
private count: number = 0;
/**
* 入队操作
*/
enqueue(item: T): void {
const node: ListNode<T> = { val: item, next: null };
if (this.rear) {
this.rear.next = node;
} else {
// 队列为空时，front 和 rear 指向同一节点
this.front = node;
}
this.rear = node;
this.count++;
}
/**
* 出队操作
*/
dequeue(): T | undefined {
if (!this.front || this.count === 0) {
return undefined;
}
const val = this.front.val;
this.front = this.front.next;
// 如果队列变空，需同步重置 rear 指针
if (!this.front) {
this.rear = null;
}
this.count--;
return val;
}
/**
* 获取队列当前长度
*/
get size(): number {
return this.count;
}
}
单元测试验证
通过 Jest 框架对核心逻辑进行覆盖测试，确保入队、出队及边界条件（如空队列出队）的正确性。
import { LinkedListQueue } from './linked-list-queue';
describe('LinkedListQueue 核心逻辑测试', () => {
let queue: LinkedListQueue<number>;
beforeEach(() => {
queue = new LinkedListQueue<number>();
});
test('入队操作应正确更新队列长度', () => {
expect(queue.size).toBe(0);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
expect(queue.size).toBe(3);
});
test('出队操作应遵循先进先出原则', () => {
expect(queue.dequeue()).toBeUndefined();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
expect(queue.dequeue()).toBe(10);
expect(queue.dequeue()).toBe(20);
expect(queue.size).toBe(1);
});
});
性能基准测试 (Benchmark)
为了直观验证理论分析，我们编写了性能测试脚本，对比数组和链表在 10 万次出队操作下的耗时表现。
import { LinkedListQueue } from './linked-list-queue';
const LIMIT = 100_000;
// 链表队列性能测试
const linkedQueue = new LinkedListQueue<number>();
for (let i = 0; i < LIMIT; i++) {
linkedQueue.enqueue(i);
}
console.time('LinkedListQueue Dequeue');
for (let i = 0; i < LIMIT; i++) {
linkedQueue.dequeue();
}
console.timeEnd('LinkedListQueue Dequeue');
// 数组队列性能测试
const arrayQueue: number[] = [];
for (let i = 0; i < LIMIT; i++) {
arrayQueue.push(i);
}
console.time('ArrayQueue Shift');
for (let i = 0; i < LIMIT; i++) {
arrayQueue.shift();
}
console.timeEnd('ArrayQueue Shift');
测试结果分析：
在 10 万次数据量的基准测试中，数组的 shift 操作由于引发了大量的内存搬移，耗时通常高达数千毫秒；而链表队列的 dequeue 操作仅涉及指针重定向，耗时通常稳定在几毫秒到十几毫秒之间。两者在出队性能上存在数量级的差异，充分证明了在实现高频出队的队列场景时，链表数据结构的优越性。
