LinkedList实现分析（二）——常用操作之一 - 简书
source link: https://www.jianshu.com/p/3a368c5de7bf?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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如下图所示：
然后执行第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的状态入下图所示:
当示例代码执行第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的状态如下图所示：
然后示例代码执行到第4行，此时myList已经有2个node，根据上图可知last指向了“b”node，然创建“c”的node对象，让“c”的prev执行“b”，然后myList中的last指向“c”，“b”的next执行“c”，执行完后myList的状态如下图所示:
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的状态如下图所示：
然后执行第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的状态如下图所示：
然后执行 succ.prev = newNode，是把原来succ指向的前驱节点改成了newNode，因为newNode插入了succ节点前面，因此succ的prev就是newNode，指向完的myList状态如下：
然后是判断pred是否为null,在myList的当前状态中， succ.prev是null，pred也就是null，所以把first指向newNode，也就是在myList的头结点succ之前添加一个新元素newNode，即 first = newNode;然后对size和modCount加一，执行完最后myList的状态如下图:
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;
今天的分享到这里，谢谢！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK