技术小菜比入坑 LinkedList,i 了 i 了

作者 : 开心源码 本文共4581个字,预计阅读时间需要12分钟 发布时间: 2022-05-13 共175人阅读

先看再点赞,给自己一点思考的时间,微信搜索【沉默王二】关注这个靠才华苟且的程序员。
本文 GitHub github.com/itwanger 已收录,里面还有一线大厂整理的面试题,以及我的系列文章。

上一篇入坑了 ArrayList,小伙伴们反响不错,那这篇就继续入坑 LinkedList,它俩算是亲密无间的兄弟,相爱相杀的那种,不离不弃的那种,详情了这个就必需详情那个的那种。

明目张胆地告诉大家一个好消息,我写了一份 4 万多字的 Java 小白手册,小伙伴们可以在「沉默王二」公众号后端回复「小白」获取免费下载链接。觉得不错的话,请随手转发给身边需要的小伙伴,赠人玫瑰,手有余香哈。

最开始学习 Java 的时候,我还挺纳闷的,有了 ArrayList,干嘛还要 LinkedList 啊,都是 List,不是很多余吗?当时真的很傻很天真,不知道有没有同款小伙伴。搞不懂两者之间的区别,什么场景下该用 ArrayList,什么场景下该用 LinkedList,傻傻分不清楚。那么这篇文章,可以一脚把这种天真踹走了。

和数组一样,LinkedList 也是一种线性数据结构,但它不像数组一样在连续的位置上存储元素,而是通过引用相互链接。

LinkedList 中的每一个元素都可以称之为节点(Node),每一个节点都包含三个项目:其一是元素本身,其二是指向下一个元素的引用地址,其三是指向上一个元素的引用地址。

Node 是 LinkedList 类的一个私有的静态内部类,其源码如下所示:

private static class Node<E> {    E item;    LinkedList.Node<E> next;    LinkedList.Node<E> prev;    Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {        this.item = element;        this.next = next;        this.prev = prev;    }}

LinkedList 看起来就像下面这个样子:

  • 第一个节点因为没有前一个节点,所以 prev 为 null;

  • 最后一个节点因为没有后一个节点,所以 next 为 null;

  • 这是一个双向链表,每一个节点都由三部分组成,前后节点和值。

那可能有些小伙伴就会和当初的我一样,好奇地问,“为什么要设计 LinkedList 呢?”假如能给 LinkedList 类的作者打个电话就好了,可惜没有他的联络方式。很遗憾,只能靠我来给大家解释一下了。

第一,数组的大小是固定的,即使是 ArrayList 可以自动扩容,但仍然会有肯定的限制:假如公告的大小不足,则需要扩容;假如公告的大小远远超出了实际的元素个数,又会造成内存的白费。虽然扩容的算法已经非常优雅,虽然内存已经绰绰有余。

第二,数组的元素需要连续的内存位置来存储其值。这就是 ArrayList 进行删除或者者插入元素的时候成本很高的真正起因,由于我们必需移动某些元素为新的元素留出空间,比方说:

现在有一个数组,10、12、15、20、4、5、100,假如需要在 12 的位置上插入一个值为 99 的元素,就必需得把 12 以后的元素往后移动,为 99 这个元素腾出位置。

删除是同样的道理,删除之后的所有元素都必需往前移动一次。

LinkedList 就摆脱了这种限制:

第一,LinkedList 允许内存进行动态分配,这就意味着内存分配是由编译器在运行时完成的,我们无需在 LinkedList 公告的时候指定大小。

第二,LinkedList 不需要在连续的位置上存储元素,由于节点可以通过引用指定下一个节点或者者前一个节点。也就是说,LinkedList 在插入和删除元素的时候代价很低,由于不需要移动其余元素,只要要升级前一个节点和后一个节点的引用地址就可。

LinkedList 类的层次结构如下图所示:

  • LinkedList 是一个继承自 AbstractSequentialList 的双向链表,因而它也可以被当作堆栈、队列或者双端队列进行操作。

  • LinkedList 实现了 List 接口,所以能对它进行队列操作。

  • LinkedList 实现了 Deque 接口,所以能将 LinkedList 当作双端队列使用。

明白了 LinkedList 的少量理论知识后,我们来看一下如何使用 LinkedList。

01、如何创立一个 LinkedList

LinkedList<String> list = new LinkedList<>();

和创立 ArrayList 一样,可以通过上面的语句来创立一个字符串类型的 LinkedList(通过尖括号来限定 LinkedList 中元素的类型,假如尝试增加其余类型的元素,将会产生编译错误)。

不过,LinkedList 无法在创立的时候像 ArrayList 那样指定大小。

