特性
LinkedList 集合底层实现的数据结构为双向链表
LinkedList 集合中元素允许为 null
LinkedList 允许存入重复的数据
LinkedList 中元素存放顺序为存入顺序。
LinkedList 是非线程安全的
添加
因为是双向队列，所以添加有三种方式，添加到最前面，添加最后面和添加到指定的位置。
添加到最前面
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
先将头结点保存下来，将新添加的值封装成一个节点，并赋值给头结点，当f==null时，表明链表没有数据，于是也将值赋值给尾节点，相当于既作为头结点也做尾节点。如果f！=null,则将新添加的节点赋值给原来节点的前一个节点。可表示为：
newNode <--> f
添加最后面
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++;
}
与添加到头结点相反，可以表示如下：
l <--> newNode
添加到指定的位置
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
添加到指定位置，先判断添加的位置，如果添加的位置与list的size一样大，则直接添加到后面即可，如果不是，则插入到当前位置的元素的前面。所以要先找到当前位置的对应的元素，调用node（）。
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;
}
}
查询采用类似二分查找的方式，判断index与size的一半的大小。如果小于一半，则从前面开始遍历，反之则从尾部开始遍历。这样可以加快查询速度。
查询到后开始进行插入。
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++;
}
原理很简单，可以表示为：
succ.pre <--> newNode <--> succ
删除
删除与添加一样，对应也有三种方式。
删除头结点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//先将待删除的节点保存
final E element = f.item;
final Node<E> next = f.next;
//将删除的节点置为null
f.item = null;
f.next = null; // help GC
//将删除节点的下一节点赋值给头结点
first = next;
if (next == null)
last = null;
else
//删除节点的下一节点的前一个节点置为空，相当于把相连的线给断了
next.prev = null;
size--;
modCount++;
return element;
}
删除尾节点
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//先将待删除的节点保存
final E element = l.item;
final Node<E> prev = l.prev;
//将删除的节点置为null
l.item = null;
l.prev = null; // help GC
//将删除节点的前一节点赋值给尾结点
last = prev;
if (prev == null)
first = null;
else
//删除节点的前一节点的后一个节点置为空，相当于把相连的线给断了
prev.next = null;
size--;
modCount++;
return element;
}
删除每个元素
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;
}
可以理解为：
x.prev <--> x <--> x.next 变成 x.prev <-->x.next
LinkedList 作为双向队列
LinkedList实现了Deque，所以他还可以看做一个双向队列。
Queue 是一个队列，遵循 FIFO 准则，我们也知道 Stack 是一个栈结构，遵循 FILO 准则。 而Deque 这个双端队列就厉害了,它既可以实现栈的操作，也可以实现队列的操作。
当 Deque 当做队列使用时（FIFO），只需要在头部删除，尾部添加即可。
当 Deque 当做栈使用时（FILO），只需要在头部删除，头部添加即可。
而Deque也是继承Queue的，所以他们的方法的区别为
Queue Deque
add(e) addLast()
offer(e) offerLast()
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()
Queue的添加方法有返回值，而Deque的没有返回值。
Queue 删除元素的实现 removeFirst 会抛出 NoSuchElement 异常，Queue 删除元素的实现 不会抛出异常 如果链表为空则返回 null
element和peek方法都是获取队列头部元素的实现。其区别是：
element()队列为空的时候回抛出异常，peek()队列为空的时候返回 null
网友评论