LinkedList简介
LinkedList概述
LinkedList底层通过双向集合的数据结构实现,LinkedList可以作为List使用，也可以作为队列和栈使用。支持从集合的头部，中间，尾部进行添加、删除等操作。LinkedList的继承与实现的关系图如下所示。
LinkedL
ist继承与实现的关系图.jpg
-
LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）有着更好的性能。 -
双向链表的每个节点用内部类
Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。当链表为空的时候first和last都指向null。
双链表结构示意图.png
// 一个私有的内部类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;
}
}
预热Deque接口
-
ArrayDeque和LinkedList是Deque的两个通用实现，由于官方更推荐使用AarryDeque用作栈和队列 -
从名字可以看出
ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要手动同步；另外，该容器不允许放入null元素。
看看源码怎么说
添加Add
//调用add默认会添加到链表末尾
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
//得到最后一个节点的指针,
final Node<E> l = last;
//封装一个节点 l为前一个节点引用地址 e真正存储的数据,后面存放后一个节点的引用
final Node<E> newNode = new Node<>(l, e, null);
//最后一个节点指向新增的节点地址
last = newNode;
if (l == null)
//空链表中新添加的节点就是第一个
first = newNode;
else
//非空链表中新添加的节点就是链表最后节点的下一个节点
l.next = newNode;
//链表长度
size++;
//扩容次数
modCount++;
}
void add(int index, E element)
add(int index, E element)的逻辑稍显复杂，可以分成两部，1.先根据index找到要插入的位置；
2.修改引用，完成插入操作。
public void add(int index, E element) {
//位置索引检测 return index >= 0 && index <= size;
checkPositionIndex(index);
if (index == size)
//末尾插入 详情见上面
linkLast(element);
else
//根据位置插入数据 node(index)得到index位置的节点
linkBefore(element, node(index));
}
//处理index位置的节点succ
void linkBefore(E e, Node<E> succ) {
//得到succ的前驱指针
final Node<E> pred = succ.prev;
//创建newNode节点，将newNode的后继指针指向succ，前驱指针指向pred
final Node<E> newNode = new Node<>(pred, e, succ);
//将succ的前驱指针指向newNode
succ.prev = newNode;
if (pred == null)
//前驱指针为空 就是第一个节点
first = newNode;
else
//前驱指针不为空 那么直接将pred的后继指针指向newNode即可
pred.next = newNode;
size++;
modCount++;
}
双链表添加元素示意图.png
- 双链表 每个节点都有一个
head前驱指针和tail后驱指针 前一个节点的tail指针指向后一个节点的head指针,如果后一个节点后面没有数据时,后一个节点的tail指针指向null ,但是双链表为空时head和tail都指向null
删除
-
移除一个对象从双向链表中 步骤
-
得到三个节点 1.需要删除的节点(x) 前一个节点(
prev) 后一个节点next -
把前一个节点的后驱指针
tail指向后一个节点next -
再把后一个节点的前驱指针
head指向前一个节点prev -
再把当前的节点x置空 就完成了双向链表的删除操作
-
public boolean remove(Object o) {
//空对象的处理
if (o == null) {
//遍历节点
for (Node<E> x = first; x != null; x = x.next) {\
//节点数据为null
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 = 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;
}
总结
- 通过对LinkedList的源码解读,又会增加对数据结构双向链表的认识,
和ArrayList的对比
其实就是链表和数组的对比。插入，删除：
-
ArrayList：基于数组实现，通常情况下添加元素很简单，直接将元素添加到预先创建的数组中，没有额外操作。但当数组空间不足时，就涉及到扩容，数组的复制，性能很差。删除时，需要进行数组元素的复制，性能不高。 -
LinkedList：基于链表实现，可变长，单纯的插入和删除操作，都比较简单，修改下关联节点的前后"指针"即可。
查询：
-
ArrayList：支持随机访问，查询效率高。时间复杂度O(1)。 -
LinkedList：不支持随机访问，按下标索引查询效率较低,尽量不要使用下标索引的方式进行元素的遍历，推荐使用迭代器