02、向 LinkedList 中增加一个元素

可以通过 add() 方法向 LinkedList 中增加一个元素:

LinkedList<String> list = new LinkedList<>();list.add("沉默王二");list.add("沉默王三");list.add("沉默王四");

感兴趣的小伙伴可以研究一下 add() 方法的源码,它在增加元素的时候会调用 linkLast() 方法。

void linkLast(E e) {    final LinkedList.Node<E> l = last;    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);    last = newNode;    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}

增加第一个元素的时候,last 为 null,创立新的节点(next 和 prev 都为 null),而后再把新的节点赋值给 last 和 first;当增加第二个元素的时候,last 为第一个节点,创立新的节点(next 为 null,prev 为第一个节点),而后把 last 升级为新的节点,first 保持不变,第一个节点的 next 升级为第二个节点;以此类推。

还可以通过 addFirst() 方法将元素增加到第一位;addLast() 方法将元素增加到末尾;add(int index, E element) 方法将元素增加到指定的位置。

03、升级 LinkedList 中的元素

可以使用 set() 方法来更改 LinkedList 中的元素,需要提供下标和新元素。

list.set(0, "沉默王五");

来看一下 set() 方法的源码:

public E set(int index, E element) {    checkElementIndex(index);    LinkedList.Node<E> x = node(index);    E oldVal = x.item;    x.item = element;    return oldVal;}

该方法会先对指定的下标进行检查,看能否越界,而后根据下标查找节点:

LinkedList.Node<E> node(int index) {    // assert isElementIndex(index);    if (index < (size >> 1)) {        LinkedList.Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        LinkedList.Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

node() 方法会对下标进行一个初步的判断,假如靠近末端,则从最后开始遍历,这样能够节省不少遍历的时间,小伙伴们眼睛要睁大点了,这点要学。

找到节点后,再替换新值并返回旧值。

04、删除 LinkedList 中的元素

可以通过 remove() 方法删除指定位置上的元素:

 list.remove(1);

该方法会调用 unlink() 方法对前后节点进行升级。

E unlink(LinkedList.Node<E> x) {    // assert x != null;    final E element = x.item;    final LinkedList.Node<E> next = x.next;    final LinkedList.Node<E> prev = x.prev;    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }    x.item = null;    size--;    modCount++;    return element;}

还可以使用 removeFirst()removeLast() 方法删除第一个节点和最后一个节点。

05、查找 LinkedList 中的元素

假如要正序查找一个元素,可以使用 indexOf() 方法;假如要倒序查找一个元素,可以使用 lastIndexOf() 方法。

来看一下 indexOf() 方法的源码:

public int indexOf(Object o) {    int index = 0;    if (o == null) {        for (LinkedList.Node<E> x = first; x != null; x = x.next) {            if (x.item == null)                return index;            index++;        }    } else {        for (LinkedList.Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item))                return index;            index++;        }    }    return -1;}

基本上和 ArrayList 的大差不差,都需要遍历,假如要查找的元素为 null,则使用“==”操作符,可以避免抛出空指针异常;否则使用 equals() 方法进行比较。

另外,getFirst() 方法用于获取第一个元素;getLast() 方法用于获取最后一个元素;poll()pollFirst() 方法用于删除并返回第一个元素(两个方法虽然名字不同,但方法体是完全相同的);pollLast() 方法用于删除并返回最后一个元素;peekFirst() 方法用于返回但不删除第一个元素。

06、最后

假如要我们自己实现一个链表的话,上面这些增删改查的轮子方法是肯定要白嫖啊,不对,肯定要借鉴啊。

上一篇 ArrayList 中提到过,随机访问一个元素的时间复杂度为 O(1),但 LinkedList 要复杂少量,由于数据增大多少倍,耗时就增大多少倍,由于要循环遍历,所以时间复杂度为 O(n)。

至于 LinkedList 在插入、增加、删除元素的时候有没有比 ArrayList 更快,这要取决于数据量的大小,以及元素所在的位置。不过,从理论上来说,因为不需要移动数组,应该会更快少量。但究竟快不快,下一篇带来答案,小伙伴们敬请期待。


我是沉默王二,一枚有颜值却靠才华苟且的程序员。关注就可提升学习效率,别忘了三连啊,点赞、收藏、留言,我不挑,奥利给

注:假如文章有任何疑问,欢迎毫不留情地指正。

假如你觉得文章对你有些帮助欢迎微信搜索「沉默王二」第一时间阅读,回复「小白」更有我肝了 4 万+字的 Java 小白手册 2.0 版,本文 GitHub github.com/itwanger 已收录,欢迎 star。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 技术小菜比入坑 LinkedList,i 了 i 了

发表回复