JDK1.8 之 集合框架 LinkedList 源码解析
2017-08-31 本文已影响26人
Gxgeek
嗯 今天看下 LinkedList，这个 最后会总结写 ArrayList 的区别吧
继承结构
-
先看下构造函数
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
// 咳咳 怎么说呢 没想到你是这样的构造函数 什么都不干
在看LinkedList 的增删改查之前 我们得有一个认知 就是LinkedList 的 数据结构是 链表（从名字就看出来了），他的每个 节点 都是存在一个 内部类中
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;
}
}
Node 节点 可以看出 LinkedList 是 一个双向链表 存了他自己 和 next 和 prev
接下去我们就可以 真正开始看 增删改查了
老规矩看下 add
- 增 add() ，addAll()
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
// 构建 node 节点
final Node<E> newNode = new Node<>(l, e, null);
//将最新的add 放到 最后
last = newNode;
// 如果尾节点为空 新加入的变成 头结点
if (l == null)
first = newNode;
else// 否则 之前的last 的 next 连接到新加入的节点
l.next = newNode;
size++;// 数组size 变大
modCount++; // 增加修改次数
}
- 删 remove
根据对象
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;
}
根据 对象删除 比较简答 直接去 equals()
根据 下 标删除
public E remove(int index) {
// 判断是否越界
checkElementIndex(index);
return unlink(node(index));
}
// 这段代码用到了 二分法查找 出node 节点
Node<E> node(int index) {
// assert isElementIndex(index);
// 有是size>>1 这个意思就是 size/2 （ >> 效率高）
// index list的左半部分的时候
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;
}
}
// unlink 就是清楚所有 有关节点 的链接然后 删除连接 节点前后 的 next 和prev 在相互连接
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;
// 如果当前节点的 prev 为空 则当前节点的next 变成头节点
if (prev == null) {
first = next;
} else {//否则 prev的 next 连接 当前节点的next
prev.next = next;
x.prev = null;
}
if (next == null) { //如果next 则 prev 变成last
last = prev;
} else { // 否则 next prev 连接 当前节点的prev
next.prev = prev;
x.next = null;
}
x.item = null; // 当前节点 全部连接置空 （提醒jvm GC ）
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;
}
查 get
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
嗯 看起来都很简单的样子 从源码来说 让我看看其他的扩展
这得从昨天 贴的 最后一段代码 说起 ArrayList 和 LinkedList遍历的时候
从今天可以看出来 LinkedList get 是 二分法查找 而 ArrayList 的get 是 直接数组的下标取出来 当然是 ArrayList 遍历快
我们在比较下 remove
回忆一下 ArrayList 增 是 调用底层本地 native 方法 整个数组 拷贝 移动的数组位置 之后 数组向前移动一位
但是LinkedList 增 移动的时候 就很简单了 unlink 改变下 链表 移动元素 前后的 prev 和next 就好了 理论上来说 是Linked remove 快点
实验下：
static final int N=50000;
static long timeListByPrev(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i<N;i++)
list.add(0, o);
return System.currentTimeMillis()-start;
}
static long timeListByLast(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i<N;i++)
list.add(i);
return System.currentTimeMillis()-start;
}
public static void main(String[] args) {
System.out.println("前置插入 ArrayList耗时："+timeListByPrev(new ArrayList()));
System.out.println("前置插入 LinkedList耗时："+timeListByPrev(new LinkedList()));
System.out.println("后置插入 ArrayList耗时："+timeListByLast(new ArrayList()));
System.out.println("后置插入 LinkedList耗时："+timeListByLast(new LinkedList()));
}
out:
前置插入 ArrayList耗时：288
前置插入 LinkedList耗时：4
后置插入 ArrayList耗时：4
后置插入 LinkedList耗时：3
可以看出 差距很大 四舍五入 差100倍 （本机测试 不代表任何基准）
总结一下
- 相对于 add 后置插入 相对于 ArrayList 和 LinkedList 其实差不多 都是最后一位插入 从实验结果来说 ArrayList 会更 慢一点 可能涉及扩容 总体来说 插入两者的花费 差不多相同 但是 对于 前置插入 来说
可以看出 差距很大 四舍五入 差100倍 （本机测试 不代表任何基准）
因为 ArrayList 插入 前置插入 后面的会向后 调用native 方法 复制 数组 消耗就比较高了 而对于LinkedList来 说 其实 前置插入 于后置插入两则的 开销都是相同的
- 对于遍历来说 ArrayList 采用是 直接数组下标 而 LinkedList 采用二分法查找 速度不言而喻
我的公众号
微信公众号
