如何利用好链表提高插入删除的效率?

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2724 天前的主题，其中的信息可能已经有所发展或是发生改变。

刚学习了链表的基础方法...
但是书上的基础方法的 insert/removeAt 方法都是一次性的,先查找后操作...
对于相邻的 100 次操作,也还是要进行 100 次查找,提高不了效率.

是应该基于书上的代码,再扩展...还是找现成的库,还是应该怎么样....

4 条回复 • 2017-06-15 11:53:48 +08:00

ryd994

2017-06-14 17:51:51 +08:00

双向链表，做个 iterator
参考 c++ STL

yeyuexia

2017-06-14 17:58:32 +08:00

书上没有告诉你的是链表在现实世界里算是最慢的数据结构之一……题外话
如果要提高效率的话可以考虑双链表或者在外层做 cache 记录 pre

msg7086

2017-06-15 03:43:36 +08:00

可以继续学下去，什么堆啊树啊都学了就知道了。

BadMan

2017-06-15 11:53:48 +08:00

链表插入删除比较快，可是它查找慢啊。我想是不是可以将链表的数据域内容拿出来做个索引，索引指向对应链表的地址。