接着上一篇文章的源码分析
取出元素
包括方法有：
- peek()
- peekFirst()
- peekLast()
- element()
- get(int index)
- getFirst()
- getLast()
- indexOf(Object o)
- lastIndexOf(Object o)
peek()
/** * 只是访问，但是不移除链表的头元素 */ public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }
peek() 源码比较简单，直接找到链表的第一个节点，判断是否为null，如果为null，返回null，否则返回链首的元素
peekFirst() ： 源码和peek() 相同
peekLast():
/**
* 访问，但是不移除链表中的最后一个元素* 或者返回null如果链表是空链表
*/
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
源码也比较好理解
element() :
/**
* 只是访问，但是不移除链表的第一个元素
*/
public E element() {
return getFirst();
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
与peek()相同的地方都是访问链表的第一个元素，不同是element元素在链表为null的时候会报空指针异常
get(int index) :
/*
* 返回链表中指定位置的元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 返回指定索引下的元素的非空节点
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;
}
}
get(int index)源码也是比较好理解，首先对下标进行越界检查，没有越界的话直接找到索引位置对应的node节点，进行返回
getFirst() ：源码和element()相同
getLast(): 直接找到最后一个元素进行返回，和getFist几乎相同
indexOf(Object o) :
/*
* 返回第一次出现指定元素的位置，或者-1如果不包含指定元素。
*/
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;
}
两种情况：
- 如果需要检索的元素是null，对元素链表进行遍历，返回x的元素为空的位置
- 如果需要检索的元素不是null，对元素的链表遍历，直到找到相同的元素，返回元素下标
lastIndexOf(Object o) :
/*
* 返回最后一次出现指定元素的位置，或者-1如果不包含指定元素。
*/
public int lastIndexOf(Object o) {
int index = size;
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;
}
从IndexOf(Object o)源码反向理解
删除
删除节点的示意图如下：
包括的方法有：
- poll()
- pollFirst()
- pollLast()
- pop()
- remove()
- remove(int index)
- remove(Object o)
- removeFirst()
- removeFirstOccurrence(Object o)
- removeLast()
- removeLastOccurrence(Object o)
- clear()
poll() :
/*
* 访问并移除链表中指定元素
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : 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;
}
poll()方法也比较简单直接，首先通过Node方法找到第一个链表头，然后把链表的元素和链表头指向的next元素置空，再把next节点的元素变为头节点的元素
pollFirst() : 与poll() 源码相同
pollLast(): 与poll() 源码很相似，不再解释
pop()
/*
* 弹出链表的指定元素，换句话说，移除并返回链表中第一个元素
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// unlinkFirst 源码上面👆有
removeFirst源码就多了如果首部元素为null，就直接抛出异常的操作
remove(int index):
/*
* 移除链表指定位置的元素
*/
public E remove(int index) {
checkElementIndex(index);
// 找到index 的节点，断开指定节点
return unlink(node(index));
}
// 断开指定节点
E unlink(Node<E> x) {
// 找到链接节点的元素，next节点和prev节点
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;
}
remove(Object o)
/*
* 移除列表中第一次出现的指定元素，如果存在的话。如果列表不包含指定元素，则不会改变，
* 更进一步来说，移除索引最小的元素，前提是(o == null ? get(i) == null : o.equals(get(i)))
*/
public boolean remove(Object o) {
// 如果o为null
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
// 匹配null对象，删除控对象，返回true
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 如果不为null
for (Node<E> x = first; x != null; x = x.next) {
// 匹配对应节点，返回true
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
removeFirst() 和remove() 源码相同
removeFirstOccurrence(Object o)和 remove(Object o) 源码相同
removeLast() 和 pollLast() 相同
removeLastOccurrence(Object o) 和 removeFirstOccurrence(Object o) 相似
clear()
/*
* 清空所有元素
*/
public void clear() {
// 遍历元素，把元素的值置为null
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++;
}
clear()方法，先找到链表头，循环遍历每一项，把每一项的prev，item，next属性置空，最后再清除first和last节点，注意源码有一点，x = next ，这行代码是向后遍历的意思，根据next的元素再继续向后查找
其他方法
链表最常用的方法就是添加、查找、删除，下面来介绍一下其他的方法
clone()
/*
* 链表复制
*/
public Object clone() {
// 此处的clone
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
// 本地方法
protected native Object clone() throws CloneN
clone() 方法调用superClone()能够获取拷贝过后的值，但是为什么要把first和last置为null，debug的时候就发现clone对象所有的值都为null了，而且为什么又要循环遍历链表再添加一遍？
contains(Object o) : 和index源码几乎相同
set(int index, E element)
/*
* 在指定位置替换指定元素
*/
public E set(int index, E element) {
// 越界检查
checkElementIndex(index);
// 找到索引元素所在的位置
Node<E> x = node(index);
// 元素替换操作，返回替换之前的元素
E oldVal = x.item;
x.item = element;
return oldVal;
}
descendingIterator()
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
descendingIterator 就相当于创建了一个倒置的Iterator，倒叙遍历
listIterator(int index) :
/*
* 在指定位置上返回一个列表的迭代器，这个list-Iterator是有快速失败机制的
* 可以参见我的另一篇文章 ArrayList 源码解析
*/
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
// ListItr 是LinkedList的一个内部类
private class ListItr implements ListIterator<E> {
// 上一个被返回的节点
private Node<E> lastReturned;
// 下一个节点
private Node<E> next;
// 下一个下标
private int nextIndex;
// 期望的修改次数 = 修改次数，用于判断并发情况
private int expectedModCount = modCount;
// 在指定位置创建一个迭代器
ListItr(int index) {
next = (index == size) ? null : node(index);
nextIndex = index;
}
// 判断是否有下一个元素
// 判断的标准是下一个索引的值 < size ,说明当前位置最大 = 链表的容量
public boolean hasNext() {
return nextIndex < size;
}
// 查找下一个元素
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
// 指向下一个元素
next = next.next;
nextIndex++;
return lastReturned.item;
}
// 是否有之前的元素
public boolean hasPrevious() {
// 通过元素索引是否等于0，来判断是否达到开头。
return nextIndex > 0;
}
// 遍历之前的元素
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
// next指向链表的上一个元素
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
// 下一个索引
public int nextIndex() {
return nextIndex;
}
// 上一个索引
public int previousIndex() {
return nextIndex - 1;
}
// 移除元素，有fail-fast机制
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
// 设置当前节点为e，有fail-fast机制
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
// 将e添加到当前节点的前面，也有fail-fast机制
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
// jdk1.8引入，用于快速遍历链表元素
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
// 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
toArray()
/*
* 返回LinkedList的Object[]数组
*/
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
//将链表中所有节点的数据都添加到Object[]数组中
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
toArray(T[] a)
/*
* 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
*/
public <T> T[] toArray(T[] a) {
// 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
// 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
//将链表中所有节点的数据都添加到数组a中
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
</div>
