LinkedList的继承结构：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
Queue(interface):
队列的父接口，抽象方法：
boolean add(E e);// 插入元素到队列，（超过容量会抛出异常）
boolean offer(E e);// 在不超出容量的情况下插入元素到队列（超过容量返回false）
E remove();// 出列返回第一个元素，（空会抛出异常）
E poll();// 出列，返回第一个元素（空返回null）
E element();// 返回第一个元素，但是不出列（和peek的区别是这个方法会抛出异常）
E peek();// 返回第一个元素，但是不出列（空返回null）
Deque（interface）：双端队列
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
结合队列的接口解释都能看懂上端队列接口的抽象方法；
LinkedList：
LinkedList的底层是双端链表（队列/双端队列），特点是增删快，查找慢
LinkedList的类变量
// 存放数据的个数
transient int size = 0;
// 链表的头
transient Node<E> first;
// 链表的尾
transient Node<E> last;
// 内部类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;
}
}
LinkedList(Collection<? extends E> c):
使用集合构造linkedList
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 判断index是否合法
checkPositionIndex(index);
// 将集合转为数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) { // 如果是构造方法里进来的
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) { // 遍历这个数组（集合转化的）
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) { // 如果是构造方法进来的，
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
// 判断下标是否合法
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
简单说下由集合构造的LinkedList，将集合转为数组，在遍历数组，创建node拼接到first和last；
add（E 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;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
LinkedList没有数量限制，所以不需要考虑容量大小，直接新建一个node，拼接到最后；
remove():
直接调用remove（），返回链表第一个元素，first指针后移
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return 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;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
remove(Object o)：
删除指定的元素
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;
}
// 删除指定元素的主要代码
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;
}
unLink（）主要思路：找到当前unLink节点x的pre和next，如果pre==null，说明x是第一个节点，将first = first.next就可以删除第一个节点了；如果next==null，说明x是最后一个节点，直接将last==null即可；如果在中间，将前面一个相邻的节点和后面一个相邻的节点连接起来；因为链表是双向的，所以需要两次连接操作；（记得置null便于回收内存）
网友评论