Java数据结构学习，从源码角度彻底搞懂LinkedList

 edList，相对于ArrayList，大家可能平时使用 edList要少一些，其实有时候使用 edList比ArrayList效率高很多，当然，这得视情况而定。

本文将带大家深入 edList源码，分析其背后的实现原理，以便以后在合适的情况下进行使用。之前我所知道的 edList的知识：

edList底层是链表结构；

插入和删除比较快，查询则相对慢一些；

因为是链表结构，所以分配的空间不要求是连续的链表。

单链表：

一个节点中包含数据和下一个节点的指针(注意,是下一个节点的指针,而不是下一个节点数据的指针),尾节点没有下一个节点,所以指向null.访问某个节点只能从头节点开始查找,然后依次往后遍历.

单向循环链表：

单向循环链表比单链表多了一个尾节点的指针指向的是头结点.

双向链表：

链表的每个节点包含以下数据:上一个节点的指针,自己的数据,下一个节点的指针.尾节点没有下一个节点,所以指向null.这样的结构,比如我拿到链表中间的一个节点,即可以往前遍历,也可以往后遍历.

双向循环链表：

双向循环链表的尾节点的下一个节点是头结点,头节点的上一个节点是尾节点.

edList的继承关系：

源码中的定义：

AbstractSequentialList这个类提供了List的一个骨架实现接口，以尽量减少实现此接口所需的工作量由“顺序访问”数据存储（如链接列表）支持。对于随机访问数据（如数组），应使用AbstractList优先于此类。

实现了List接口,意味着 edList元素是有序的,可以重复的,可以有null元素的集合.

Deque是Queue的子接口,Queue是一种队列形式,而Deque是双向队列,它支持从两个端点方向检索和插入元素.

实现了Cloneable接口,标识着可以它可以被复制.注意,ArrayList里面的clone()复制其实是浅复制(不知道此概念的赶快去查资料,这知识点非常重要).

实现了Serializable 标识着集合可被序列化。

erList 的源码解析

节点定义
Node是 edList的静态内部类.

为什么是静态内部类?我觉得可能原因如下:普通内部类会有外部类的强引用,而静态内部类就没有.有外部类的强引用的话,很容易造成内存泄漏,写成静态内部类可以避免这种情况的发生.

成员变量
看构造方法之前先看看几个属性:

这里为什么要存在一个成员变量尾节点?我感觉是为了方便,比如查找相应索引处元素+插入元素到最后.查找相应索引处元素时,先判断索引是在前半段还是在后半段,如果是在后半段,那么直接从尾节点出发,从后往前进行查找,这样速度更快.在插入元素到最后时,可以直接通过尾节点方便的进行插入.

构造方法
下面是构造方法源码:

两个构造方法都比较简单,就是构造一个列表,其中的addAll()方法待会儿放到后面分析.

思考:为什么 edList没有提供public edList(int initialCapacity)这种构建指定大小列表的构造方式?

因为ArrayList有这种构造方法public ArrayList(int initialCapacity),ArrayList提供这种构造方法的好处在于在知道需要多大的空间的情况下,可以按需构造列表,无需浪费多余的空间和不必要的生成新数组的操作.而 edList可以很轻松动态的增加元素(O(1)),所以没必要一开始就构造一个有很多元素的列表,到时需要的时候再按需加上去就行了.

添加元素

add(E e)
方法作用:将e添加到链表末尾,返回是否添加成功。

大体思路:

构建一个新的节点，将该新节点作为新的尾节点.如果是空链表插入第一个元素,那么头结点=尾节点=新节点；如果不是,那么将之前的尾节点指向新节点.增加链表长度。

小细节

boolean add(E e)添加成功返回true,添加失败返回false.我们在代码中没有看到有返回false的情况啊,直接在代码中写了个返回true,什么判断条件都没有,仔细想想,分配内存空间不是必须是连续的,所以只要是还能给它分配空间,就不会添加失败.当空间不够分配时(内存溢出),会抛出OutOfMemory.

addLast(E e)

方法作用:添加元素到末尾. 内部实现和add(E e)一样.

addFirst(E e)

方法作用:添加元素到链表头部.

大体思路:

构建一个新的节点，将该新节点作为新的头节点.如果是空链表插入第一个元素,那么头结点=尾节点=新节点;如果不是,那么将之前的头节点的prev指针指向新节点.增加链表长度.

push(E e)

方法作用:添加元素到链表头部 这里的意思比拟压栈.和pop(出栈:移除链表第一个元素)相反.内部实现是和addFirst()一样的.

offer(),offerFirst(E e),offerLast(E e)

方法作用:添加元素到链表头部. 内部实现其实就是add(e)

add(int index, E element)

方法作用:添加元素到指定位置,可能会抛出IndexOutOfBoundsException

大体思路:

