Java集合框架----LinkedList源码

少年阿涛 2020-05-28

LinkedList的源码分析

LinkedList的数据结是双向链表,因为是链表结构,所以LinkedList更加适用于增删频繁而查询修改不频繁的场景,其适用场景和ArrayList有一些相反的。

LinkedList的结构

1、实现了List接口:可以使用List接口中的所有方法。
2、实现了Cloneable接口,因此LinkedList支持克隆,但是只支持浅克隆,在LinkedList类中,其中的内部类Node并没有被克隆,只是调用了Object类中的clone方法进行可克隆。
3、实现了Serializable接口,因此LinkedList支持可序列化。
4、实现了Deque接口,实现了Deque的可选操作。
5、继承了AbstractSequentialList抽象类,在遍历的时候,推荐使用迭代器进行遍历。

LinkedList中的源码解释:

一、LinkedList源码的核心组成:用来存储数据的结点,在LinkedList中设计成了内部类

/**
    存储数据的内部类,用于创建结点
*/
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    //内部类构造方法,传入参数前结点,要添加的元素和后结点
    Node(Node<E> prev,E element,Node<E> next){
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

一、字段

1、int size = 0:记录LinkedList集合容器中的实际存储的元素个数
2、Node<E> first:记录双向链表中的头结点
3、Node<E> last:记录双向链表中的尾结点

二、构造方法

LinkedList的构造方法只提供了两个,和ArrayList相比,没有初始化容量的构造方法,这主要是因为ArrayList是数组,传入初始容量是为了创建一个具有初始长度的数组,而LinkedList是链表结构,每次新增都是在原有结点后面链接上,因此没有初始容量得构造函数

1、无参构造

/**
无参构造方法
*/
public LinkedList(){}
/**
有参构造方法:将一个容器作为参数传入
*/
public LinkedList(Collection&lt;? extends E&gt; c){
//首先调用无参构造函数
this();
//然后调用addAll(c);将传入的参数集合中元素全部添加倒新创建的LinkedList容器中
addAll(c);
}

三、LinkedList常用方法实现

1、添加元素

1) 添加单个元素:add(E e)

/**
添加的方法
*/
public boolean add(E e){
//调用添加在最后的方法
linkLast(e);
return true;
}
//添加在最后的方法
void linkLast(E e){
//要将添加的e元素添加在最后,就先记录原来的last元素,指向给l
final Node&lt;E&gt; l = last;
//新建一个结点,将e元素封装进去,前结点为l,元素为e,后元素没有为null
final Node&lt;E&gt; newNode = new Node&lt;&gt;(l,e,null);
//将新结点设置为最后结点
last = newNode;
//判断原尾结点l是否尾null
if(l == null){
//如果为null,则说明还没有元素,则新结点就为头结点
first = newNode;
}else{
//否则将原尾阶段l的next指向新结点
l.next = newNode;
}
//实际元素个数增加1
size++;
//操作次数加1
modCount++;
}

2)在尾部添加一个元素

/**
在链表的尾部添加一个元素
*/
public void addLast(E e){
//直接调用在尾部添元素的方法linkLast(E e),源码在上面已经描述,不再重复。
linkLast(E e);
}

3)在第一个位置添加元素

/**
在LinkedList容器中第一个位置添加元素
*/
public void addFirst(E e){
//直接调用linkFirst(e);
linkFirst(e);
}
//在第一个位置添加元素的方法
private void linkFirst(E e){
//记录原头元素
final Node&lt;E&gt; f = first;
//新建一个结点,前元素为null,next指向原头元素f
final Node&lt;E&gt; newNode = new Node&lt;&gt;(null,e,f);
//将头结点设置为newNode
first = newNode;
//判断原头结点f是否为null,
if(f == null){
//如果为null,则头结点和尾结点都应该是newNode
last = newNode;
}else{
//否则原头结点的前结点设置尾newNode
f.prev = newNode;
}
//实际元素个数增加1;
size++;
//操作次数增加1
modCount++;
}

4)在指定索引出添加元素

