多语言展示
当前在线:1044今日阅读:26今日分享:39

java中LinkedList源码分析

LinkedList也是我们开发中常用到的集合类,它是基于链表实现的。其允许存储的元素为null,允许重复元素,且是有序非线程安全的。以下通过其源码,简单介绍下LinkedList。
工具/原料
1

java

2

jdk1.8,IntelliJ IDEA

方法/步骤
1

首先,找到LinkedList的存储数据的地方。通过参数,我们可以发现一个Node对象,查看Node对象,发现其为LinkedList中的一个内部类,其中定义的item即为存储数据。

2

我们已经知道LinkedList是基于双向链表来实现的,那么它一定有一个基本的存储单元,通过上面的Node初始化,我们可以用以下图形模拟LinkedList的进本存储单元。初始化有三个数据,指向上一个节点和指向下一个节点的引用,以及真实的存储数据。

3

添加元素:add(E e),按顺序进行添加。创建新节点,将上个节点的last地址作为新建节点的first地址。

4

图形说明add原理。第一个元素的添加,此时最后一个节点和最初节点都为null,因此第一个节点既是既是first也是last。指向该节点的引用假设为0x。

5

在添加第二个元素时,此时last为尾结点的引用0x,此时新建的第二个节点引用假设为0x,那么,新节点引用将赋值给l.next即第一个节点的next指针。

6

同理当第三个元素添加时,last的值已经变更为0x,其余按照上一步骤相同。这样,就实现了向LinkedList中添加元素。

8

删除元素:remove(int idex)可以看到,首先查看是否有该index,然后调用node方法,先去找到该index的node,再通过unlink方法将该node的item,pre和next指针都置空,让其等待gc回收,另外将前node的next指针指向后node的pre,将后node的pre指向前node的next。插入的程序刚好和remove相反,这里不多赘述。

9

这里做一个简单的流程图说明remove。

注意事项

LinkedList的遍历用for循环会非常慢,一般使用foreach的迭代遍历。

推荐信息