目录
前言
linkedList是使用的双向链表，今天就来研究一下；我使用的jdk1.8；
正文
LinkedList使用的数据结构如上图，图中的箭头是指向的节点，不是指向节点中的数据；
成员变量
size表明LinkedList中存储数据的量；- 指向第一个节点；
- 指向最后一个节点；
private static class Node{ // 节点存储的数据 E item; // 指向下一个节点 Node next; // 指向上一个节点 Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
这个类是LinkedList中定义的静态内部类，数据的增删查改都是用的这个数据结构，还是比较重要的
构造方法
因为LinkedList使用的是双向链表，所以不用专门去写一个扩容的方法，就不用担心动态扩容的问题了；LinkedList有两种构造方法；
- 第一种：
public LinkedList() {} 直接new一个；
- 第二种：
public LinkedList(Collection c) { this(); addAll(c);} 这种方法还是使用的第一种的构造方法，然后再调用其中的方法将数据填充进LinkedList；
常用方法
主要写增删查改的方法；
添加
添加元素有六种方法，这里直选其中两个进行研究
直接添加元素，就是将数据添加到末尾
public boolean add(E e) { linkLast(e); return true; } linkLast方法：
/** * Links e as last element. */ void linkLast(E e) { //1 final Node l = last; //2 final Node newNode = new Node<>(l, e, null); //3 last = newNode; //4 if (l == null) first = newNode; else l.next = newNode; //5 size++; modCount++; } 感觉注释写到代码中太拥挤了，就提出来单独写了；流程说明如下 ：
- 用 l 来替换最后一个节点的值；
- 构造新节点，上一个节点指向l，存储添加的e数据，下一个指向null；
- 尾节点变为新建的节点；
- 如果尾节点为空，第一个节点也等于新建节点,反之 l 指向新节点；
- 数量自加1；
外边调用add(E e)方法，实际上是调用的linkLast(E e)方法，从方法名可以看出直接将添加的数据放到了尾节点；
添加元素到指定位置
public void add(int index, E element) { // 1 checkPositionIndex(index); // 2 if (index == size) linkLast(element); // 3 else linkBefore(element, node(index)); } - 检查index是否越界；
- 如果index等于LinkedList的size的时候，直接将元素添加到尾节点；
- 如果不是，则通过node(int index)方法找到该位置的节点，并调用linkBefore方法将元素element添加到找到的节点之前
Node<E> node(int index)方法就是找到第index个元素节点,代码如下：
/** * Returns the (non-null) Node at the specified element index. */ Nodenode(int index) { // assert isElementIndex(index); // 1 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
- 如果index小于size的一半，则从开头开始查询，反之从尾节点向前开始查询
- 最后返回查找到的节点
- 这个方法在后面用得较多，可以多看一看
linkBefore(E e, Node<E> succ) 方法就是将元素e添加到节点succ之前，代码如下：
/** * Inserts element e before non-null Node succ. */ void linkBefore(E e, Nodesucc) { // assert succ != null; // 1 final Node pred = succ.prev; // 2 final Node newNode = new Node<>(pred, e, succ); // 3 succ.prev = newNode; // 4 if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
- 找到succ节点的上一个节点
pred - 构造一个新的节点
newNode，该节点的上个节点指向pred,存储节点e,下一个节点指向succ; succ的父节点指向新节点newNode;- 如果
pred节点为空，说明succ节点就是头结点，所以直接将第一个节点first变为新节点newNode,反之pred节点的下一个节点指向新节点newNode;
删除
删除节点有四个方法，这里悬着其中两个进行研究：
根据下标删除节点
代码如下：
public E remove(int index) { // 1 checkElementIndex(index); // 2 return unlink(node(index)); } - 检查
index是否越界 - 先调用
node方法找到节点，再调用unlink方法删除节点
unlink方法代码如下：
E unlink(Nodex) { // assert x != null; //1 final E element = x.item; //2 final Node next = x.next; //3 final Node prev = x.prev; //4 if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } //5 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } // 6 x.item = null; size--; modCount++; return element; }
- 找到该节点存储的数据
item; - 找到该节点指向的下一个节点
next; - 找到该节点的上一个节点
prev; - 判断该节点的父节点
prev是否是null，如果为null，说明该节点为头结点，则first变为该节点的下一个节点，反之不为null，则父节点prev的子节点指向next节点,然后清空该节点的prev元素 - 判断该节点的next是否为
null，即是否为尾节点，如果是尾节点，则last就等于prev，反之不为null，则next.prev就等于prev节点，清空该节点的next元素 - 清空该节点的
item元素
根据节点删除节点
代码如下：
public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } 首先判断对象o是否为null，如果为null，则遍历链表删除第一个item为null的节点，如果不为null，则遍历链表调用对象o的equals方法来和节点的item作比较，删除第一个比较为true的节点;
查找
查找就比较简单了
根据下标查找节点
代码如下：
public E get(int index) { //1 checkElementIndex(index); //2 return node(index).item; } - 调用
checkElementIndex检验index是否越界 - 调用
node方法找到节点，并返回该节点的item
修改
修改也比较简单
根据下标修改节点
代码如下：
public E set(int index, E element) { // 1 checkElementIndex(index); // 2 Node x = node(index); // 3 E oldVal = x.item; // 4 x.item = element; // 5 return oldVal; } - 检查
index是否越界； - 调用
node方法找到节点； - 获取该节点的
item值oldVal； - 用
element替换掉原来的值； - 返回修改前的值
oldVal；
其他方法
clear方法
遍历该链表，每个节点的元素清空，清空该链表；
代码如下：
public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node x = first; x != null; ) { Node next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } size方法
返回该链表中存储节点的数量
代码如下：
public int size() { return size; } indexOf方法
该方法是查找节点的下标位置；
代码如下：
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } 流程大概就是遍历链表，如果为null，则直接查找为null的节点，反之就调用equals方法来查找节点
最后
阅读的方法并不多，也许其他的没有阅读的方法并不简单，但是个人感觉LinkedList整体来说还是不难的，主要还是要理解链表的操作，这些理解了就差不多了；
总结
- LinkedList底层数据结构采用双向链表，所以内存空间并不一定是连续的；
- 可以存储null，可以存储重复值
- 有序的，按存储顺序排列
- 线程非安全的
相比于ArrayList
两者都是按存储顺序来排列的
两者都是线程非安全的
两者都可以存储重复元素，都可以存null
ArrayList使用的数组，LinkedList采用双向链表，所以相对于ArrayList寻址快，LinkedList寻址慢
两者在添加元素时，ArrayList底层采用数组，所以可以将元素直接存储进去，添加的元素需要新建(new)一个节点
当插入或删除一个元素时，ArrayList需要copy数组，会调用
Arrays.copyof()方法，而LinkedList是链表，则可以直接修改，而这个快慢考虑的因数就比较多了，例如：元素的位置，元素的大小等等；ArrayList是数组，所以到了一定数量就需要扩容，而LinkedList留不用担心扩容的问题