Java源码解析程序员架构算法设计模式和编程理论

LinkedList 源码之我见

2017-04-08  本文已影响50人  遗忘的流逝

接下来要开始手撕LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 继承自AbstractSequentialList,实现了List Deque Cloneable 实现了序列化。
在此之前,先讲解一下它所具有的内部类Node<E>,我们可以知道这个LinkedList 是用链表实现的,根据这个内部类的实例成员可以看出这是个双向链表,具有前驱结点和后继结点。

private void linkFirst(E e)
增加结点到头结点
void linkLast(E e)
增加结点到尾部结点
void linkBefore(E e, Node<E> succ)
增加一个结点到succ之前
private E unlinkLast(Node<E> l)
删除最后一个
E unlink(Node<E> x)
删除指定的结点

这些事LinkedList的私有函数,一般我们调用的是其在内部封装好的public方法,类似于removeFirst()

public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}

我们从这段代码中可以看出它其实调用了unlinkFirst。unlinkFirst是个private方法就像上面所列举的方法一样。我们用的所有基本操作其实全部来自于这些函数。
基本操作,我们已经很熟了,像什么添加元素到末尾,添加元素到开头等等。
我们在这些当中,有一个modCount实例成员变量特别突出,比如它只是增加,没有减少。

ConcurrentModificationException()

Iterator 是工作在一个独立的线程中,并且拥有一个 mutex 锁。 Iterator 被创建之后会建立一个指向原来对象的单链索引表,当原来的对象数量发生变化时,这个索引表的内容不会同步改变,所以当索引指针往后移动的时候就找不到要迭代的对象,所以按照 fail-fast 原则 Iterator 会马上抛出 java.util.ConcurrentModificationException 异常。
所以 Iterator 在工作的时候是不允许被迭代的对象被改变的。但你可以使用 Iterator 本身的方法 remove() 来删除对象, Iterator.remove() 方法会在删除当前迭代对象的同时维护索引的一致性。(来着网上的答案,我觉得这个还是比较靠谱)。至于fail-fast原则,fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。毕竟,这个linkedList不是线程安全的。vectory为线程安全类。或者使用Collections.synchronizedList();方法转化。
而这个触发的条件是modCount != expectedModCount。

private class ListItr implements ListIterator<E>
这个expectedModCount是来源于这个Listltr内部类,迭代器内部类。它内部维护了这个对象,这个对象的时候,expectedModCount==modCount一般是相等的。

这些代码重复的使用了内部类,实现了隐藏你不想让别人知道的操作,也即封装性。内部类其实还有很多的用处,就留给读者去探索了。

上一篇下一篇

猜你喜欢

热点阅读