首先判断一下插入的位置是在链表的最后还是在链表中间，如果是插入到链表末尾,那么将之前的尾节点指向新节点，如果是插入到链表中间，需要先找到链表中index索引处的节点，将新节点赋值为index处节点的前一个节点，将index处节点的前一个节点的next指针赋值为新节点.

addAll(int index, Collection)

大体思路:

将需要添加的集合转成数组a.判断需要插入的位置index是否等于链表长度size,如果相等则插入到链表最后;如果不相等,则插入到链表中间,还需要找到index处节点succ,方便拿到该节点的前后节点信息.记录index索引处节点的前一个节点pred,循环将集合中所有元素连接到pred的后面将集合最后一个元素的next指针指向succ,将succ的prev指针指向集合的最后一个元素

删除元素
remove(),removeFirst()

方法作用: 移除链表第一个元素

大体思路:其实就是将第一个节点移除并置空,然后将第二个节点作为头节点.思路还是非常清晰的,主要是对细节的处理.

remove(int index)

方法作用:移除指定位置元素

大体思路:

首先找到index索引处的节点(这样就可以方便的获取该节点的前后节点),记为x.记录x的前(prev)后(next)节点.将x的前一个节点prev节点的next指针指向next,将x节点的后一个节点的prev指针指向prev节点.将x节点置空,链表长度-1.

remove( o)

方法作用:从此链表中删除第一次出现的指定元素o

大体思路:

首先判断入参是否为null，如果为null,那么循环遍历链表,从头节点开始往后查找,找到第一个节点的数据值为null的,直接删除该节点.如果非null,那么循环遍历链表,从头节点开始往后查找,找到第一个节点的数据值为o的,直接删除该节点.这里的循环遍历链表的代码,我觉得还是比较通用的,从头节点开始,通过不断的将x赋值为下一个元素,直到遍历到为null的地方结束,这样就完美的遍历完了链表所有节点.

removeFirstOccurrence( o)

方法作用:从此链表中删除第一次出现的指定元素o. 内部其实就是上面的remove(o);

removeLast()

方法作用:移除最后一个元素并返回

大体思路:

判断链表是否有节点, 没有节点直接抛错误….首先找到倒数第二个节点(可能没有哈,没有的话,说明链表只有一个节点)prev，然后将尾节点置空,prev的next指针指向null。

removeLastOccurrence( o)

方法作用:从此链表中删除最后一次出现的指定元素o.

实现:其实和上面的remove(o)是一样的,只不过这里遍历时是从尾节点开始往前查找的.

poll()

方法作用:获取第一个元素的同时删除第一个元素,当链表无节点时,不会报错. 这里的un First()上面已分析过.

pop()

方法作用:获取第一个元素的同时删除第一个元素,当链表无节点时,会报错.

修改元素
set(int index, E element)

方法作用:设置index处节点数据值为element

大体思路:非常简单,就是首先找到index处节点,替换该节点数据值

查询元素
element()

方法作用:获取链表第一个元素. 方法比较简单,就是将链表头节点数据值进行返回

get(int index)

方法作用:获取指定索引处元素. 方法比较简单,就是通过node(index)找到index索引处节点,然后返回其数据值

getFirst()

方法作用:获取链表第一个元素. 非常简单,就是将first的数据值返回

getLast()

方法作用:获取链表最后一个元素. 非常简单,就是将last的数据值返回

通过listIterator()遍历 这也是查询的一种,哈哈

我们先来看看listIterator(int index)方法,就是new了一个ListItr进行返回.ListItr是 edList的内部类.

接下来,我们看看这个内部类:

这里的ListIterator有点强，ListIterator只能用于List及其子类型。有add()方法,可以往链表中添加对象，可以通过hasNext()和next()往后顺序遍历,也可以通过hasPrevious()和previous()实现往前遍历，可以通过nextIndex()和previousIndex()返回当前索引处的位置，可以通过set()实现当前遍历对象的修改。

总结

下面我们来总结一下 edList的关键点

底层是双向链表存储数据,并且记录了头节点和尾节点

添加元素非常快,如果是添加到头部和尾部的话更快,因为已经记录了头节点和尾节点,只需要链接一下就行了. 如果是添加到链表的中间部分的话,那么多一步操作,需要先找到添加索引处的元素(因为需要链接到这里),才能进行添加.

遍历的时候,建议采用forEach()进行遍历,这样可以在每次获取下一个元素时都非常轻松(next = next.next;). 然后如果是通过fori和get(i)的方式进行遍历的话,效率是极低的,每次get(i)都需要从最前面(或者最后面)开始往后查找i索引处的元素,效率很低.

删除也是非常快,只需要改动一下指针就行了,代价很小.

如果有正在学java的程序员，可来我们的java技术学习扣qun哦：59789，1510里面免费送java的视频系统教程！