/**
在指定索引出的位置添加元素
*/
public void add(int index,E element){
//判断传入的索引参数是否合法
checkPositionIndex(index);
//判断传入的索引index是否是最后一个位置,和size比较即可
if(index == size){
//直接将元素添加在尾部
linkLast(element);
}else{
//否则添加在指定索引位置
linkBefore(element,node(index));
}
}
//在执行索引位置添加元素的方法,在非空的succ结点之前添加元素。
void linkBefore(E element,Node&lt;E&gt; succ){
//声明一个结点,暂时记录succ结点的前结点,因为新结点需要添加在succ的前面
final Node&lt;E&gt; pred = succ.prev;
//新建一个结点,并且新结点的前指向pred,后结点指向当前结点succ
final Node&lt;E&gt; newNode = new Node&lt;E&gt;(prev,element,succ);
//判断succ指向的原前结点pred是否为空
if(pred == null){
//如果为空,则说明前面没有元素,那新结点就为头结点
first = newNode;
}else{
//否则记录的succ原前结点pred的next指向新结点newNode即可
pred.next = newNode;
}
//实际元素个数增加1
size++;
//实际操作次数增加1
modCount++:
}
//根据传入索引计算要插入位置的结点元素
Node&lt;E&gt; node(int index){
//在LinkedList集合容器中,对遍历元素进行了优化,判断传入的index索引是靠近尾结点还是头结点位置
if(index &lt; (size &gt;&gt;1)){
//从头结点开始遍历,一直遍历到index指定索引处
Node&lt;E&gt; x = first;
for(int i = 0;i &lt; index;i++){
x = x.next;
}
return x;
}else{
//从尾部开始往前遍历
Node&lt;E&gt; x = last;
for(int i = size - 1;i &gt; index;i--){
x = x.prev;
}
return x;
}
}

2、删除的方法
1)删除LinkedList集合容器中的指定元素

public boolean remove(Object obj){
//判断传入的元素obj是否尾null
if(obj == null){
//遍历LinkList中的所有结点
for(Node&lt;E&gt; x = first;x!= null;x = x.next){
//如果x结点的元素值等于null,则删除该结点
if(x.item == null){
//删除结点
unlink(x);
return true;
}
}
}else{
//否则说明传入的元素obj的值不为null
for(Node&lt;E&gt; x = first;x != null;x = x.next){
//是否为null的差别在这里
if(obj.equals(x.item)){
//删除该结点
unlink(x);
return true;
}
}
}
//否则返回false
return false;
}
//删除结点的方法
E unlink(Node&lt;E&gt; x){
//定义一个变量来记录当前要删除结点的值,因为最后要返回去
final E element = x.item;
//定义一个结点变量来记录该结点的后结点
final Node&lt;E&gt; next = x.next;
//定义一个结点变量,用来记录该结点的前结点
final Node&lt;E&gt; prev = x.prev;
//判断待删除结点x的前结点是否为null,如果为null,则待删结点的后结点next设置为头结点
if(prev == null){
first = next; 
}else{
//否则将待删结点x的前结点和后结点连接起来
prev.next = next;
//并将待删结点x的前结点置为null,相当于断开连接
x.prev = null;
}
//判断待删除结点的next结点是否为null
if(next == null){
//直接将待删除结点设置为尾结点即可
last = prev;
}else{
//否则待删结点x的后结点的prev指向待删结点的前结点
next.prev = prev;
x.next = null;
}
//将待删结点的元素值设置为null
x.item = null;
//实际长度减少1
size--;
//操作增加1
modCount++;
//返回待删结点的原元素值
return element;
}

2)清空LinkedList集合框架中的所有元素

/**
*   清空LinkedList集合中的所有元素
*/
public void clear(){
//遍历LinkedList集合容器中的所有元素,将所有的结点都置为null
for(Node&lt;E&gt; x = first;x != null){
Node&lt;E&gt; next = x.next();
x.item = null;
x.next = null;
x.prev = null;
}
//将头结点和尾结点全部置为null
first = last = null;
//实际元素设置为0
size = 0;
//操作次数增加1
modCount++:
}

3)删除指定索引位置的结点

/**
*   根据传入的索引位置删除元素
*/
public E remove(int index){
//校验用户名是否合法
checkElementIndex(index);
//直接返回删除的方法,上面已经介绍,就不再重复分析
return unlink(node(index));
}

3、查询元素
1)根据索引查询所在位置的元素

/**
*   根据索引位置查询该位置的元素值
*/
public E get(int index){
//校验用户名是否合法
checkElementIndex(index);
//返回结点的元素值,其中使用到node(index)上面已经介绍,不再重复介绍。
return node(index).item;
}

4、修改结点元素
1)根据索引位置设置元素值

/**
*  根据索引值设置索引值
*/
public E set(int index,E element){
//校验索引位置是否合法
checkElementIndex(index);
//根据索引获取该结点
Node&lt;E&gt; x = node(index);
//定义变量用来记录原结点的元素值
E oldVol = x.item;
//用传入的元素值替换原来的元素值
x.item = element;
//将原结点的元素值返回
return oldVol;
}

相关推荐

TiDBPingCAP / 0评论 2020-07-29