上一篇分析了ArrayList的源码jdk源码——集合(ArrayList)，这一次分析LinkedList的源码。
先看一下LinkedList的类定义：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
由上面的代码，可以得出LinkedList继承了AbstractSwquentialList，接下来我们先看一下AbstractSwquentialList类。
/*
abstract AbstractSequentialList继承了AbstractList，所有的方法内部都是调用一个抽象的方法listIterator(int index)，
*/
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
protected AbstractSequentialList() {
}
//获取，根据内部的迭代器，获取值
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
//设置新值
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
//指定位置添加
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
//删除指定位置的值
public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
//在指定的位置添加一个集合
public boolean addAll(int index, Collection<? extends E> c) {
try {
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
Iterator<? extends E> e2 = c.iterator();
while (e2.hasNext()) {
e1.add(e2.next());
modified = true;
}
return modified;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
//返回一个迭代器
public Iterator<E> iterator() {
return listIterator();
}
//抽象方法，需要子类实现
public abstract ListIterator<E> listIterator(int index);
}
有父类可以知道，LinkedList必须实现listIterator方法，方法内部必须要实现一个迭代器，并将之返回。
ArrayList的底层是一个数组，LinkedList的底层是一个链表。如果你知道链表结构的操作，看LinkedList将会非常简单。
不知道大家对链表有没有认识，这里就不讲解链表了，如果有同学不会的话，可以网上搜一下。链表是由一个一个的节点组成的。我们可以看一下java中对链表的定义。
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;
}
}
——LinkedList的成员变量
/*
first和list都会在链表被修改时候(首或尾改变)或添加的时，就会被赋予值，
*/
transient int size = 0;//LinkedList的长度
transient Node<E> first;//首节点
transient Node<E> last;//末节点
这些成员变量，都被transient关键字所修饰，这个关键字的作用就是不被序列化
——LinkedList的构造方法(2个)
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);调用了addALL()方法，下面会介绍
}
——LinkedList的普通方法
——添加
/**
在首位添加，
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;//first变为新添加的节点
if (f == null)
//如果f为null，则该链表为null
last = newNode;//尾节点，首节点都是newNode
else
f.prev = newNode;//前面插入
size++;
modCount++;
}
/*
在最后添加元素
*/
void linkLast(E e) {
//transient Node<E> last;
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
//如果l为null，则该链表为null
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/*
在某个元素之前插入元素
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
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++;
}
//----------------------------------几乎后面的添加操作，都是调用的上面的三个方法
/*
在first位置插入元素
*/
public void addFirst(E e) {
linkFirst(e);
}
/*
addLast和add方法一样，都是调用linkLast方法
*/
public void addLast(E e) {
linkLast(e);
}
/*
在末尾添加节点
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/*
添加一个集合
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/*
添加集合的实际操作方法，有参数构造器，也调用了此方法，
*/
public boolean addAll(int index, Collection<? extends E> c) {
//index就是在指定位置添加一个集合，其实链表并没有和数组一样的下标，只是LinkedList有一个size属性，添加操作时会+1，类似于下标
checkPositionIndex(index);//判断参数合法化，index >= 0 && index <= size;，如果不符合，则会抛出异常
Object[] a = c.toArray();//将传入的集合转化为数组
int numNew = a.length;
if (numNew == 0)
//如果传入的集合长度为0，直接返回false
return false;
Node<E> pred, succ;
if (index == size) {
//如果在最后添加
succ = null;
pred = last;//保存未添加集合之前，最后一个节点
} else {
//如果不是在最后添加
succ = node(index);//保存的是指定位置的节点
pred = succ.prev;//保存的是指定位置的节点的前一个节点
}
for (Object o : a) {
//循环遍历，将将得到的元素变为一个节点结构，
@SuppressWarnings("unchecked") E e = (E) o;//将Object类型强制转化
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//如果前一个节点为null，证明是在第一个节点添加
first = newNode;//重新设置first
else
//前一个节点不为null，只需要维护维护节点的next，将前一个节点的next指向这个新节点即添加成功
pred.next = newNode;
pred = newNode;//然后把该节点当做当前节点，继续循环遍历
}
if (succ == null) {
last = pred;//因为实在末尾进行添加操作，首节点未改变，末节点已经改变，还需要重新设置
} else {
//因为不是在末尾添加，所以首尾节点不改变或者已经在for循环中进行了维护，
pred.next = succ;//将已经添加成功后的节点的next指向添加之前index位置的节点(在中间添加一个集合的情况)
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
/*
固定位置添加值
*/
public void add(int index, E element) {
checkPositionIndex(index);///判断参数合法化
if (index == size)
linkLast(element);//如果传入的参数等于长度，直接在最后添加元素
else
//如果不等于链表长度，调用linkBefore(),在摸个元素之前添加节点
linkBefore(element, node(index));
}
/*
在链表尾添加元素
*/
public boolean offer(E e) {
return add(e);
}
/*
在链表头部添加元素
*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/*
在链表尾添加元素,
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/*
在链表首添加第一个元素
*/
public void push(E e) {
addFirst(e);
}
大家可以看到添加的方法有很多，但是有很多方法都重复了，底层都是调用了同一个方法。其实根本没有区别。
——删除
/*
删除第一个元素并返回
*/
private E unlinkFirst(Node<E> f) {
/*
其实根本不是真正以上的删除，只是将第一个节点后面的那个节点的prev设置为null，第一个节点next设置为null，
first保存第一个节点后的那个节点，如此而已
*/
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // 将第一个节点都设置为null，会让垃圾收集器进行清除
first = next;
if (next == null)
//如果next为null，证明是该链表只有一个节点
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/*
删除并返回最后一个元素，维护最后一个和倒数第二个节点即可
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/*
删除指定为的元素并返回
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;//后一个节点
final Node<E> prev = x.prev;//前一个节点
//将后一个节点和前一个节点互相指向，即可
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
//----------------------------------下面的删除方法都是调用的上面的三个删除方法
/*
删除第一个元素
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/*
删除最后一个元素
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/*
删除指定的值删除节点
*/
public boolean remove(Object o) {
if (o == null) {
//就是循环遍历，得到包含这个值得节点，然后调用unlink()删除这个节点
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/*
只要指定固定位置的，都需要调用node()方法，来获得该位置的元素
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));//调用了node(int index),获得节点
}
/*
删除第一个元素，如果为空时返回null
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/*
删除第一个元素，如果为空时报错
*/
public E remove() {
return removeFirst();
}
/*
unlinkFirst()删除，获取并移除第一个元素
*/
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/*
unlinkFirst()删除，获取并移除最后一个元素
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
/*
删除第一个元素，如果为空，会报错
*/
public E pop() {
return removeFirst();
}
/*
从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
*/
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/*
删除最后一次出现的指定元素，
*/
public boolean removeLastOccurrence(Object o) {
if (o == null) {
//也是循环遍历，只不过方向是从后往前
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
} 删除的方法也是，都有了大量的重复，但是有少许的不同，就是为null，是返回null，还是报错。底层还是调用的相同的方法。
——获取
/*
获得指定位置的元素
*/
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
//这个设计，我没有想到，我想的是遍历链表，设置length值，遍历一次length+1，知道length=index，而这个设计是根据index，进行next操作
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
/*
获得第一个元素
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
//为null抛异常
throw new NoSuchElementException();
return f.item;
}
/*
获得最后一个元素
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
/*
根据指定位置，获得值
*/
public E get(int index) {
checkElementIndex(index);//判断传入的指定位置，是否合法
return node(index).item;
}
/*
获得该元素在链表中的下标
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
//从头到尾 依次比较
if (x.item == null)//为空时，比较的是地址
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))//不为空时，比较的是内容
return index;
index++;
}
}
return -1;
}
/*
获得该元素在最末尾的下标
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
/*
获得首元素，如果为null，返回null，不为空，则返回该元素的值
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/*
获得第一个元素，为空时会报错
*/
public E element() {
return getFirst();
}
/*
获取第一个值，如果为空，返回null
*/
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/*
获取最后一个值，如果为空，返回null
*/
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
—— 获取并删除
/*
unlinkFirst()删除，获取并移除第一个元素
*/
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/*
unlinkFirst()删除，获取并移除最后一个元素
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
—— 设置
/*
固定位置设置元素并返回原来的值
*/
public E set(int index, E element) {
checkElementIndex(index);//判断传入的指定位置，是否合法
Node<E> x = node(index);//获得指定位置的元素
E oldVal = x.item;//仅仅需要改变节点中的值即可，因为上一个节点的地址和下一个节点的地址都没有改变.
x.item = element;
return oldVal;
}
—— 其他方法
/*
size会在链表改变时改变size
*/
public int size() {
return size;
}
/*
是否包含该元素，也是查询该链表，如果有则返回length值，length并不是下标值，只是模拟的下标志
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/*
清除链表
*/
public void clear() {
for (Node<E> x = first; x != null; ) {
//循环遍历，将node节点全部设置为null
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
/*
链表的复制，实际上就是创建一个新的空的链表然后将目的链表添加
*/
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
/*
将链表变为数组，创建一个数组，遍历，将链表中每个节点的值放在新创建的数组中
*/
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;
}
@SuppressWarnings("unchecked")
/*
将链表变为数组，就是遍历，将链表中每个节点的值放在指定的数组中
*/
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;
}
好了，LinkedList集合就分析到这了。差不多就是这样了吧，看集合的底层最好是有一些数据结构的基础，这样看源代码，会起到事半功倍的效果。
嗯，文章中有错误的，记得评论哦！下一篇简单将一下红黑树，因为set集合的底层是Map集合，而Map集合的底层是红黑树。所以，知道红黑树的结构和操作，很重要！！！