LinkedList特点
LinkedList底层是通过一个双向链表实现，不是线程安全的。可以被当作双向链表、堆栈、队列或双端队列进行操作。
LinkedList结构
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
-
List：用来存储有序的、可重复的数据。
-
AbstractSequentialList：是个抽象类并且父类为AbstractList，只是使用了列表迭代器(listIterator)重写了增删改查操作（查看AbstractSequentialList源码），而ListIterator的nextIndex()方法和previousIndex()方法可以实现双向链表的操作，使得继承AbstractSequentialList抽象类的实现类拥有操作双向链表的属性。
-
Deque：LinkedList实现Deque 接口，即能将LinkedList当作双端队列使用可作为队列使用。Deque接口主要有ArrayDeque实现，ArrayDeque这个双端队列（用数组实现）线程不安全，区别于用链表实现的双端队列LinkedList。
-
Cloneable：LinkedList实现了Cloneable接口，并覆盖了函数clone()，能被克隆。
-
Serializable：实现java.io.Serializable 接口后LinkedList支持序列化，能通过序列化去传输。
LinkedList属性
//元素的实际个数
transient int size = 0;
/**
*指向第一个节点
* Pointer to first node.
* Invariant[ɪnˈveəriənt]: adj. 无变化的，不变的
(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;
//内部类，用于实现链表
private static class Node<E> {
E item; //存储的元素
Node<E> next; //下一个节点,尾元素的next指向为null
Node<E> prev; //上一个节点,头元素的prev的指向为null
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList方法分析
类源码方法层面的分析最好的方法是使用Debug一步步走一遍该方法。
add(E e)方法
/**
* 增加指定元素到list的末尾
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 使用对应参数作为尾节点
*/
void linkLast(E e) {
//将新加节点的前驱指向last节点(<--)
final Node<E> l = last;
//创建节点(前驱是last节点，元素为e，后继为null节点)
final Node<E> newNode = new Node<>(l, e, null);
//将last节点修改为指向新节点
last = newNode;
//判断新节点的前节点(就是以前的last节点)是不是为空
if (l == null)
//如果新节点的前节点为空，
// 说明这个list集合是一个空集合，这个新加节点是添加的第一个节点，
//将first节点修改为指向新节点
first = newNode;
else
//如果新节点的前节点不为空
//说明这个list集合有元素
//将前节点的后继修改为新节点(-->)
l.next = newNode;
size++;
modCount++;
}
方法思路：直接将新增的元素放置链表的最后面，然后链表的长度（size）加1，修改的次数（modCount）加1
add(int index, E element)方法
public void add(int index, E element) {
checkPositionIndex(index);//检查位置的角标，[0,size]
if (index == size) //如果指定位置为最后，则添加到链表最后
linkLast(element);
else
//如果指定位置不是最后，则添加到指定位置前
linkBefore(element, node(index));
}
//在指定节点前插入节点，节点succ不能为空
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节点
first = newNode;//将first节点修改为新节点
else
//将指定节点的前节点指向新节点
pred.next = newNode;
size++;
modCount++;
}
方法思路：
- 1、检查索引是否越界
- 2、如果指定位置是最后，则添加到链表最后
- 3、如果指定位置不是最后，则添加到指定位置之前
remove()方法
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; // 将节点后继置空，帮助回收
first = next;//首节点的下一个节点成为新的首节点
if (next == null)
//如果链表中就有一个节点，首节点和尾节点都指向这个节点的话
//首节点的下一个节点为空
last = null; //如果不存在下一个节点，则首尾都为null(空表)
else
next.prev = null;//如果存在下一个节点，那它向前指向null
size--;
modCount++;
return element;
}
remove(int index)方法
public E remove(int index) {
checkElementIndex(index);//判断索引是否越界
return unlink(node(index));
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 返回指定索引的节点
*/
Node<E> node(int index) {
// 判断位置在链表前半段或者是后半段
if (index < (size >> 1)) {//如果index在链表的前半段
Node<E> x = first;//第一个节点
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果index在链表的后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//删除不为空的节点x
E unlink(Node<E> x) {
// assert isElementIndex(index);
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()删除操作分以下几个步骤：
- 1、 通过要删除的元素x拿到它的前驱节点prev和后继节点next。
- 2、 若前驱节点prev为null，说明x是集合中的首个元素，直接将first指向后继节点next即可；
若不为null，则让前驱节点prev的next指向后继节点next，再将x的prev置空。（这时prev与x的关联就解除了，并与next建立了联系）。 - 3、若后继节点next为null，说明x是集合中的最后一个元素，直接将last指向前驱节点prev即可；（下图分别对应步骤2中的两种情况）
若不为null，则让后继节点next的prev指向前驱节点prev，再将x的next置空。（这时next与x的关联就解除了，并与prev建立了联系） - 4、最后，让记录集合长度的size减1。
网友评论