Java源码分析之LinkedList
1.这个类位于java.util包下。
2.继承关系
<span style="font-family:Microsoft YaHei;font-size:14px;">public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable</span>
1)继承AbstractSequentialList类，提供了List接口骨干性的实现，并且减少实现List接口的复杂度。
2)实现List接口
3)实现Deque接口，定义双端操作的方法
4)实现Coloneable接口，标记接口
5)实现Serializable接口，标记接口，表示可序列化
3.底层使用双向链表实现的，所以插入和删除操作比ArrayList高效
4.源码分析
1)定义了三个属性
<span style="font-family:Microsoft YaHei;font-size:14px;"> transient int size = 0;//表示的是链表的大小Node结点的定义：是LinkedList的静态内部类，每个节点指向前一个结点和后一个结点，这就是双向链表结点。
transient Node<E> first;//指向第一个结点
transient Node<E> last;//指向最后一个结点</span>
<span style="font-family:Microsoft YaHei;font-size:14px;"> 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;
}
}</span>
2)构造方法
<span style="font-family:Microsoft YaHei;"> <span style="font-size:14px;"> <span style="font-weight: normal;">public LinkedList() {
}</span></span></span>
<span style="font-weight: normal;">public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}</span>
}</span></span></span>
this();
addAll(c);
}</span>
LinkedList类提供了两个构造方法。一个是无参的构造方法，是一个空链表，第二个是接收一个Collection参数c，先调用自身的无参构造方法，然后调用addAll()方法，将c中的元素加入到链表中。
<span style="font-size:18px;"> public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}</span>
<span style="font-size:18px;"></span><pre name="code" class="java"> public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); //判断插入的位置index是否在正常范围内0<=index<size 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; } for (Object o : a) { E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null)插入在第0个 first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) {插入的位置在最后面 last = pred; //last指向最后一个节点 } else { pred.next = succ; succ.prev = pred; } size += numNew; //增加size的大小 modCount++; return true; }
3）链表遍历器：ListIterator
通过调用对象的listIterator(int index)返回从指定位置开始的链表遍历器。实现了ListIterator接口的类，需要实现hasNext(), next(),hasPrevious(),nextIndex(),previousIndex(),remove(),set(),add()方法。<span style="font-size:18px;"> public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);//判断index是否越界
return new ListItr(index);//返回从指定位置开始的链表遍历器
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
</span>
<span></span>//构造函数，初始化next和nextIndex
ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; }<span style="white-space:pre"></span>//判断是否还有下一个结点 public boolean hasNext() { return nextIndex < size; }<span style="white-space:pre"></span>//返回下一个结点 public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; }<span style="white-space:pre"></span>//判断是否有前一个结点 public boolean hasPrevious() { return nextIndex > 0; }<span style="white-space:pre"></span>//返回前一个结点 public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; }<span style="white-space:pre"></span>// public int nextIndex() { return nextIndex; }<span style="white-space:pre"></span>// public int previousIndex() { return nextIndex - 1; }<span style="white-space:pre"></span>//删除结点 public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; }<span style="white-space:pre"></span>//添加节点 public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); }<span style="white-space:pre"></span>//与ArrayList类似，也是通过一个属性modCount来判断是否在取得遍历器之后对链表进行结构变化的操作，如果有
<span style="white-space:pre"></span>//则会抛异常 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }4）从后往前遍历
调用descendingIterator()得到LinkedList对象的从后往前的遍历器。/**
* @since 1.6 */ public Iterator<E> descendingIterator() { return new DescendingIterator(); }
LinkedList类的遍历器类是通过内部的私有类实现Iterator接口得到的，实现了Iterator接口的类需要自己实现三个方法，hasNext()，next()，remove()。 private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
5)toArray(T[] a),通过数组的反射机制新建新的数组，在执行toarray操作。
public <T> T[] toArray(T[] a) {
if (a.length < size)
<span style="color:#ff0000;"><strong><u> a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);</u></strong></span>
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;
}