【9RIA—iloveas】— 【性能优化讨论】趣谈数组/Vector/Dictionary/链表的访问效率(4完) - 11RIA 闪客社区 - 最赞 Animate Flash 论坛

上传

点击文件名下载附件

把这些信息连成一条线，就形成了链条状的结构（图 14），所以这样的集合类型有个很形象的名称——链表，虽然它不是AS3的内置类，但我们完全可以自己实现它。

(, 下载次数: 57)

上传

点击文件名下载附件

链表的特征就是其中的每个元素都记录着下一个元素的位置，所以它在遍历的过程中可以直接定位到下一元素，而无需像数组/Vector那样，每次循环都要重新回到马路的入口。

如果当前对象的下一个元素为空，那就意味着链表已经到达末尾，遍历完成（图 15）。

(, 下载次数: 54)

上传

点击文件名下载附件

有时候我们需要反向遍历，那我们就可以把上一个元素的位置都记录下来，从而形成双向链表（图 16）。

(, 下载次数: 50)

上传

点击文件名下载附件

如果想实现折返功能（即到达末尾的时候回到第一个对象），那么就可以将最后一个对象的下一元素指向到链表的开头，从而得到环状链表的效果（图 17，这个图有点偷懒了，没做好）。

(, 下载次数: 52)

上传

点击文件名下载附件

下面我引用某高手用AS3实现的链表代码。首先要有一个链表类：

[Actionscript3] 纯文本查看 复制代码

public class LinkedList {



    public firstNode:*;



    public function LinkedList() {



    }



}

然后链表中的每个元素都包含上一个和下一个的引用：

[Actionscript3] 纯文本查看 复制代码

public var nextNode:*;



public var prevNode:*;

具体的遍历代码可参阅下面的链接：

http://bbs.9ria.com/thread-55240-1-1.html（已失效）

不过，就我贴出来的代码而论，这个链表结构显然在类型转换方面存在一定的性能问题。不过作为一个通用的链表类，使用泛型也是仅有的办法。

在实际项目开发中，你可以按照这样的思路实现固定类型的链表：

[Actionscript3] 纯文本查看 复制代码

public class MySpriteLinkedList {



    public firstNode:MySprite;



    public function LinkedList() {



    }



}

[Actionscript3] 纯文本查看 复制代码

public class MySprite extends Sprite{



  public var nextNode:MySprite;



  public var prevNode:MySprite;



}

经过这样的优化以后，类型转换的效率就可以提高很多了，但是它只能构建元素类型为MySprite的链表，如果想要换成其他的类，那你还得按照上面的写法重新给别的类再写一遍，相当麻烦，这让我感到灰常蛋疼，如果能给我们自定义像Vector那样的类，比如LinkedList.<T>，那该有多完美啊！

可见，链表在遍历寻址和类型转换方面优化得相当不错，它充分吸取了Array和Vector最最精华的地方。

至于push/unshift一类的操作，链表类也能实现，而且效率绝对优于Array/Vector，因为操作都是简单的引用更改。我上面给出的链接已包含相关代码，这里就不再重复了。

不过，链表也并不是个万能的数据结构，因为它已经没有编号的概念了，所以，想要单独访问链表中的某一个元素，比如第5个的时候，就需要在AS层循环4次才能获得，如果编号值较大，那么访问的效率就反而不如Vector和Array了。

此外，for each...in形式的遍历可能在寻址方面已经做了一些针对性的优化操作（这估计也是导致在遍历里删除元素后，数据访问出错的原因之一），不过具体机制我还没搞清楚，欢迎各位发表下自己的看法。

所以在项目开发中，我们应根据实际情况，选择最合适的数据类型，如果1种类型无法兼顾多方面的优势，那大家还可以把它们结合在一起。举个栗子，比如一组元素既要进行遍历又要对个别元素进行访问，那么就可以把这批元素同时推入到链表和数组中，从而让各方面的执行效率都达到最优的状态。

（完）

最后，发出一个高清的 PDF版本（包含1-4片帖子的所有内容），喜欢的请收藏：
(, 下载次数: 3)