前面一篇博客，写了关于ArrayList的源码分析，发现对于ArrayList，其内部是数组结构，在查询和遍历的时候效率较高，而在增加元素、删除的时候效率就比较慢了。
那么对于我们常用的另外一个List，LinkedList内部结构是什么样子的呢？
直接开始上代码：
一、LinkedList内部结构：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { //起始端值 transient Node<E> first; //尾端值 transient Node<E> last; //构造函数 public LinkedList() { } //node 一个匿名内部类，这其实就是LinkList里面的最小元素 //三个属性 当前对象 前面一个对象 后面一个对象 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; } } }
由一个个的Node节点连接起来，Node节点通过其prev和next属性，在寻找前面借点和后面借点是什么，头节点和尾部节点分别是first和last
二、对ListLinked内部元素的操作
1、获取元素
(1)getFirst()/getLast()
transient Node<E> first; transient Node<E> last; 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; } } //获取第一个元素 public E getFirst() { //第一个元素赋值给f final Node<E> f = first; //判断非空 if (f == null) throw new NoSuchElementException(); //返回元素 return f.item; } public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
查询获取首个元素和最后一个元素，直接获取first和last，效率很高。
（2）get（index）
//根据下角标获取元素 public E get(int index) { //检查下角标范围 checkElementIndex(index); //执行node（index）得到下角标为index的元素 return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); //判断index在前面一半还是后面一半 if (index < (size >> 1)) { //从第一个值开始遍历 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; //遍历结束，到达第index个值 return x; } else { //从last开始遍历 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
get（index），需要从first或者last一一遍历，并且需要计数，知道到达需要拿到index的元素，所以效率很低。
2、设置元素值
//设置下角标index值 public E set(int index, E element) { //检查index范围 checkElementIndex(index); //获取index Node<E> x = node(index); //记录原来的值 E oldVal = x.item; //设置新值 x.item = element; //返回原来的值 return oldVal; } //通过遍历获取index下角标元素 Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
set（index），需要先取得index下角标的元素，然后再将Node的item属性设置为新值，效率比较低下。
3、add(index,element)
public void add(int index, E element) { //检查index位置 checkPositionIndex(index); if (index == size) //放在最后 linkLast(element); else //其余，传入index位置元素和新元素 linkBefore(element, node(index)); } //传入index位置元素和新元素， void linkBefore(E e, Node<E> succ) { // assert succ != null; //愿index元素前面的Node final Node<E> pred = succ.prev; //新元素 前面的值为原index元素前面的值，后面为原index元素 final Node<E> newNode = new Node<>(pred, e, succ); //原index元素，前面值更新为插入值 succ.prev = newNode; if (pred == null) //判断新插入元素，前面值是否为空，如果是空则说明是第一个元素 first = newNode; else //设置前面值的对应next为新增值 pred.next = newNode; //添加大小 size++; //修改次数更新 modCount++; }
新增元素，还是比较方便的，最多只要动三个元素调整pre和next就可以，还是比较效率的。
其余的，比如删除等等，跟add类似，效率都比较高。