先看看，再喜欢，给自己一点时间思考。微信搜索【沉默王二】关注这位才华横溢的程序员。 这篇文章已经收录在GitHub github.com/itwanger,并且有一线厂商整理的面试问题，还有我的系列文章。 上一篇文章，入坑访问了ArrayList，朋友们反响不错，所以本文将继续入坑LinkedList。他们是亲兄弟，相爱相杀的那种，不离不弃的那种，细节这个那个的那种。 我明目张胆地告诉你一个好消息。我写过一本四万多字的Java小白手册。朋友们可以在微信官方账号回复《寂静之王二》后端“白色”获得免费下载链接。 如果你觉得很好，请转发给有需要的朋友，送他们玫瑰，还有余香。 刚开始学Java的时候，还挺疑惑的。有了ArrayList，为什么我还需要LinkedList？都是单子，不是很多吗？那时候真的很傻很天真。不知道有没有同款的朋友。 不知道两者的区别，也不知道在什么场景下要不要用ArrayList和LinkedList。 那么这篇文章就可以一脚把这种幼稚踢开。 与数组一样，LinkedList也是一种线性数据结构，但它不像数组那样将元素存储在连续的位置，而是通过引用相互链接。 LinkedList中的每个元素都可以称为一个节点，每个节点包含三项:元素本身、下一个元素的引用地址和上一个元素的引用地址。 是node链表类的私有静态内部类，其源代码如下:私有静态类node < E & gt{ E项；LinkedList。节点& ltE & gt接下来；LinkedList。节点& ltE & gtprev节点(LinkedList。节点& ltE & gtprev，E元素，LinkedList。节点& ltE & gtnext){ this . item = element；this.next = nextthis.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的双向链表，所以也可以作为stack、queue或dequeue来操作。 LinkedList实现了List接口，所以它可以排队。 LinkedList实现了dequee接口，因此它可以用作dequee。 在了解了LinkedList的一点理论知识之后，我们来看看如何使用LinkedList。 01.如何创建LinkedListLinkedList< 但是，LinkedList在创建时不能像ArrayList那样指定大小。 02.向LinkedList添加元素。您可以通过添加()方法向LinkedList添加元素:Linked List < String & gtlist = new LinkedList<。& gt();List.add(《寂静之王二》)；List.add("沉默王三")；List.add("沉默王四")；有兴趣的伙伴可以研究一下add()方法的源代码，该方法在添加元素时调用linkLast()方法。 void link last(E E){ final linked list。节点& ltE & gtl =最后；最终链接列表。节点& ltE & gtnewNode =新LinkedList。节点& lt& gt(l，e，null)；last = newNodeif(l = = null)first = new node；else l.next = newNodesize++；modcount++；}添加第一个元素时，last为null，创建一个新节点(next和prev都为null)，然后将新节点赋给last和first；添加第二个元素时，last是第一个节点，创建一个新节点(next为空，prev为第一个节点)，然后将last升级到新节点，first保持不变，第一个节点的next升级到第二个节点；等等 还可以通过addFirst()方法将元素增加到第一个位置；addLast()方法将元素添加到末尾；add(int index，E element)方法将一个元素添加到指定位置。 03.升级LinkedList中的元素。可以使用set()方法更改LinkedList中的元素，并且需要提供下标和新元素。 List.set(0，“无声王五”)；看一下set()方法的源代码:public eset (int index，ee element){ CheckElementIndex(index)；LinkedList。节点& ltE & gtx =节点(索引)；e old val = x . item；x.item = element返回oldVal}这个方法会先检查指定的下标是否可以越界，然后根据下标找到节点:linkedlist.node < E & gtnode(int index){//assert isElementIndex(index)；if(index & lt；(大小& gt& gt1)) { LinkedList。节点& ltE & gtx =第一；for(int I = 0；我& lt指数；i++)x = x . next；返回x；} else { LinkedList。节点& ltE & gtx =最后；for(int I = size-1；我& gt指数；I-)x = x . prev；返回x；} } node()方法会对下标进行初步判断。如果是接近末端，就从末端开始遍历，可以节省很多遍历时间。小伙伴们要擦亮眼睛，学会这个。 找到节点后，替换新值并返回旧值。 04.删除LinkedList中的元素。可以通过remove()方法删除指定位置的元素:list . remove(1)；这个方法调用unlink()方法来升级前后节点。 E unlink(LinkedList。节点& ltE & gtx) { //断言x！= null最终E元素= x . item；最终链接列表。节点& ltE & gtnext = x.next最终链接列表。节点& ltE & gtprev = x.previf(prev = = null){ first = next；} else { prev.next = nextx.prev = null} if(next = = null){ last = prev；} else { next.prev = prevx.next = null} x.item = null尺寸-；modcount++；返回元素；}还可以使用removeFirst()和removefirst()方法删除第一个和最后一个节点。 05.在LinkedList中查找元素。如果要寻找正序的元素，可以使用indexOf()方法；如果要以逆序查找元素，可以使用lastIndexOf()方法。 看看indexOf()方法的源代码:public int index of(object o){ int index = 0；if (o == null) { for (LinkedList。节点& ltE & gtx =第一；x！= nullx = x.next) { if (x.item == null)返回索引；index++；} } else { for (LinkedList。节点& ltE & gtx =第一；x！= nullx = x.next) { if (o.equals(x.item))返回索引；index++；} } return-1；}和ArrayList基本一样，需要遍历。如果要搜索的元素为空，则使用“= =”运算符避免引发空指针异常；否则，使用equals()方法进行比较。 另外，getFirst()方法用于获取第一个元素；getLast()方法用于获取最后一个元素；Poll()和pollFirst()方法用于删除和返回第一个元素(虽然两个方法名称不同，但方法体是相同的)；PollLast()方法用于删除并返回最后一个元素；peek()方法用于返回peekFirst元素，而不删除它。 6.最后，如果要自己实现一个链表，上面的添加、删除、检查的轮子方法一定是白嫖。不，我们必须向他们学习。 前面ArrayList提到过，随机访问一个元素的时间复杂度是O(1)，但是LinkedList稍微复杂一点。随着数据的倍增，时间消耗也倍增，由于循环遍历，时间复杂度为O(n)。 至于LinkedList在插入、添加和删除元素时是否比ArrayList快，这要看数据量和元素的位置。 不过理论上，因为不需要移动阵列，应该会更快更小。 但无论快不快，下一个都会带来答案，敬请期待，朋友们。 我是寂静王二代，一个拥有巨大价值却靠天赋维持生计的程序员。 注意力可以提高学习效率。别忘了三通。喜欢，收藏留言。我不会挑的。奥利给的。 注:如果对文章有任何疑问，请毫不留情地指正。 如果你觉得文章对你有帮助，欢迎你在微信搜索《寂静之王二》，第一时间阅读。如果回复“小白”，我肝里就有4万+字的Java小白手册2.0版。这篇文章已经被收录在GitHub github.com/itwanger,，欢迎你来star。