链表用途
数据需要经常性地插入移除, 并且数据量不算很小的情况下, 一般都用链表表示
链表插入删除效率极高, 达到 O(1). 对于不需要搜索但变动频繁且无法预知数量上限的数据, 比如内存池, 操作系统的进程管理, 网络通信协议栈的 trunk 管理等等等等, 缺了它是绝对玩不转的.
在操作系统中, 链表用来分配内存, 链接了一串空闲内存. 分配容易, 释放容易.
楼上有人说了 LRU 和文件系统, 还有一个比较常用的应用是 Git.
Git 里面每次 commit 都是创建一个 node,node 包含了删减后的新文件, 然后 node 指向前一个 commit 的 node.Git checkout,delete branch,merge,rebase 这些基本上都是以链表操作为主. Git 应该算是对 linked list 很好的应用. 不用 linked list 应该很难高效地实现 Git 提供的功能.
相对于 ArrayList,LinkedList 插入是更快的. 因为 LinkedList 不像 ArrayList, 不需要在数组装满的时候要将所有的数据重新装入一个新的数组, 这是 ArrayList 最坏的一种情况, 时间复杂度是 O(n), 而 LinkedList 中插入或删除的时间复杂度仅为 O(1).ArrayList 在插入数据时还需要更新索引(除了插入数组的尾部).
我觉得在以下场景 LinkedList 比 ArrayList 有优势:
1) 你的应用不会随机访问数据. 因为如果你需要 LinkedList 中的第 n 个元素的时候, 你需要从第一个元素顺序数到第 n 个数据, 然后读取数据.
2) 你的应用更多的插入和删除元素, 更少的按索引读取数据(如果只是遍历, 区别不大). 因为插入和删除元素不涉及重排数据, 所以它要比 ArrayList 要快.
以上回答摘自知乎: 链表 (linked list) 这一数据结构具体有哪些实际应用? https://www.zhihu.com/question/60724366
ArrayList 和 LinkdList 区别
看了这么多 LinkedList 的方法, 现在我们来总结一下 ArrayList 和 LinkedList 的区别(也是顺序表和链表的区别):
(1)ArrayList 是基于动态数组实现的, LinkedList 是基于双向链表实现的.
(2)ArrayList 支持随机访问(通过下标),LinkedList 不支持.
(3)ArrayList 的查询和尾部插入元素效率较高, 中间插入和删除元素效率较低, 因为有大量的数组复制操作.
LinkedList 的插入和删除效率较高, 只需要把节点指针改变一下就行, 但是查询效率较低, 即使有双向链表的特性可以从两个方向查找, 但还是需要使用蛮力法的方式进行遍历, 所以效率较低.
(4)ArrayList 会造成一定的空间浪费, 因为随时需要探测数组容量然后扩容; LinkedList 通过节点方式进行存放数据, 不存在空间浪费.
来源: http://www.bubuko.com/infodetail-3279755.html