LinkedList源码解析
序言
LinkedList，顾名思义就是使用链表的形式存储List。链表和数组就是俞亮。各有优缺点。
源码解析
package java.util;
import java.util.function.Consumer;
//采用双端链表的形式，就是其中的节点有next和pre引用(指针)分别指向本
//节点的下一个节点和上一个节点
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
//列表的头引用(指针)
transient Node<E> first;
//链表的尾引用(指针)
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//插入到头部
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++;
}
//拿出来第一个节点，有点队列的感觉
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (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;
}
////可以看到链表对待头或者尾的操作都很快，直接定位，o(1) 的时间
//获取第一个节点的数据,直接使用头引用first
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//获取最后一个节点的数据，直接使用尾引用last
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
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 void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
//对待这种不知道是第几个的，那就没办法了，一个一个的查找了
public boolean contains(Object o) {
return indexOf(o) != -1;
}
//size是记录起来的
public int size() {
return size;
}
//当你不指定位置的时候，ArrayList和LinkedList都是插入尾部的
public boolean add(E e) {
linkLast(e);
return true;
}
//和ArrayList差不多，都是需要遍历，只不顾一个使用next指针，一个使用数组的
//索引定位
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;
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, 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;
}
//清空整个List
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//这个方法目的是返回第index个元素，如果是ArrayList，直接elementData[index-1]就行
//但是LinkedList就得一个一个的找，但是这个地方
//用了一个小技巧：就是看index和size>>1(其实就是size除以2)比较，看下这个index
//位于链表的左半边还是右半边，位于左半边，那就从头部开始找，反之从尾部开始找
//能节约很多执行时间的
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;
}
}
//这种根据对象去找的，那就只有一一遍历了
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;
}
LinedList和ArrayList的比较
这个最多，其实优缺点大家都很明白，我再次介绍下
1、 ArrayList底层用的是数组，LinkedList底层是双端链表
2、 ArrayList的访问速度比LinkedList快，这个快也就是根据下标定位，如果是根据对象去查找定位，他俩区别
3、 ArrayList扩容的时候可能产生内存浪费，但是LinkedList不会，LinkedList是需要一个节点， 那就new一个，不过ArrayList可以使用trimSize函数来去除掉多余的内存
4、 ArrayList的插入比较费劲，尤其是指定位置插入，需要各种调用System.arrayCopy操作，LinkedList在查找的时候 麻烦，但是插入的时候，o(1)即可
问题案例比较
曾经有个案例是这样子：需要处理一批(大概1200万)的数据，从数据库根据关联关系得到我们要的数据(大概1200万) ，然后写入到文件中去，当时的做法是从处理文件当中读取100万，作为一个批次，然后数据库操作获取到我们需要的 关联数据，之后等待着100w都返回完了，写入文件，这中间倒是没有出现什么内存OOM问题，而是，写入的速度非常的 慢，一秒钟只能写1000-1200行/s的样子，后面想了下，不至于这么慢啊，1000来行，估计也就是100KB的样子，硬盘 的速度不至于这么慢，加了一下日志才看到，原来是 list.get(int index)的方法调用太耗时了，去查看了一下使用 的list是LinkedList，看了一下源码明白了，对于100万数据，调用get(int index)，所需要的查找次数是： (1+500000)*500000/2 *2 = 250000500000(2500亿次)。之后使用ArrayList进行替换，速度提升到每秒50万行/s 的写入速度，因为ArrayList是直接定位，100万数据也就100万次查找定位。这次我算是体会到了一次他俩的性能体验了.