实现原理
LinkedList是基于链表实现的，链表是一种线性的存储结构，是一个双向链表，链表中的存储结构除了记录当前的数据的地址外，还记录了，前一个和后一个数据的地址。
LinkedList的node内部类是这样实现的：
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;
}
}
item为当前节点存储的数据，next记录下个节点的引用，prev记录上个节点的引用。
常用方法分析
添加元素
public boolean add(E e) {
linkLast(e); //调用linkLast方法，关联最后一个元素
return true;
}
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++;
}
- 定义一个变量，指向最后一个对象（Node<E> l = last），为了把最后一个node，和新创建的node关联起来
- 创建一个前置、后置引用为null的Node节点
- 把最后一个对象引用(last)指向新创建的对象
- 当l为null，即第一次添加元素时，把first引用指向这个新创建的node节点；如果l不为null，即之后添加元素时，把l的引用，即原先的最后的一个Node节点的next引用指向新创建的node上
- 集合的个数+1，然后修改的次数也+1
查看元素
public E get(int index) {
checkElementIndex(index);//验证index是否超过索引的
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//根据索引index返回对应的Node节点
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;
}
}
这段代码就体现出了双向链表的好处了。双向链表增加了一点点的空间消耗（每个Node里面还要维护它的前置Node的引用），同时也增加了一定的编程复杂度，却大大提升了效率。
由于LinkedList是双向链表，所以LinkedList既可以向前查找，也可以向后查找，node方法的作用就是：当index小于数组大小的一半的时候（size >> 1表示size / 2，使用移位运算提升代码运行效率），向后查找；否则，向前查找。
删除元素
支持按元素删除 和 按下标删除
按元素删除代码如下：
//按元素删除时从first指向的元素开始向下遍历，如果相等或为null则剔除这个元素对象
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;
}
//剔除指定的节点元素
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) { //如果前一个节点为空，则说明当前这个节点为第一个节点，删除这个节点后，
//下个节点会成为第一个节点，first指向下个节点
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;
}
将prev,x,next引用指向null是为了让虚拟机可以回收这个Node节点。
但是，按照Java虚拟机HotSpot采用的垃圾回收检测算法—-根节点搜索算法来说，即使prev、x、next不设置为null也是可以回收这个Entry的，因为此时这个Entry已经没有任何地方会指向它了，x的prev与first的next都已经变掉了，所以这块Node会被当做”垃圾”对待。之所以还要将prev、x、next设置为null，网上大神认为可能是为了兼容另外一种垃圾回收检测算法—-引用计数法，这种垃圾回收检测算法，只要对象之间存在相互引用，那么这块内存就不会被当作”垃圾”对待。
按下标删除元素比较简单，代码如下：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
- 首先先检查下标是不是越界
- 根据node方法取出待删除的Node节点
- 用unlink方法进去删除
LinkedList和ArrayList的对比
- 插入速度AL的速度比LL要快，因为AL是基于数组实现的，数组的对象都是事先new好在那放着，添加对象时只需要数组的指向就可以了，而LL则是新new的，再加上一些引用赋值的操作，所以会比AL慢些，AL的时间主要耗时在容量扩容
- 基于上一点，因为LL里面不仅维护了待插入的元素，还维护了Entry的前置Node和后继Node，如果一个LL中的Node非常多，那么LL将比AL更耗费一些内存
JDK版本: 1.7.0_75
网友评论