版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/81389523
LinkedList
LinkedList是基于双向循环链表(从源码中可以很容易看出)实现的,除了可以当做链表来操作外,它还可以当做栈、队列和双端队列来使用。
LinkedList同样是
非线程安全
的,只在单线程下适合使用。LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆。
先看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;
}
}
根据JDK版本的不同 ,构造方法也不同
/**
* JDK1.8
* Deque接口,Deque接口表示是一个双端队列,那么也意味着LinkedList是双端队列的一种实现,
* 所以,实现了基于双端队列的所有操作。
*/
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* 构造方法在1.6版本也不太一样
* 默认构造函数:创建一个空的链表
*/
public LinkedList() {
header.next = header.previous = header;
}
/**
* 链表的表头,表头不包含任何数据。Entry是个链表类数据结构。 相当于1.8 Node
*/
private transient Entry<E> header = new Entry<E>(null, null, null);
/**
* 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* 因为数据结构不大一样 所以add方式也不一样
* remove方式 实现方式有一点不一样
*/
/**
* JDK1.8 节点Node
* Links e as last element.
*/
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++;
}
/**
* Unlinks non-null node 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;
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;
}
/**
* JDK1.6 节点Entry
* 将节点(节点数据是e)添加到entry节点之前。
*/
private Entry<E> addBefore(E e, Entry<E> entry) {
// 新建节点newEntry,将newEntry插入到节点e之前;并且设置newEntry的数据是e
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
// 修改LinkedList大小
size++;
// 修改LinkedList的修改统计数:用来实现fail-fast机制。
modCount++;
return newEntry;
}
/**
* 将节点从链表中删除
*/
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
Java 集合中常见 checkForComodification()方法的作用? modCount和expectedModCount作用?
Node的查找加速
/**
* 源码中先将index与长度size的一半比较,if index < (size >> 1),就只从位置0往后遍历到位置index处,
* 而如果index > (size >> 1),就只从位置size往前遍历到位置index处。
* 这样可以减少一部分不必要的遍历,从而提高一定的效率(实际上效率还是很低)。
* JDK1.8这里用的是位运算 , 而JDK1.6 用的是判断index<size/2
* Returns the (non-null) Node at the specified element index.
*/
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;
}
}
每次看都有新发现,都会更新记录!