前言
LinkedList实现了List和Deque接口,说明LinkedList是个双向链表来的,又是队列,允许添加null值;该类底层是用链表来实现,具有先进先出。从jdk的文档中也可以知道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;
}
}
1、java.util.LinkedList#add(E)
public boolean add(E e) {
linkLast(e);
return true;
}
//加在链表的最后节点
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
//如果一开始l节点为null,则first节点=newNode=last节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
2、java.util.LinkedList#addFirst
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
//如果一开始f节点为null,则first节点=newNode=last节点
if (f == null)
last = newNode;
else
//f节点的prev节点 = newNode
f.prev = newNode;
size++;
modCount++;
}
3、java.util.LinkedList#addLast
public void addLast(E e) {
linkLast(e);
}
4、java.util.LinkedList#remove(java.lang.Object)
//移除某个节点的值,使用for循环遍历,如果成功移除o的话,则返回true,否则返回false
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;
}
//返回x节点的元素
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==null,说明x是first节点,
//所以如果移除x的话,则first=x.next,这样就能保证队列中的数据准确
if (prev == null) {
first = next;
} else {
//如果prev不为null,则prev.next必须指定到x.next,也就是上面的next对象
prev.next = next;
//这里方便对象回收
x.prev = null;
}
//如果next == null,则x是last节点
//所以如果移除x的话,则last=x.prev,这样就能保证队列中的数据准确
if (next == null) {
last = prev;
} else {
//如果next不为null,则next.prev必须指定到x.prev,也就是上面的prev对象
next.prev = prev;
//这里方便对象回收
x.next = null;
}
//这里方便对象回收
x.item = null;
//size-1
size--;
modCount++;
return element;
}
5、java.util.LinkedList#get
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//这里使用类似二分查找法来遍历查数据。
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
6、java.util.LinkedList#set
//将对应位置的对象重新赋值,然后返回旧值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
7、java.util.LinkedList#add(int, E)
public void add(int index, E element) {
checkPositionIndex(index);
//如果index==size的话,就加到链表最后
if (index == size)
linkLast(element);
else
//
linkBefore(element, node(index));
}
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++;
}
8、java.util.LinkedList#remove(int)
public E remove(int index) {
checkElementIndex(index);
//这里复用了unlink(Object o) 方法,这个方法上面已经做了解读
return unlink(node(index));
}
9、java.util.LinkedList#indexOf
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;
}
10、java.util.LinkedList#peek
//返回队列中先进的元素,可能返回null值
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
11、java.util.LinkedList#poll
//返回队列中先进的元素,并将该元素从队列中移除
public E poll() {
final Node<E> f = first;
//unlinkFirst,移除队列中先进来的元素
return (f == null) ? null : unlinkFirst(f);
}
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; // help GC
f.next = null; // help GC
first = next;
//如果当前节点的下个节点为null,则该队列为空了
if (next == null)
// help GC
last = null;
else
// help GC
next.prev = null;
size--;
modCount++;
return element;
}
12、java.util.LinkedList#remove()
//如果当前队列为空的话,会抛出NoSuchElementException
//这里和pop方法是有点区别的,pop在队列为空的情况是不会抛异常
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
13、offer、offerFirst、offerLast、peekFirst、peekLast、pollFirst、pollLast是jdk1.5之后加的方法
offer、offerFirst、offerLast和add、addFirst、addLast对应,只不过offer都会返回一个boolean值
至于peekFirst、peekLast、pollFirst、pollLast的代码实现也很简单
总结
LinkedList具备列表和队列的特性。在做队列集合的时候可以使用。
如果大家喜欢这样风格的代码分析,点点关注,点点赞,也在评论区指出不足之处,后续还会推出相关框架的源码分析