java中LinkedList怎么用

这篇文章主要为大家展示了“java中LinkedList怎么用”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“java中LinkedList怎么用”这篇文章吧。

与ArrayList一样，我们同样先从LinkedList的构造器分析，LinkedList只有两个构造器，下面我们开始上源码分析。

public LinkedList()

源码如下：

从源码可以看出，LinkedList的默认构造器相当简单，什么都没有做。

public LinkedList(Collection<? extends E> c)

这个构造器的源码如下：

可以看出这个构造器调用了一下默认构造器，然后调用了addAll方法，也是相当简单的实现。

下面开始分析LinkedList的实现，而LinkedList作为经典的链表实现，我们先简单介绍一下链表。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构（ArrayList属于线性表顺序结构），操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表顺序结构相应的时间复杂度则是O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

关于链表的介绍完毕（偷了个懒，百度百科copy的），下面正式开始介绍LinkedList。

private static class Node<E> 

首先是介绍一个Node<E>类，Node作为LinkedList里边存储的基本元素（节点），本身结构很简单，Node的定义如下：

其中有三个变量，一个是item，存储实际节点数据，一个是next，存储当前节点的下一个节点，一个prev，存储当前节点的上一个节点，由该Node很容易可以看出来，LinkedList是一个链状的表（这不废话嘛~）。Node只提供一种构造器，接收参数分别为该Node的前一个Node，该Node实际存放的数据，该Node的下一个Node。

public boolean add(E e)

这是List基本的方法之一，LinkedList该方法的源码如下：

可以看到该方法调用了一下linkLast方法，然后固定返回了一个true，非常简单，linkLast方法稍后会介绍。

public boolean remove(Object o)

该方法也是List基本方法之一，从链表中删除。源码如下：

可以看到跟ArrayList一样，首先判断o是不是null，然后遍历，查出来指定节点后调用unlink方法删除，同样很简单，unlink方法会在稍后介绍。

void linkLast(E e)

该方法在调用add方法时被调用了，下面开始介绍该方法。源码如下：

首先声明一个Node l等于last，该last定义在LinkedList中，表示当前链表的最后一个元素，然后new出来一个新的Node，其中该Node的前一个Node指定为原链表的最后一个，同时该Node的下一个Node为null（因为该Node是添加到了链表的末尾，后边已经没有元素了）。然后将链表自己维护的最后一个节点last更新为新加入的节点，判断原来的最后一个节点是否为null：

1、如果为null说明添加该节点时原链表为空链表（只有空链表才会没有first和last），上边已经将该链表的最后一个元素更新为新节点，下一行将该链表的第一个元素也更新为这个新节点，

2、如果不为null说明原链表不为空，只需将原链表的最后一个节点的下一个节点指向新节点即可。

最后更新size和modCount（该值很多地方都有用，不过可以暂时不用关注）。

E unlink(Node<E> x)

该方法在remove（Object o）的时候用到了，下面说说这个方法的实现，源码如下：

其中第一行获取element，同时还验证了x为非空（如果为空会抛出空指针异常NullPointException），然后取出要删除的节点的前一个节点的指针prev和后一个节点的指针next，然后判断前一个节点是否为null：

1、如果为null说明要删除的节点是链表的第一个节点，删除后需要将第二个节点也就是该节点的后一个节点next设置为首节点first；

2、如果不为null那么将该节点的前一个节点prev的下一个节点更新为该节点的下一个节点next，同时将该节点对prev的引用删除（设置为null）。

判断完prev后对next也需要判断，逻辑与prev差不多，就不再多说了。

以上是“java中LinkedList怎么用”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！