Java基础、中级、高级、架构面试资料

Java 程序员(CRUD程序员)为什么很少使用 LinkedList?

JAVA herman 5158浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog2,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云

其实我不想写 LinkedList 的!为什么呢?因为它没什么好些的。简单用的也少,尤其是对 CRUD 程序员来说。那么本文就说说为什么它在 Java 中用的少!

一般的一个东西用的少,可能有几种情况。一种是封装的不好,不好用;二是,不懂如何用?怎么用?什么场景用?三是,很少好到代码中有人用,所以我也就不用。LinkedList 就属于后两者,不知道什么场景用,以及很少有 Java 程序员去使用它!

在开始之前,我还是先简单的说一下 LinkedList 吧!

LinkedList

LinkedList 底层是基于双向链表实现的,也是实现了 List 接口,所以也拥有 List 的一些特点。实际上你从它的类名上也可以看出,它是一个链表,并且具有 List 的一些特性。

java LinkedList

LinkedList 和 ArrayList 有一些相反的特点。比如,ArrayList 插入删除慢,查找快;LinkedList 则相反,插入和删除都比较快,而删除则比较慢。这些特点也可以从它们各自的源码中看出(关于 ArrayList 可以先阅读我的这两篇文章《一个 ArrayList 就能让你面试到哭!》、《ArrayList 为什么要实现 RandomAccess?》):

public boolean add(E e) {
    linkLast(e);
    return true;
}
 /**
 * 业余草:www.xttblog.com
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

根据上面的代码,我们可以看出,LinkedList 每次插入都是移动指针,和 ArrayList 的拷贝数组来说效率要高上不少。

那么 LinkedList 为什么查找慢呢?同样的从它的源码中我们可以看出:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
// 业余草:www.xttblog.com
Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

从上面的代码中可以看出,它的查找不像 ArrayList 那样,可以根据下标索引去查找元素。

上述代码,利用了双向链表的特性,如果 index 离链表头比较近,就从节点头部遍历。否则就从节点尾部开始遍历。使用空间(双向链表)换取时间的方法加快查找。

node 会以O(n/2)的性能去获取一个结点。如果索引值大于链表大小的一半,那么将从尾结点开始遍历。这样的效率是非常低的,特别是当 index 越接近 size 的中间值时。

看到这里,有些人可能要问了,为什么我们不给 LinkedList 加上索引呢?比如:hash。

哎,你能想到的,Java 的设计者都能想到,所以 Java 中还有一些其他集合。这个我们以后有时间了,再来说说其他集合!

看到这里,也许有些人就明白了,为什么 Java 中 LinkedList 用的少了!

Java 中很多程序员,更多的是编写 CRUD 代码,遍历用的多,而 LinkedList 遍历速度相比 ArrayList 来说确实不占优。

那么 LinkedList 是不是就没有使用场景了呢?当然有,而且是必须要有,要不然 Java 设计它干嘛呢?

根据我在谷歌和百度上,得出一些结论。像 LRU 、操作系统的文件存储、路由 Trunk 、操作系统进程管理器等都是基于链表实现的。

链表相比数组还有一个特点就是它的内存地址不是连续的。还有网上有人实验得出,同样的数据,使用 LinkedList 存储比使用 ArrayList 存储需要占用更多的内存空间。

LinkedList 和 ArrayList 存储占用空间比

根据上面的讨论,如果让你使用 LinkedList 或 ArrayList 实现一个队列,是不是 LinkedList 好实现一些。因为队列是先进先出(FIFO)的,而且还容易实现插队(我是VIP)功能。

总之,LinkedList 适合经常有删除/插入操作而顺序遍历列表的场景。具体有哪些场景,应该在几个知名的开源框架源码中搜索一下,哪里有用到就可以了。鉴于时间关系,我就不去搜索查找了。大家自己动手去吧!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » Java 程序员(CRUD程序员)为什么很少使用 LinkedList?