前言
LinkedList与Vector和ArrayList存在很大的不同，底层使用链表实现，也正是这个数据结构注定它的使用场景和其它两个不同。我们都知道数组读取的速度是O(1),但删除和写入数据可能涉及到数组的移动，所以效率会慢一些，而链表和数组正好相反，链表的读写速度慢，到操作速度快，只需要改变指针指向即可，一起看看它是如何实现的。
LinkedList
LinkedList是List接口的常用实现，对于一些读少写多的场景是非常合适的，它实现了Deque接口，所以拥有双向链表的功能，LinkedList是无法指定容量大小的，所以不存在扩容的说法，它会根据数据的大小，自动伸缩，但是如果链表无限长的话，查询效率是极低的，也可能会发生OOM。
源码分析
一下源码是基于JDK 1.8来分析，如果发现和你看的源码不一样，那得看看你的源码的版本哦。
重要的属性
// 容器元素个数
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
重要的属性就是上边的三个，其实很容易看出来，实现双向链表是基于first和last来实现的。
构造方法
// 无参构造方法
public LinkedList() {
}
// 初始化容器的时候把传入的数据存到容器里
public LinkedList(Collection<? extends E> c) {
this();
// 后边说
addAll(c);
}
构造函数很简单，因为是使用链表存储，所以不需要指定容器大小。
Node
Node是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;
}
}
存储数据的方法
容器提供了三总数据存储的方法，我们挨个分析
add(E e)
边看源码边分析
public boolean add(E e) {
// 看方法名应该能猜出来，是将数据写到末尾
linkLast(e);
return true;
}
void linkLast(E e) {
// 记录一下last尾节点
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++; // 容器数据+1
modCount++; // modCount 的作用不分析，看前Vecotor的分析
}
当我们通过add(E e)方法将数据写入容器时，会将新的数据写入链表的尾部
add(int index,E e)
指定插入的位置
public void add(int index, E element) {
// 验证index，其实就是和size进行比较
checkPositionIndex(index);
if (index == size) // 说明插入末尾，和add(E e)是一样的
linkLast(element);
else
linkBefore(element, node(index)); // 在中间的位置插入
}
/*
* 这个方法的主要目的是找出要插入位置的节点
* 因为是双向链表，所以可以从头尾开始查询
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// size >> 1 其实就是获取size的中点
if (index < (size >> 1)) { // 说明节点在前半部分，从头结点开始查
Node<E> x = first;
// 只能for循环挨个比较
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;
}
}
/*
* 插入数据的方法：找到要插入的位置节点就很简单了，只需要移动指针就可以
* @param e 要插入的值
* @param succ 要插入位置的节点
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 记录插入位置的上一个节点
final Node<E> pred = succ.prev;
// 创建新节点，并将它的下一个节点指向succ
final Node<E> newNode = new Node<>(pred, e, succ);
// 将succ 的上一个节点指向新节点
succ.prev = newNode;
if (pred == null) // 说明succ是头结点
first = newNode; // 将first指向新的节点即可
else
pred.next = newNode; // 将pred的下一个节点指向新的节点
size++; // 容器数据+1
modCount++;
}
主要步骤如下：
- 验证index的正确性： index >= 0 && index <= size
- 找到链表中index位置的节点 succ
2.1 为了加快查询效率，先找到index在链表的前半部分还是后半部分
2.2 如果是前半部分，从first开始查，反之从last开始查 - 先记录index位置节点的前一个节点 pre
- 创建新的节点newNode,并将newNode.next = succ
- 如果pre为空，说明是头节点，将first = newNode，反之pre.next = newNode
- size++ , modCount++
addFirst
将新的元素新增到链表的头部
public void addFirst(E e) {
// 啥也不干，交给linkFirst处理
linkFirst(e);
}
private void linkFirst(E e) {
// 先记录头结点
final Node<E> f = first;
// 创建新节点，并将它的next指向头结点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
以上就比较简单了，将新的节点放到头结点，只是简单的节点引用指向改变就能实现
addLast
将新的节点放入链表尾部，这个方法和add(E e)是一样的，都是交给linkLast方法去做，这里就不再分析了。
set(int index,E e)
LinkedList也提供了更新数据的方法，逻辑都一样，先通过node(index)方法找到要修改的节点，然后将值进行替换，返回旧值，这里不分析啦，自己看吧。
get(int index)
get方法其实很简单，走的还是node(index) 方法，先找到节点，然后返回节点值，不分析了
LinkedList拥有了头节点和尾节点两个属性，所以对于操作头结点和尾节点来说，很方便，所以它可以实现栈，也可实现队列
peekFirst
返回链表头部的值，不删除头结点
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
pollFirst
返回头结点，并删除头结点
public E pollFirst() {
final Node<E> f = first;
// 删除头节点是在unlinkFirst方法里做
return (f == null) ? null : unlinkFirst(f);
}
// 删除头节点，并返回旧头节点的值
// 入参 f就是要删除的节点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 先记录头节点的值
final E element = f.item;
// 获取要删除节点的下一个节点
final Node<E> next = f.next;
// 优秀的代码是为别人考虑的，将引用置空，让GC尽快回收
f.item = null;
f.next = null; // help GC
// 将头节点指向下一个节点
first = next;
if (next == null)
last = null; // 说明只有一个节点
else
next.prev = null; // 将next节点的上一个节点指向null，因为它已经是头结点
size--; // 容器数据-1
modCount++;
return element;
}
其实也很简单，我相信peekLast和pollLast方法不需要我分析了吧，知道了操作原理，怎么操作都很容易明白
remove
remove方法是用来删除容器数据，默认删除的就是头节点的数据，你一定想到了吧，没错，做事的还是unlinkFirst方法，已经分析过了。
案例
基于LinkedList的特性，我们可以用来实现队列 和 栈 ，简单写两个demo
队列（先进先出）
public class LinkedListStudy {
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
}
private static class MyQueue{
LinkedList<Integer> list = new LinkedList<>();
public void push(Integer num){
list.addFirst(num);
}
public Integer pop(){
if(list.size() == 0){
return null;
}
return list.pollLast();
}
}
}
输出
1
2
3
栈（先进后出）
public class LinkedListStudy {
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.push(3);
System.out.println(myStack.pop());
System.out.println(myStack.pop());
}
private static class MyStack {
LinkedList<Integer> list = new LinkedList<>();
public void push(Integer num){
list.addFirst(num);
}
public Integer pop(){
if(list.size() == 0){
return null;
}
return list.pollFirst();
}
}
}
输出
3
2
总结
- LinkedList底层使用链表存储，容器容量不受限制
- 因为使用链表存储，所以查询效率低，不过通过双向链表可以稍微缓解一些，但是操作数据的效率很高
- 由于使用的是双向链表，所以可以当做队列和栈来使用。
以上就是我分析，如果问题，烦请支出更正，一起学习。
我是一个爱看源码的老谢，知道越多，不知道的越多。
网友评论