如果本文中有不正确的地方请指出
由于没有留言可以在公众号添加我的好友共同讨论。
目录
介绍
继承结构
属性
构造方法
添加元素
LinkedList 是线程不安全的,允许元素为null的双向链表。就这么多。
我们来看一下LinkedList的继承结构图:代码实现:
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.SerializableCloneable实现克隆
Serializable序列化
List 定义了一些集合类的方法
Deque双向队列接口(就是两端都可以进行增加删除操作)
注意一点LinkedList并没有实现RandomAccess所以随机访问是非常慢的。
元素个数
transient int size = 0;指向第一个节点的指针(注释直接就写着)
/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first;指向最后一个节点的指针
/** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;transient关键字的作用是保持变量不被序列化具体的百度。
不过我们注意到LinkedList是有Node类,这里的Node是一个内部类:
item存储的元素
next指向后置节点
prev指向前置节点
内部类同时包含了一个构造函数
其实LinkedList 集合就是由许多个 Node 对象一个连着一个组成手构成,可以看下方的图可以看上面的四个元素,分别就是四个Node对象,可以看到node1所指向的prev上一个节点是空也就是没有上节点,node4所指向的next节点为空也就是没有下一个节点。
LinkedList共有两个构造方法,一个是创建一个空的构造函数,一个是将已有的Collection添加到LinkedList中。
LinkedList有几种添加方法我们先从add()开始。
可以看到在调用Add方法首先校验一下索引是否合法,如果不合法就会抛出异常。
if (index == size) linkLast(element); else linkBefore(element, node(index));然后如果索引值等于size的值则直接调用linkLast插入到尾部节点。
void linkLast(E e) { //将l设为尾节点 final Node<E> l = last; //构造一个新节点,节点上一个节点引用指向尾节点l final Node<E> newNode = new Node<>(l, e, null); //将尾节点设为创建的新节点 last = newNode; //如果尾节点为空,表示原先链表为空 if (l == null) //将头节点设为新创建的节点(尾节点也是新创建的节点) first = newNode; else //将原来尾节点下一个节点的引用指向新节点 l.next = newNode; size++;//节点数加1 modCount++; }注意一下这里出现了modCount方法,和ArrayList中一样,iterator和listIterator方法返回的迭代器和列表迭代器实现使用。linkBefore:
void linkBefore(E e, Node<E> succ) { //将pred设为插入节点的上一个节点 final Node<E> pred = succ.prev; //将新节点的上引用设为pred,下引用设为succ final Node<E> newNode = new Node<>(pred, e, succ); //succ的上一个节点的引用设为新节点 succ.prev = newNode; //如果插入节点的上一个节点引用为空 if (pred == null) //新节点就是头节点 first = newNode; else //插入节点的下一个节点引用设为新节点 pred.next = newNode; size++; //同上 modCount++; }在LinkedList中有两个addAll方法一个是 addAll(Collection c)一个是addAll(int index, Collection c),其实源码如下:
现在开始分析源码:首先我们可以看到先调用了checkPositionIndex(index);方法来检查索引是否合法。然后将传进来的Collection转成Object数组
Object[] a = c.toArray();如果集合为空就直接返回false
if (numNew == 0) return false;如果插入的位置等于链表的长度就把新增加的元素放在尾部。
Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; }最后在循环要插入的元素。这里我们可以看到上面也有modCount。
addFirst是将元素插入到LinkedList的头部。如果现在的结构是下图的:addFirst执行的操作就是:红色是使用addFirst插入后的位置。一下是源码
调用了linkFirst方法。上面的操作时:
首先执行final Node f = first;将头节点赋值给 f
final Node newNode = new Node<>(null, e, f);将指定元素构造成一个新节点,此节点的指向下一个节点的引用为头节点
//将新节点设为头节点,那么原先的头节点 f 变为第二个节点 first = newNode; //如果第二个节点为空,也就是原先链表是空 if (f == null) //将这个新节点也设为尾节点(前面已经设为头节点了) last = newNode; else f.prev = newNode;//将原先的头节点的上一个节点指向新节点 size++;//节点数加1 modCount++;//和ArrayList中一样记录修改次数addLast是将元素插入到尾部如图(黄色元素):
黄色node是新增加。注意add也是把元素添加到尾部。我们来看一下源码:
这里看到addLast和add是调用的同一方法,这里就不在讲解。可以看上方的代码。
由于文章比较长分为两次更新。请关注我下一篇文章继续分析
原创不易,如果你喜欢本文或者对你有帮助就
请转发或者点个再看
推荐阅读
❖