Cocos Creator实战：用TypeScript实现单向链表管理动态数据队列

1. 单向链表到底解决什么问题我在用 Cocos Creator 做 UI 列表、NPC 追逐队列和战斗指令序列时频繁遇到一个尴尬局面明明只是把数据排个队却要为一两个单独的增删操作去翻 JavaScript 原生数组的splice、shift、unshift性能倒是其次关键是代码一多谁在什么时候改了数组顺序、谁把引用搞丢了全靠肉眼 debug。后来我干脆在多个项目里统一用单向链表管理线性数据问题一下子清晰了很多。单向链表的核心价值是在不移动数据本身的情况下只通过改指针就能完成插入和删除。这和水果摊排队很像每个人只记住下一个是谁前面的人离开队伍时只需要让上一个人的手搭到再下一个人肩膀上后面整条队伍不用挪动半步。用数组做同样的事意味着整段内存要集体搬家用链表做只改一两处引用。那既然人总要排队为什么不是所有场景都用链表因为链表也有明显短板按下标随机访问是 O(n)、内存不连续、缓存不友好。实际项目的通用做法是高频随机访问用数组高频中间插入删除用链表数据量小随便用数据量大了再认真权衡。Cocos Creator 场景里最合适的场景通常有这几类音效播放队列不断有新音效插入播完从头部移除。回收对象池的延迟释放链表对象不立即回收而是按过期时间排队逐帧检查头部。战斗角色行动顺序表角色随时可能死亡、离场需要在任意位置删除节点还要在回合中插入新行动。分帧加载资源队列一批资源依次加载支持随时取消某个还没轮到加载的任务。在做这类功能时我需要的不是“一个能跑的 demo”而是“一套怎么改都不容易出错的链表封装”。所以这篇文章重点不是贴一份最小实现而是把节点设计、哨兵节点、增删改查、链表逆置、排序、遍历时机这些实际工程里绕不过去的细节全部拆开讲最后给出 TypeScript 实现和踩坑经验。适合已经会写基本循环和类的同学不要求你有算法基础但建议你跟着敲一遍。2. 整体设计从节点到哨兵节点这一步决定后面少踩多少坑2.1 为什么用类封装而不是直接拼指针初学者很容易写出直接在组件里摆弄node.next的代码看起来简单但项目里结构和逻辑一旦多起来就管不住指针了。我的习惯是封装成ListNode和LinkedList两个类前者只负责“站在队伍里”后者负责“维护队伍秩序”。ListNode的定义要非常克制只存两样东西该节点携带的数据、指向下一个节点的引用。不要把 prev、index、是否已删除这类状态塞进去否则每个节点都会变成小仓库维护成本直线上升。// 节点类只负责数据和指向下一个节点 export class ListNodeT { public data: T; public next: ListNodeT | null null; constructor(data: T) { this.data data; } }为什么不要在这里加 prev 指向上一个节点因为单向链表的名字已经说明了一切——它只支持从头部向尾部单向遍历。如果确实需要回头访问前一个节点优先考虑双向链表而不是在单向链表里频繁遍历从头找前驱。很多性能事故都是因为数据结构选错了而不是实现不够好。2.2 哨兵节点链表里的“虚拟头”我给链表加了一个哨兵节点dummy node它不存储业务数据永远固定在链表的头部之前。也就是说一个空链表不是head null而是head - dummyNode。null - dummyNode - node1 - node2 - node3 - null哨兵节点的好处做过 LeetCode 链表题的同学应该深有体会它让“删除第一个节点”和“删除中间节点”的代码完全统一不用再写 if 判断是不是头节点。插入同理无论插入位置在哪逻辑都是“找到目标节点的前一个节点然后改指针”。另一种常见做法是不用哨兵直接用head指向第一个真实节点空链表时head null。这种写法更省一个节点但每次增删都要额外处理“头节点为空”或“删除的是头节点”这种边界。两个方案没有绝对的谁对谁错但我强烈建议用哨兵节点因为后面要实现链表反转、按值删除、排序时哨兵能把代码里至少三分之一的边界条件抹掉可读性提升非常明显。2.3 对外暴露的数据结构设计在设计对外 API 时我遵循的原则是调用方永远不需要知道节点内部长什么样。所以链表类对外只操作数据比如append(data)、insertAt(index, data)、remove(data)、getAt(index)而不是让调用方持有ListNode自己动指针。不过有一个例外如果调用方需要持续持有某个节点的引用希望将来直接通过节点删除或插入那我会额外提供findNodeByData或toNode之类的内部方法它的返回类型是ListNodeT。这种“持有节点引用”的模式在处理对象池、音效句柄时非常实用因为避免了下标失效带来的各种头疼问题。3. 核心方法实现与为什么要这么写3.1 初始化与 append从尾巴上加入新节点append是最常用的方法它的语义是“在链表尾部追加一个新节点”。大多数人第一反应是先找到 tail再让 tail.next 指向新节点。但我们的链表只有头没有尾所以只能从头开始遍历到末尾。这里有一个工程取舍如果追加操作非常频繁比如每帧都要往链表里塞几十个节点可以额外维护一个tail指针让append的复杂度从 O(n) 降为 O(1)。代价是删除节点、反转链表、排序后都需要重新校正 tail很容易漏。我的建议是先实现最简单的版本等确实出现性能瓶颈再引入 tail 优化。绝大多数 UI 列表、对象队列场景链表长度不过几百O(n) 的 append 完全够用。public append(data: T): void { const newNode new ListNode(data); let cur this._sentinel; while (cur.next ! null) { cur cur.next; } cur.next newNode; }判断“当前节点是不是最后一个节点”的条件是next null不是cur null很多初学者在这里写反。整个过程等价于排队从头开始走一直走到队伍最后一个人的背后再把新人接上去。3.2 insertAt在指定位置插入别让“第几个”搞混insertAt(index, data)的难点在于 index 是“从 0 开始”还是“从 1 开始”以及插入位置和遍历次数的对应关系。我们的约定和数组保持一致index 0 表示插入到最前面。有了哨兵节点这个操作可以统一成“从哨兵节点出发向后走 index 步然后插入到该节点的后面”。public insertAt(index: number, data: T): boolean { if (index 0) return false; let cur this._sentinel; let step index; while (step 0) { if (cur.next null) { return false; // 越界了 } cur cur.next; step--; } const newNode new ListNode(data); newNode.next cur.next; cur.next newNode; return true; }这里最容易踩坑的就是边界当index等于当前链表长度时cur会停在最后一个节点上然后newNode被接到尾巴后面这个行为是合法的等价于 append。当index超过链表长度时因为循环里发现cur.next null直接返回 false。当初我没加这个检查插超了索引之后链表就静默少了一个节点排查到怀疑人生。3.3 remove、removeAt、getAt三个最容易写错边界的方法按数据删除是最常用的操作。因为单向链表只能找到“下一个”节点所以删除某个节点本质上要修改它的前一个节点的 next。我们可以用经典的“双指针”方式一个指针负责停留在前一个节点另一个指针向后探。public remove(data: T): boolean { let prev this._sentinel; let cur this._sentinel.next; while (cur ! null) { if (cur.data data) { prev.next cur.next; return true; } prev cur; cur cur.next; } return false; }注意这个实现删除的是第一个匹配的节点不是所有匹配项。如果业务上需要删除链表中所有等于该数据的节点循环体里要在删除后继续往下走不要一删就 return。removeAt(index)和getAt(index)本质是同一件事的两个方向一个改指针一个只读。它们的共同坑点都是index越界一个友好一点的封装应该返回 boolean 或 null而不是直接抛异常因为游戏里“列表动态变化导致下标过期”太常见了抛异常只会让上层崩得更快。3.4 链表逆置从“从前到后”变成“从后到前”链表逆置是面试中出现率最高的链表题也是实际中用得比想象多的操作——比如回放系统里要把操作记录反过来执行。逆置的核心思路是遍历原链表每经过一个节点就把它摘下来插到哨兵节点的后面。public reverse(): void { let cur this._sentinel.next; let prevTail this._sentinel.next; // 逆置后原来的头变成尾巴 this._sentinel.next null; // 先把链表断开 while (cur ! null) { const nextNode cur.next; cur.next this._sentinel.next; this._sentinel.next cur; cur nextNode; } if (prevTail ! null) { // 原来的头节点现在是尾节点它的 next 应该指向 null // 这里其实无需额外操作因为断链时已经处理了 } }更容易理解的方式是准备三个指针prev指向“已经逆置好的部分的头”cur指向“当前要处理的原节点”next暂存cur.next。每次把cur.next改成prev然后三个指针整体向后移动。我建议你在草稿纸上画出 4 个节点的手写步骤比盯代码快得多。需要特别提醒逆置后原来带头节点的链表语义会发生变化如果外部有人持有某个节点的引用这个节点的 next 关系会全部反转引用本身的 data 不受影响。最稳妥的做法是逆置完成后通知所有依赖链表顺序的模块“顺序已变”或者干脆不要长期持有节点引用。3.5 链表排序不移动节点只改指针链表排序和数组排序最大的区别是数组可以随便交换元素链表也可以但因为节点在物理上不连续交换元素会牵动大量指针。一个更优雅的方案是拆链再插先把链表变成一个一个孤立节点再用有序插入的方式重新组装。这种方式时间复杂度是 O(n^2)对几百个节点完全够用。还有一种实现是归并排序因为归并天然适合链表时间复杂度 O(n log n)不需要额外的数组存储空间。实际项目如果不是超大链表优先用插入排序代码短、容易调试。等链表出现在性能热点路径上再换归并。public sort(compareFn?: (a: T, b: T) number): void { const defaultCompare (a: T, b: T) (a b ? -1 : a b ? 1 : 0); const cmp compareFn ?? defaultCompare; let cur this._sentinel.next; this._sentinel.next null; while (cur ! null) { const nextNode cur.next; // 把 cur 按顺序插入到已经排好的链表中 cur.next null; let prev this._sentinel; let sorted this._sentinel.next; while (sorted ! null cmp(sorted.data, cur.data) 0) { prev sorted; sorted sorted.next; } cur.next sorted; prev.next cur; cur nextNode; } }这种“从旧链表头部摘一个往新链表合适位置插一个”的做法本质上就是用一个临时结果链表替换原链表。由于我们是断链重建原链表里节点的 next 会在过程中被改写所以操作之前如果还有别的遍历在跑必须先停下来。4. 实际操作过程完整 TypeScript 实现与 Cocos Creator 集成4.1 创建链表工具文件在 Cocos Creator 3.8 项目中我习惯把所有通用数据结构放进assets/scripts/common/ds/目录。新建一个LinkedList.ts把前面这些方法完整合到一起。文件内部不依赖 cc 引擎的任何模块所以你在纯 TypeScript 环境、小程序、Node.js 里都能复用同一份代码。export class ListNodeT { public data: T; public next: ListNodeT | null null; constructor(data: T) { this.data data; } } export class LinkedListT { protected _sentinel: ListNodeT; protected _size: number 0; constructor() { this._sentinel new ListNodeT(null as any); } public get size(): number { return this._size; } public isEmpty(): boolean { return this._size 0; } public append(data: T): void { const newNode new ListNode(data); let cur this._sentinel; while (cur.next ! null) cur cur.next; cur.next newNode; this._size; } public insertAt(index: number, data: T): boolean { if (index 0 || index this._size) return false; let cur this._sentinel; let step index; while (step 0) { cur cur.next!; step--; } const newNode new ListNode(data); newNode.next cur.next; cur.next newNode; this._size; return true; } public getAt(index: number): T | null { if (index 0 || index this._size) return null; let cur this._sentinel.next!; for (let i 0; i index; i) cur cur.next!; return cur.data; } public removeAt(index: number): boolean { if (index 0 || index this._size) return false; let prev this._sentinel; let cur this._sentinel.next!; for (let i 0; i index; i) { prev cur; cur cur.next!; } prev.next cur.next; this._size--; return true; } public remove(data: T): boolean { let prev this._sentinel; let cur this._sentinel.next; while (cur ! null) { if (cur.data data) { prev.next cur.next; this._size--; return true; } prev cur; cur cur.next; } return false; } public reverse(): void { let cur this._sentinel.next; this._sentinel.next null; while (cur ! null) { const nextNode cur.next; cur.next this._sentinel.next; this._sentinel.next cur; cur nextNode; } } public sort(compareFn?: (a: T, b: T) number): void { const defaultCompare (a: T, b: T) (a b ? -1 : a b ? 1 : 0); const cmp compareFn ?? defaultCompare; let cur this._sentinel.next; this._sentinel.next null; while (cur ! null) { const nextNode cur.next; cur.next null; let prev this._sentinel; let sorted this._sentinel.next; while (sorted ! null cmp(sorted.data, cur.data) 0) { prev sorted; sorted sorted.next; } cur.next sorted; prev.next cur; cur nextNode; } } public clear(): void { this._sentinel.next null; this._size 0; } public toArray(): T[] { const result: T[] []; let cur this._sentinel.next; while (cur ! null) { result.push(cur.data); cur cur.next; } return result; } }这个版本我特意把_size加入了所有增删方法里因为很多初版实现忽略 size后面想快速判断越界都没办法。size 看似小事但它是链表从“玩具”走向“可用工具”的一个重要标志。4.2 在组件里跑一个最小示例在 Cocos Creator 里我通常是挂一个组件到空节点上用update里的一小段逻辑来验证链表行为。比如维护一个对象池的待回收列表import { _decorator, Component } from cc; import { LinkedList } from ./LinkedList; const { ccclass, property } _decorator; ccclass(LinkedListDemo) export class LinkedListDemo extends Component { private _recycleList new LinkedList() void(); start() { this._recycleList.append(() console.log(回收对象A)); this._recycleList.append(() console.log(回收对象B)); this._recycleList.insertAt(0, () console.log(紧急回收对象C)); console.log(当前链表大小, this._recycleList.size); // 3 console.log(第2个元素, this._recycleList.getAt(1)); // 回收对象B } update(deltaTime: number) { // 每帧只回收一个对象避免一帧卡死 if (!this._recycleList.isEmpty()) { const first this._recycleList.removeAt(0); if (first) { // 这里拿到的其实是 data不是节点 } } } }注意我的removeAt返回的是 boolean如果你想取回被删除的数据看代码会觉得很别扭。实际项目里我更推荐把removeAt改成removeAtGet(index: number): T | null返回被删除节点的 data。不过为了统一接口语义上面的示例用了 boolean 版本。如果你要抄作业建议给removeAt加一个removeFirst(): T | null专门从头部取出并删除这个组合在队列型需求里出现频率极高。4.3 与 Cocos Creator 组件、节点结合时的两个特殊技巧第一不要在遍历链表的过程中执行增删操作。这是链表使用中最容易犯的错误。比如你正在for循环里遍历一个音效列表突然一个音效播完触发回调要把它从链表里删掉遍历的cur.next就可能变成 null导致你漏掉后续节点。稳妥做法是先在遍历中收集要删除的节点引用等遍历结束后统一删除。第二链表节点里存组件引用时要小心节点销毁。Cocos Creator 中节点被销毁后组件实例仍然可能存在一段时间如果链表里存的是组件引用而组件已经被销毁访问它的任何属性都可能报错。我通常会在销毁时显式调用list.remove(comp)或者存节点 ID 而不是组件引用用的时候再通过find查询。5. 高频问题与排查经验实时栈5.1 遍历链表时“丢节点”的经典原因丢节点的本质通常是你删除了当前节点然后又把cur cur.next但此时cur.next已经被上一步删掉的那个节点的 next 覆盖了导致跳过了下一个节点。更安全的方式是删除前先把nextNode cur.next存起来删除完成后再赋值给cur。let prev this._sentinel; let cur this._sentinel.next; while (cur ! null) { const nextNode cur.next; if (shouldDelete(cur.data)) { prev.next nextNode; } else { prev cur; } cur nextNode; }这种写法无论是否删除遍历都能继续向下走。5.2 size 与实际节点数对不上size 出问题几乎可以断定是某次修改没有维护 size。我查代码时会直接从增删方法下手一个个核对。另一种隐蔽情况是有人直接拿着ListNode绕过链表自己改了node.next这会让链表内部完全失控。所以我在设计时把节点指针操作限制为类内部可见对外不暴露节点引用的修改能力。5.3 排序后遍历顺序还是不对可能原因有两个一是比较函数写反了二是你在排序前有其他代码也持有旧链表的节点引用排序后他们指向的节点虽然还在但位置已经变了造成遍历结果和预期对不上。我的建议是排序这种全量重排操作尽量避免在事件回调过程中触发最好放在一帧的开始或结束等“安全时间片”。5.4 内存泄漏循环引用与节点滞留链表的内存泄漏比数组隐蔽。如果节点里持有组件或大的资源引用而这个节点被从链表移除后你仍然在业务代码的某个闭包里保存着它那该节点和它引用的资源都会无法释放。另一个常见问题是对象池里的链表长期持有节点但节点数据已经被业务清空导致旧数据残留。解决方案很直接移除节点时把node.data null显式清掉避免无意间被闭包捕获。5.5 链表的迭代器要不要做我建议后续一定要给链表加一个迭代器尤其是当你在 Cocos Creator 里配合for...of使用。TypeScript 支持[Symbol.iterator]()实现起来不复杂却能大幅简化遍历代码。如果没有迭代器你每次都要写let cur list.head这种暴露内部结构的代码破坏封装。6. 在真实项目里我最终会选择链表还是数组坦率说Cocos Creator 项目里绝大多数列表用数组就够了数组的内存连续性和随机访问优势在几百个元素的规模下非常明显。我使用链表的高频场景其实很集中需要在任意位置频繁增删、且遍历顺序经常变化的地方。例如战斗系统的行动顺序表每回合要插入新行动、移除死亡单位的行动、调整某些单位的优先级如果全用数组每次 splice 都要移动整段元素用链表加哨兵插入移除只改指针代码逻辑也更直观。另一个例子是音效管理多个音效同时播放时的播放句柄管理、顺序调度用链表比数组更不容易出现“删除中间音效导致后续句柄全部移位”的情况。当然音效数量少数组也出不了大事但链表给了你一种更接近人类思考方式的组织形式——你不是在维护一块连续内存而是在维护一条有先后关系的对象链。性能上链表最大的代价是每个节点都要额外存储 next 指针内存开销大约多 8 字节这点在移动游戏里可以忽略不计。真正的成本是 cache miss节点不连续会导致遍历时缓存命中率低所以如果你要高频顺序遍历整个链表反而不如数组。这就是为什么我通常只在“增删频率远高于遍历频率”的数据结构上使用链表。7. 关于这套实现的最后几点补充写到这里这套单向链表已经能覆盖我日常开发里 90% 的需求了。它没有做成一个巨大的容器库而是尽量保持核心逻辑短小、清楚方便你在遇到特殊需求时按自己的规则修改。比如想把它改成双向链表只需要在节点里加一个prev在插入和删除时多维护一组指针想把它变成环形链表让尾节点的 next 指向哨兵即可。但我更想强调的是数据结构选型是一种思维习惯。很多人一遇到排序、查找就下意识用数组一遇到“顺序不重要”就下意识用集合却很少认真想“这个线性序列到底是不是真的需要按下标访问”。如果你能习惯先用链表的思路去看这类问题你写出来的代码通常会更接近业务语义也更容易在将来做对象池、分帧处理这类性能优化。我在实际项目里的体会是链表代码本身并不难难的是在“该用链表”的时候果断用在“数据量极小、改动频率低”的时候不硬上以及时刻记住遍历和修改不能同时进行。这套设计我在多个中大型 Cocos 项目里反复用过踩过的坑基本都在上面了希望你能比我少走几步弯路。