chromium中的LinkedList

为什么使用LinkedList而不是std::list?

使用LinkedList最大的理由是性能。一般来说std:list的erase操作的时间复杂度是O(n),因为std:list要遍历容器获得删除元素的迭代器。
而LinkedList的erase操作的时间复杂度是O(1),因为它直接用LinkNode的RemoveFromList方法去删除。

为什么LinkedList不跟std::list一样需要遍历迭代器呢?这是因为LinkedList中的元素不是复制到到容器中的,LinkedList中存放的是元素的指针,所以元素本身就可以调用RemoveFromList把自己从容器中删除。这个特性带来的另外一个好处:插入新元素的时候,LinkedList不需要从heap中分配内存。

LinkedList就是对元素指针进行简单的封装管理,优点是没有对管理的元素有复制操作,元素加入到容器,元素本身跟放入容器中的元素是一样的。

使用LinkedList

使用LinkedList前,需要用LinkNode把栈中的元素封装起来。如下:

MyStruct就是我们要放入LinkedList中管理的真正数据类型。

LinkedList可以管理栈中的元素,也可以管理堆中的元素。

 注意

不能从一个函数中返回LinkedList<MyNodeType>,因为LinkedList.root_已经失效。

总结

总体来说使用LinkedList还是挺繁琐的,应用场景也比较特殊,而且不能使用stl中那些标准的算法。所以除非为了追求极致的性能,还是推荐使用std::list。

LinkedList代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注