Java集合之LinkedList源码剖析(jdk1.8)
目录
1、简介
LinkedList底层基于双向链表，增删快，插入慢，还可以作为队列或者栈来使用。
继承图谱如下：
LinkedList实现了List、Serializable、Cloneable、Deque等接口。
LinkedList实现了Cloneable，可以被克隆。
LinkedList实现了Serializable，可以被序列化。
LinkedList实现了Deque接口，能作为队列、栈使用。
2、源码剖析
1、属性
LinkedList的属性非常简单，因为基于链表，所以内部有一个Node类。
只有三个主要属性。
//元素数量
transient int size = 0;
//链表头节点
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;
}
}
2、内部类
除了Node类外，内部还有三个和迭代器有关的内部类。
其中较为常用的是ListItr类，该类继承自ListIterator，可以向前向后遍历数据。
通过LinkedList的listIterator(int index) 方法获得。
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
//略去
}
除了listIterator迭代器外，也可以使用iterator这个Collection的迭代器。
LinkedList海域两个迭代器基本不使用。
3、构造方法
有两个构造方法,都很简单。
由于基于链表，所以构造方法可以不用指定空间。
在增加元素的时候再使用已有节点连接新节点。
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//从尾节点后加入集合c,组成新链表
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//通过索引，将集合c挂到链表中
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;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
4、链表方法
这部分方法多数是用于对内部链表进行维护的方法。
对内部链表进行增删改查。
node(int 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;
}
}
link系列方法（增操作）
link方法是对链表进行增加操作。
可以从头部、尾部、任意位置之前添加。
//从头部添加
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//从尾部添加
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++;
}
//在某个节点前添加
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++;
}
ulink系列方法(删操作)
ulink系列方法用于删除节点。
//删除首节点，此处f必须是首节点
private E unlinkFirst(Node<E> f) {
//这两个用于暂存f内容
final E element = f.item;
final Node<E> next = f.next;
//这两个是用于辅助Gc的
f.item = null;
f.next = null;
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//删除尾节点，l必须是尾节点
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) {
//默认x为中间节点，暂存x内容
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;
}
set方法(改操作)
更新的方法直接就可以从外部访问。
//通过索引更新元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
5、List方法
这部分方法从外部就可以访问，基于内部链表。
get方法(查)
通过node方法执行get系列方法。
以及一个indexOf方法。
//通过索引获取元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//获取头节点元素
public E getFirst() {
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;
}
//通过元素获取索引
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;
}
add方法(增操作)
add方法用于加入元素，在构造方法中使用过addAll方法。
//从尾部添加
public boolean add(E e) {
linkLast(e);
return true;
}
//从指定位置添加
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//从头部加入
public void addFirst(E e) {
linkFirst(e);
}
//同样是从尾部加入
public void addLast(E e) {
linkLast(e);
}
remove方法(删)
删除方法，调用了unlink系列方法，在核心方法中已有。
//从头部删除元素
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) {
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;
}
6、其他方法
这部分方法多是对各种接口的实现。
toArray方法
Collection接口的实现，将集合转化为数组。
//转换为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;
}
//转换为T类型数组，T必须是LinkedList的泛型
@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;
}
push/pop/peek方法
这是对Deque接口的实现，可以充当栈操作。
//这里入栈出栈都从头部操作，这样不用每次都遍历链表
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
3、总结
（1）LinkedList底层基于双链表，增删快，查询慢；
（2）LinkedList还是一个双端队列，具有队列、双端队列、栈的特性；
（3）LinkedList线程不安全。
（4）LinkedList有多种迭代器，支持向前向后遍历。