我们都知道，ArrayList和LinkedList2个是List接口最重要的2个实现；
上篇文章通过自己定义1个ArrayList的方式来分析了ArrayList的实现原理，
这篇我们也通过这个方式来分析下LinkedList的实现原理，并分析下ArrayList和LinkedList的区别；
LinkedList支持无参构造，并且在构造中可以什么 也不用做，我们直接进入他的增删改查方法来分析；
Node类
LinkedList的内部类
Node的作用我们之后再说，暂时知道他是LinkedList的一个内部类就可以；
成员变量
LinkedList中定义了个Node的变量，1个first，1个last;我们继续往下分析
LinkedList底层维护的是1个链表，所以我们简单下画图；
LinkedList的数据结构
LinkedList中的结构就是1个Node（节点），每个节点都包含1个prev 1个next和1个element,其中prev是指向上一个节点的指针，next是指向下1个节点的指针，element才是我们放进去的值；
因此我们就可以得出first的结构和last的结构为下图：
first为链表的第一个节点，所以他的prev为null,last为链表的最后1个节点，所以他的next为null，之后我们的逻辑中就以此为判断依据来区分节点是否为头（尾）节点
现在我们来看看
Add方法：
add方法是在集合的尾部增加1个元素，所以最重要的方法就是linkLast方法；
该方法的逻辑也很简单，就是将目前链表的最后1个元素，也就是last，赋给1个临时节点l，之后将这个临时节点l作为prev创建1个新节点，将此新节点设置为链表的最后1个节点，也就是last = newNode;
最后判断当前创建的是不是链表中 的第一个节点，如果是，则直接赋值给first,如果不是，则将新节点接入到旧链表的尾部(next节点指针)，完成1次元素的添加
上面说了是add方法在集合的尾部增加元素的情况，那下面接着分析下在具体位置如何插入1个元素
根据上面代码逻辑，如果是在尾部插入的话，直接走尾部插入的逻辑；
首先，先找到需要插入的位置的节点数据
找到需要插入位置的节点
我们可以将链表想象成如下图的结构：
假设集合中一共10个数据，当我们需要在链表的第三个位置也就是index = 2的位置插入数据时，我们首先就需要找到index = 2时候Node的数据；
链表一共10个数据，index = 2，位于链表的前半部分，所以可以从链表的头节点开始找；
循环遍历列表，first 的next指针指向的是Node2,Node2的next指针指向的Node3，此时我们只需要遍历2次就找到了index = 2对应的节点数据了；
如果此时index = 8，位于链表的后半部分，如果还从头结点开始寻找就显得效率很慢，这时候就可以转换下思路，从尾节点反向查找；
尾节点last的 prev指针指向的就是Node9，Node9的prev指针指向的就是Node8,只需要查找2此就能找到index = 8所对应的节点数据，大大提高了查找的效率；
以上就是node()的实现原理，现在得到了需要插入的Index的位置所对应的节点数据，我们继续看下是如何在 指定位置插入数据的；
还是以在Index为2插入1个数据为例来讲解。
可以由上图看到，如果要在index为2的位置插入新的节点，那原来的Node3就得往后移动；改动涉及到3个节点：Node2,Node3和newNode
Node2的next指针指向的节点由指向Node3改成newNode；
Node3的prev指针由指向Node2改成指向newNode;
newNode的prev指针指向的是Node2,next指针指向的是Node3
如果插入的位置是头节点，那很显然的prev是空的。则可以直接将新节点赋为头结点
newNode的创建
以上就在指定位置插入数据的具体实现细节
set和get方法的具体实现细节最主要的就node方法的细节，获取index位置的节点数据。参考上面的node的解析
remove方法
具体接着看unLink()方法的实现细节
同样是需要获取需要删除位置的节点数据
针对头节点，尾节点和中间节点参照下三图
删除的是中间节点
如果删除的是中间节点 Node3,那么收到牵连的就有3个节点：
Node2节点的next指针指向的由Node3--->Node4
Node4节点的prev指针指向由Node3--->Node2
Node3节点的prev指针指向由Node2--->null，next指针指向由Node4--->null；
删除的是头节点
如果删除的是头节点，则直接把Node2移到first节点上当做头节点，其他的都不需要改动
删除的是尾节点
如果删除的是尾节点，则直接把Node9移到last节点上当做链表的尾节点，其他也不需要改动
以上就LinkedList的基本实现原理；
网友评论