LinkedList实现分析（二）——常用操作
上一篇文章LinkedList实现分析（一）介绍了LinkedList中的一些重要属性和构造方法，下面我们将详细介绍一下LinkedList提高的常用方法的实现原理
元素添加
add(E e)方法
往LinkedList添加元素，LinkedList提供了多重方式，首先介绍add方法，下面我们使用一个简单的实例代码来分析一下add方法的实现原理：
List<String> myList = new LinkedList();//1
myList.add("a"); //2
myList.add("b"); //3
myList.add("c"); //4
执行第一行代码后创建了一个空的myList对象，此时myList如下图所示：
myList.png
然后执行第2行代码myList.add("a")，把字符串"a"添加到myList中，通过debug方式进入add方法内部：
public boolean add(E e) {
linkLast(e);
return true;
}
add又调用linkLast方法，linkLast方法实现如下：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
在linkLast内部，此时e="a"。首先把last，此时myList是新创建的对象，last=null，赋值给一个临时变量 l，这里的做法是用来保存last的值，然后用元素e创建一个新的Node对象，这里是往myList的尾部添加元素，因此创建的Node节点的构造方法最后一个参数是null，而第一个参数表示的是插入元素e的前一个元素指针，因此需要传入l，因为在整个LinkedList中last属性表示的最后一个元素。当创建好包含e的newNode节点的时候，此时newNode就应该是myList的最后一个节点，也是第一个节点（l==null），因此把newNode赋值给last和first，然后把表示myList大学的size进行加一，最后对modCount加一，记录了修改次数。执行完第2行代码后，myList的状态入下图所示:
myList.png
当示例代码执行第3行代码的时,同样会执行linkLast，此时e=“b”。在进入linkLast方法的时候，last的值已经不在是null，而是刚刚创建的包含了“a”的Node节点对象，同样把last先用一个临时变量l保存起来，然后创建一个包含“b”的Node节点，这个时候该node节点的前一个节点是“a”所在的节点，因此构造函数 new Node<>(l, e, null)，把新创建的newNode作为整个myList的最后一个节点： last = newNode，而由于l不为null，也就是last不为null，所以需要把新创建的节点放到myList中最后一个节点的后面： l.next = newNode，最后修改size和modCount的值，完成“b”元素的添加。此时myList的状态如下图所示：
myList.png
然后示例代码执行到第4行，此时myList已经有2个node，根据上图可知last指向了“b”node，然创建“c”的node对象，让“c”的prev执行“b”，然后myList中的last指向“c”，“b”的next执行“c”，执行完后myList的状态如下图所示:
myList.png
add(int index, E element)
该方法是在指定的索引的位置插入一个元素，index值指定的索引位置，element是需要插入的元素信息。这里还是以一个示例为基础进行对 add(int index, E element) 源码的分析，示例代码如下：
List<String> myList = new LinkedList();//1
myList.add("a"); //2
myList.add(0,"b")//3
当示例代码执行完第2部的时候，myList的状态如下图所示：
myList.png
然后执行第3行代码，具体 add(int index, E element) 的源码如下：
public void add(int index, E element) {
checkPositionIndex(index);//index校验
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先是对传入的index进行位置校验，具体实现是要求index不能小于0，不能大于myList当前的大小。根据示例代码，执行到第3行的时候，此时size=1，index=0，因此程序执行linkBefore方法，linkBefore是第一参数是新添加的元素element，第二个参数表示element需要被添加到myList中哪个元素的后面。这里传入是位置索引，因此需要调用node(index)方法找到mylist中index对应的node对象，node方法实现如下：
Node<E> node(int 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;
}
这里源码中使用了一个技巧，通过判断传入的index与整个list的大小(size)的1/2进行比较，如果index<size/2，那么对myList进行正序遍历，如果index>=size/2，那么对myList进行倒序遍历。这里需要大家注意的是源码中使用<font color=red>右移操作获取size的1/2</font>，这个技巧希望大家可以掌握：
在java中，数字左移表示乘2，数字右移除2
由于当前myList的size=1，右移之后是0，index=0，因此执行else的语句，从last指向的node开始倒序遍历，此时myList只有一个index=0所指向的元素就是last的值，因此把last返回。node方法执行完之后，开始执行linkBefore方法：
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
linkBefore方法就是一个双向列表的插入操作，首先把succ的前驱节点prev保存到临时变量pred，使用传入的e（根据示例代码，此时e=“b”）创建一个新的Node对象：newNode，由于是在succ节点的前面插入新元素"b"，因此newNode的前驱点是之前succ节点的前驱节点，newNode的后节点就是succ节点本身：final Node<E> newNode = new Node<>(pred, e, succ)，此时myList的状态如下图所示：
image.png
然后执行 succ.prev = newNode，是把原来succ指向的前驱节点改成了newNode，因为newNode插入了succ节点前面，因此succ的prev就是newNode，指向完的myList状态如下：
image.png
然后是判断pred是否为null,在myList的当前状态中， succ.prev是null，pred也就是null，所以把first指向newNode，也就是在myList的头结点succ之前添加一个新元素newNode，即 first = newNode;然后对size和modCount加一，执行完最后myList的状态如下图:
image.png
addAll(Collection<? extends E> c)
下面介绍一下使用集合对象给LinkedList添加元素，addAll有两个重载方法：
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
在源码中，addAll(Collection<? extends E> c)实际是调用了addAll(int index, Collection<? extends E> c) :
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
因此这里只介绍后面一个addAll的实现:
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//下面的代码是查询需要插入位置的前驱和后继节点
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//把a中的元素创建为一个列表
//并且让pred指向a的最后一个节点
for (Object o : a) {
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//如果没有后继节点，那么c集合中最后一个节点就是
//整个list的最后节点
if (succ == null) {
last = pred;
} else {
//如果在list找到插入的前驱和后继节点
//把c中的最后一个节点的后继节点指向succ
//把后继节点的前驱节点指向c中的最后一个节点
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
addAll方法内部，首先还是判断index的值是否合法，然后对传入的Collection对象c进行验证， 接着在源码中定义了两个变量：
Node<E> pred, succ;
pred表示需要插入c的前驱节点，succ表示c的后继节点。当index=size表示是把c添加到LinkedList的尾部，因此执行succ=null和pred=last;否则调用 node(index)方法，找到后继节点succ，然后把当前后继节点的前驱节点赋值给pred。
找到所插入前驱和后继节点之后，开始循环遍历c，把c中的每一个元素创建一个Node对象，c中的前一个元素都是后一个元素的前驱节点，把c建立为一个链表。然后把c的链表插入的LinkedList中，具体见上面源码的注释，完成链表的连接操作只会，对size和modCount进行加1操作。
其他添加元素的方法
下面介绍一个往list头插入元素的方法：
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
//保存第一个元素
final Node<E> f = first;
//头插法，因此newNode的前驱节点是null，后继节点是f
final Node<E> newNode = new Node<>(null, e, f);
//让新创建节点当整个list的头节点
first = newNode;
if (f == null)
//如果f=null，表示当前list没有一个元素，因此需要给last=newNode
last = newNode;
else
//把之前的first接的前驱节点换成新创建的newNode
f.prev = newNode;
size++;
modCount++;
}
头插入的原理就是在整个list中，找到一个元素first，把first的前驱节点换成新插入的元素，然后把新传入元素的后继节点指向之前的头节点，具体实现见上面源码和注释
LinkedList提供了offer(E e)，offerFirst(E e)， offerLast(E e)，addFirst(E e) ，addLast(E e)，push(E e) 往list中添加一个元素的方法，这些方法的底层都是基于上面介绍的原理实现的：头插和尾插。这里就不多做说明。
获取元素
LinkedList获取元素提供多种方法：
//根据索引获取元素
public E get(int index)
//获取头元素
public E peek()
//获取头元素，并且把头元素从list中删除
public E poll()
//获取头元素，并且把头元素从list中删除
public E pop()
下面追个介绍这些方法的具体实现：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
由上面源码可知，get操作底层是调用的node方法，node方法参考上面的介绍。
下面是peek，peek操作是获取头元素，因此只需要获取到LinkedList的first所执行的元素就可以了。
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
下面介绍poll():
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
//保存f的具体值
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
//f的后继节点赋值给LinkedList的first
first = next;
//next==null表示要删除的节点是list的最后一个节点
if (next == null)
last = null;
else
//表示删除f之后的list列表中，头结点的prev应该为null，而之前
//prev是执行f的
next.prev = null;
size--;
modCount++;
return element;
}
由上面源码可知，当调用poll的时候，会把LinkedList的头元素返回，然后把头元素从LinkedList中删除。
下面看一下pop方法：
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
pop方法的底层也是调用unlinkFirst方法完成头结点的删除操作。
To Array的操作
LinkedList提供了两种方法完成list到数组的转换：
public Object[] toArray()
public <T> T[] toArray(T[] a)
第一个方法，是把list转为Object类型的数组，具体是实现如下：
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
该方法的实现原理比较简单，首先创建一个大小与list相同的object类型数组，然后从头到尾遍历list的元素，把每个元素放到创建的数组中，因为数组对象是Object类型，因此list中的任何元素都可以直接放入到数组中，最后把数组返回。
在T[] toArray(T[] a) 方法中，需要传递一个T类型的数组对象，这样可以按照T类型返回T类型数组：
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
首先是判断传入的数组a的大小是否大于或者等于list的大小，如果小于，那么利用反射机制重新创建一个数组，此时参数a和toArray的数组就不是同一个数组了，如果a的大小大于size的值，假设数组a={"1","2","3","4"},LinkedList的值是:{"a","b"}，那么调用toArray方法之后，a的值变为：{"a","b",null,"4"}。"3"变为null是因为
if (a.length > size)
a[size] = null;
今天的分享到这里，谢谢！
