上次我讲了ArrayList的使用，那么这次我就来讲讲他的“兄弟”，LinkedList。
相信大家都知道，LinkedList是通过链表来进行连接的。那么具体是如何进行的呢？我们还是通过源码来进行学习。
一、底层结构
大家可以看到，他定义了两个Node类型的结构，first和last。其中的注释说明，first永远都代表着第一个节点，而last会永远代表着最后一个节点。
接下来，我们看一下这个Node的实现是什么样的。
它是一个泛型，因为链表里可以包含任意的数据结构。它内部包含一个item，也就是当前的内容；一个next，也就是下一个节点；一个prev，也就是previous，是代表之前一个节点。这个结构说明，LinkedList中所有节点都是用一种链表的形式连接起来的。而且可以看出，这是一个双向链表，不但有next还有prev。
二、常用方法
2.1 add
LinkedList支持多种add方法，下面我一个个来进行分析
首先是常见的xxx.add（element）方法。
顾名思义，它是把一个新的内容节点采用linkLast方法加到最后面并且如果不报错就返回true。那么这个方法具体是怎么实现的呢？下面是源码。
这里有一个last类型，它是什么？他就是这篇文章最开始提到的那个最末尾的节点。我们先把这个值传入l，再新建一个节点，其中l作为它之前的节点（prev），e也就是当前的节点，null作为它之后的节点（next）。在完成这一步之后，把这个节点变成新的last。这一步其实非常好理解，相信大家不需要我画图也能够想明白。
这里最后还有一个判断，如果说这个节点是第一个节点，那么first也要被赋值，不然逻辑不合理；反之，就让前任的last和当前的节点连起来。如此，就形成了一个链表结构。
最后的size是list的size，和ArrayList类似，而这个modCount是什么呢？
在ArrayList,LinkedList,HashMap等等的内部实现增，删，改中我们总能看到modCount的身影，modCount字面意思就是修改次数，但为什么要记录modCount的修改次数呢？
大家发现一个公共特点没有，所有使用modCount属性的全是线程不安全的，这是为什么呢？说明这个玩意肯定和线程安全有关系喽，那有什么关系呢？
简单的说，在一个迭代器初始的时候会赋予它调用这个迭代器的对象的mCount，如何在迭代器遍历的过程中，一旦发现这个对象的mcount和迭代器中存储的mcount不一样那就抛异常。具体通过调用这个checkForComodification来实现。
好的，下面是这个的完整解释
Fail-Fast 机制
我们知道 java.util.LinkedList 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了LinkedList，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount域，modCount顾名思义就是修改次数，对LinkedList内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断 modCount 和expectedModCount是否相等，如果不相等就表示已经有其他线程修改了LinkedList。
所以在这里和大家建议，当大家遍历那些非线程安全的数据结构时，尽量使用迭代器。
然后是是xxx.add（index, element）方法。
其实也很好理解，如果设置的index刚好是当前的目录就会直接插入到最后，不然就是插入到指定的index位置。
linkBefore方法如下
首先，我们让一个pred为指定index之前的链表位置；在新建一个newNode，内容是指定的e，位置处于pred和succ中间。完成这一步后，我们肯定要把他们连接起来，所以我们让succ之前连接上newNode。最后还是一部判断，如果说我们插入的是第二个值（之前仅有一个succ）就会让newNode成为第一个；不然就把pred后面连接上newNode。有人会问，如果说我们插入之前是空怎么办呢？其实是不可能的，根据之前的checkPositionIndex方法，index的值一定是小于等于当前的size的。如果等于则进入linkLast方法，而进入linkBefore方法的时候index一定小于size。也就意味着，size至少为1。
2.2 remove
直接根据index删除
首先我们还是要检查index小于等于size。然后返回unlink方法，入参是一个node方法。大家也许会好奇这个node方法是啥样的，所以我们先讲一下这个node。
这个代码中进行了一个判断，如果说我们当前的index小于size的一半，就从前往后找到对应的节点；不然，我们就从后往前找到对应的节点。也就是说，这个方法就是帮助我们找到对应index下的链表节点的。
言归正传，我们看一下这个unlink方法的实现。
这个代码相信大家都看的懂，其实就是进行了一头一尾的判断。如果是第一个，那么我们需要让这个first变成原来的第二个；不然，就需要把这个节点之前的节点的next变成原来这个节点的后一个。这样一来，从前往后的逻辑就成立了。然后同理可以进行从后往前的连接。最后我们把这个节点的内容置为null，size-1，并且让modCount增加。
根据内容删除
这里是使用了一个object来作为入参，因为我们不知道这个list里具体会装载什么类型的数据。因为null无法使用equals方法，所以需要单独拿出来进行判断。具体的逻辑其实和之前是一样的，不过从前往后一旦找到一个就会直接返回并返回true，也就是只会删除第一个出现的对应的数据。
三、和ArrayList的区别
相信看到这个双向链表的结构,大家都会明白,我们可以直接从后往前操作这个list了。比如addLast，removeLast等方法就说明了这点
get方法中，ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快（O1）。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端（node方法）（On）。对LinkedList而言，访问列表中的某个指定元素没有更快的方法了
但在某些情况下LinkedList的表现要优于ArrayList，有些算法在LinkedList中实现时效率更高。比方说，利用Collections.reverse方法对列表进行反转时，其性能就要好些。当要对list进行大量的插入和删除操作时，LinkedList也是一个较好的选择。
今天一个同事问我，ArrayList和LinkedList谁更加消耗空间？我当时脱口而出LinkedList，因为想着他是链表要进行连接。但是仔细一想，ArrayList存在一个内容扩充的机制（详情可以看https://91jkys.yuque.com/trt71o/snfgpf/gahgkv），所以在大多数情况下都是会消耗更多的空间的。简而言之，ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
萌新手打，有问题请指正。
