LinkedList的源码解析
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0; // transient不可序列化
transient Node<E> first;
transient Node<E> last;
构造方法:
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//内部私有类Node:
构造方法的参数顺序是：前继节点的引用，数据，后继节点的引用。
关于为什么Node这个类是静态的？答案是：这跟内存泄露有关，Node类是在LinkedList类中的，也就是一个内部类，若不使用static修饰，那么Node就是一个普通的内部类，在java中，一个普通内部类在实例化之后，默认会持有外部类的引用，这就有可能造成内存泄露。但使用static修饰过的内部类（称为静态内部类），不用再创建外部类的对象了,就不会有这种问题
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;
}
}
Add 方法
//addFirst 执行linkFirst方法
public void addFirst(E e) {
linkFirst(e);
}
//addLast 和add执行的都是同一个方法
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
add(index,element)
//在某个索引位置添加元素
//该add方法将添加集合元素分为2种情况，
//一种是在集合尾部添加，另一种是在集合中间或头部添加，
public void add(int index, E element) {
//调用方法去检查输入的索引是否存在,不在就抛异常
checkPositionIndex(index);
//如果你所输入的索引值刚好等于集合的大小,就属于把元素插入到链表尾部,索引从0开始
if (index == size)
linkLast(element);
else
//先调用node(int index)方法得到指定位置的元素节点,也就是linkBefore()方法中的形参 succ。
linkBefore(element, node(index));
}
addAll 方法
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // 检查是否越界
Object[] a = c.toArray(); // 将集合转为数组
int numNew = a.length; // 获取到集合的大小
if (numNew == 0) //长度为空返回false
return false;
Node<E> pred, succ; // pred：中间变量， succ：插入位置的后一个元素
if (index == size) { // 如果插入位置为尾元素的下一个位置
succ = null; // 插入位置后面没有元素了
pred = last; // 新插入集合的前一个元素为原来的尾元素
} else { // 如果不是在尾部的下一个元素插入
succ = node(index); // 通过node()方法获取到index位置的元素
pred = succ.prev; // 插入集合的首元素的前指向为index位置的前一个元素
}
for (Object o : a) { // 循环遍历，使新插入集合元素的排列起来，并使pred指向新插入集合的最后一个元素
@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;
}
LinkFirst
//linkFirst方法是私有的所以不能从外部调用
该方法,从外部传入我们要add的参数
private void linkFirst(E e) {
//让此时集合中的头节点（即first"指针"指向的节点）赋给变量f
final Node<E> f = first;
//创建一个新节点，结合Node的构造函数，我们可以知道，在创建新节点（newNode）的同时，newNode的next指向了f(即之前集合中的头节点)，变量f 就是newNode的后驱节点了，newNode的前继节点为null。
final Node<E> newNode = new Node<>(null, e, f);
//再将first指向newNode，也就是说newNode成为该链表新的头节点
first = newNode;
if (f == null)
//接着，判断变量f 是否为null，若是null，说明之前集合中没有元素（此时newNode是集合中唯一一个元素），则将last指向newNode，也就是说此时的newNode既是头节点又是尾节点（要知道，这时newNode中的prev和next均是null，但被first和last同时指向）；若变量f 不是null，说明之前集合中已经存在了至少一个元素，则让之前集合中的头节点（即变量f ）的prev指向newNode。（结合步骤2，此时的newNode与newNode的后驱节点f已经是相互指向了）
last = newNode;
else
f.prev = newNode;
size++;
modCount++; //理解为修改的次数
}
linkLast方法
//让此时集合中的尾节点（即last"指针"指向的节点）赋给变量l
void linkLast(E e) {
final Node<E> l = last;
//创建一个新节点，结合Node的构造函数，我们可以知道，在创建新节点（newNode）的同时，newNode的prev指向了l(即之前集合中的尾节点)，变量 l 就是newNode的前驱节点了，newNode的后继节点为null。
final Node<E> newNode = new Node<>(l, e, null);
//再将last指向newNode，也就是说newNode成为该链表新的末尾节点。
last = newNode;
//接着，判断变量 l 是否为null，若是null，说明之前集合中没有元素（此时newNode是集合中唯一一个元素），则将first指向newNode，也就是说此时的newNode既是头节点又是尾节点（要知道，这时newNode中的prev和next均是null，但被first和last同时指向）；若变量 l 不是null，说明之前集合中已经存在了至少一个元素，则让之前集合中的尾节点（即变量 l ）的next指向newNode。（结合步骤2，此时的newNode与newNode的前驱节点 l 已经是相互指向了）
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
LinkBefore方法
void linkBefore(E e, Node<E> succ) {
// assertsucc != null;
//通过succ.prevt得到succ的前一个元素pred。（此时拿到了第index个元素succ，和第index-1个元素pred）
final Node<E> pred = succ.prev;
//再创建一个新节点newNode，newNode的prev指向了pred，newNode的next指向了succ。（即newNode往succ和pred的中间插入，并单向与它们分别建立联系，eg：pred ← newNode → succ）
final Node<E> newNode = new Node<>(pred, e, succ);
//再让succ的prev指向newNode。（succ与跟newNode建立联系了，此时succ与newNode是双向关联，eg：pred ← newNode ? succ）。
succ.prev = newNode;
//接着，判断pred是否为null，若是null，说明之前succ是集合中的第一个元素（即index值为0），现在newNode跑到了succ前面，所以只需要将first指向newNode（eg：first ? newNode ?succ）;若pred不为null，则将pred的next指向newNode。（这时pred也主动与newNode建立联系了，此时pred与newNode也是双向关联，eg：pred?newNode ? succ）
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
remove方法
//removeFirst方法
//获取到LinkedList的首元素，然后判断是否为空，如果为空，则抛出NoSuchElementException异常，否则通过调用unlinkFirst(Node<E> f)方法来移除首元素。
unlinkFirst这个方法是LinkedList的内部方法，源代码如下。首先拿到首元素的下一个元素(新的首元素)，然后将首元素的值，和指向下一个元素的变量都置为空，然后等待垃圾回收器空闲的时候把首元素GC掉，然后判断新的首元素是否为空，如果为空，则置尾元素也为空，并且新的首元素的前指向也置空，size(列表存储个数)减一，modeCount(结构变化次数)也减一，返回新的首元素。
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f); // 调用unlinkFirst(Node<E>f)来移除首元素
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
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;
}
private E unlinkLast(Node<E> l) {
// assert l
== last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
//首先通过查找是否包含该元素，实现原理和contains方法一致，在找到的时候，调用unlink方法，移除元素。
unlink方法就是将，要移除元素的前一个元素的后指针指向移除元素的下一个元素，要移除元素的下一个元素的前指针指向要移除元素的上一个元素，当然，要判断前后元素是否为空的状态。
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;
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
get方法
public E get(int index) {
//先查看索引是否越界
checkElementIndex(index);
return node(index).item;
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
Set方法
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
node方法
//根据索引值查找相应的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;
}
}
clear方法
//通过遍历链表，将每一个结点的结构体内的变量置为空，等待垃圾处理器进行回收，并置size为0
public void clear() {
// Clearing
all of the links between nodes is "unnecessary", but:
// - helps a
generational GC if the discarded nodes inhabit
// more than one generation
// - is sure
to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
//查看是否包含该元素
public boolean contains(Object o) {
return indexOf(o) != -1;
}
//如果传入的参数为空,遍历是只要得到的item为空的时候就返回当前的index,如果不为空,遍历是比较器值
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;
}
public int size() {
return size;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private String outOfBoundsMsg(int index) {
return "Index:
"+index+", Size: "+size;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
lastIndex方法
//返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
public int lastIndexOf(Object o) {
int index = size;
//如果传入的值为空,遍历集合,从后往前遍历,如果得到的item为空就刚好就是那个地方所对应的index
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E element() {
return getFirst();
}
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E remove() {
return removeFirst();
}
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
}
网友评论