【Java源码分析】LinkedList类

LinkedList<E> 源码解读

继承AbstractSequentialList<E>

实现List<E>, Deque<E>, Cloneable, Serializable接口

方法说明

private void linkFirst(E e)

功能:将新元素添加至链表的头。

过程:如果头为空,头尾结点共同指向新结点,反之,把新结点插入到原头结点前。

void linkLast(E e)

功能:将新元素添加至链表的尾。

过程:如果尾为空,头尾结点共同指向新结点,反之,把新结点 插入到原尾结点后。

void linkBefore(E e, Node<E> succ)

功能:把新结点插入到目标结点前。

过程:设置一个临时引用指向succ的前结点,然后把新结点插入到succ结点前结点的后面,succ的前指针重新指向新结点,新结点前指针如果为空,那么头指针指向新结点,否则,新结点的前结点的后指针指向新结点。

private E unlinkFirst(Node<E> f)

功能:把头结点删除并返回结点元素值(不能对空链表执行该操作)。

过程:建立临时结点存储头结点的next指针指向的结点,让头结点的元素值置为空,头结点的next指针指向空,判断如果头结点的next指针指向空,那么尾结点也指向空(即链表为空),否则,让头结点的next指针指向的结点(最开始存入临时结点)的前指针指向空。

private E unlinkLast(Node<E> l)

功能:把尾结点删除并返回结点元素值(不能对空链表执行该操作)。

过程:建立临时结点存储尾结点的prev指针指向的结点,让尾结点的元素值置为空,尾结点的prev指针指向空,判断如果尾结点的prev指针指向空,那么头结点也指向空(即链表为空),否则,让尾结点的prev指针指向的结点(最开始存入临时结点)的后指针指向空。

E unlink(Node<E> x)

功能:删除一个结点,并返回该结点的元素值(不能对空链表执行该操作)。

过程:建立两个临时的结点的引用,分别指向目标结点的头指针指向的结点和后指针指向的结点。判断如果目标结点前指针不为空,那么临时的结点引用prev的后指针指向临时的结点引用next指向的结点,否则,原头指针指向临时结点引用next所指向的结点,然后把目标结点的前指针指向空。对目标结点的后指针同样进行判断操作,然后把目标结点的后指针指向空。最后把目标结点元素置空。

public E getFirst()

功能:返回链表第一个结点的元素值。

过程:判断头结点是否为空,如果为空则抛出NoSuchElementException异常,否则返回头指针指向的结点的元素值。

public E getLast ()

功能:返回链表最后一个结点的元素值。

过程:判断尾结点是否为空,如果为空则抛出NoSuchElementException异常,否则返回尾指针指向的结点的元素值。

public E removeFirst()

功能:删除头结点并返回结点元素值。

过程:判断头结点是否为空,如果为空则抛出NoSuchElementException异常,否则调用unlinkFirst()方法。

public E removeLast ()

功能:删除尾结点并返回结点元素值。

过程:判断尾结点是否为空,如果为空则抛出NoSuchElementException异常,否则调用unlinkLast()方法。

public void addFirst(E e)

功能:向链表头添加一个元素。

过程:调用linkFirst(E e)方法。

public void addLast(E e)

功能:向链表尾添加一个元素。

过程:调用linkLast (E e)方法。

public boolean contains(Object o)

功能:判断某个元素是否在链表中。

过程:调用indexOf()方法,判断返回的索引值是否为-1,如果是则代表链表中不存在该元素索引,则返回false,否则返回true.

public int size()

功能:返回链表长度。

过程:返回LinkedList类中的类私有变量size.

备注:size在链表进行添加和删除操作时都会相应的增加或减少。

public boolean add(E e)

功能:向链表尾部添加一个元素

过程:调用包权限方法linkLast(E e),并返回true.

public boolean remove(Object o)

功能:删除链表中的某个元素。

过程:判断o是否为空,如果为空则遍历链表,把空元素所在结点用unlink()方法删除,并返回true;反之,也遍历链表,调用equals()方法判断每个结点的元素是否和传入的元素相等,如果是则调用unlink()方法删除,并返回true;如果都没有符合条件的元素,则返回false.

public boolean addAll(Collection<? extends E> c)

功能:把一个Collection对象直接添加至链表尾部。

过程:调用addAll(size, c)并将该方法的返回值直接返回。

public boolean addAll(int index, Collection<? extends E> c)

功能:把一个Collection对象插入到链表第index元素之后。

过程:先调用checkPositionIndex方法检测传入的index是否超过链表size,如果是则抛出异常。然后将Collection对象转为Object数组,判断数组长度是否为0,是的话则返回false.然后创建两个结点的引用,分别指向index结点(prev)和index后一结点(succ)(如果后一结点为空则指向空)。然后遍历传入的Collection对象被转成的Object数组,每次建立一个临时的newNode,然后插入之前创建的指针中(prev后,succ前),并返回true.

public void clear()

功能:清空链表中所有结点。

过程:遍历链表,当结点不为空时,建立一个临时结点引用指向下一结点,然后清空当前结点的元素值及prev next指针。最后让first和last指针都指向空,并置size为0.

public E get(int index)

功能:根据索引返回指定的结点元素值。

过程:先调用checkElementIndex()方法检查索引是否超过链表长度,超过则抛出异常。然后返回指定结点元素,调用node()方法的返回制定结点并访问item成员。

public E set(int index, E element)

功能:根据指定的索引修改结点中的元素值,并返回之前结点中的元素值。

过程:先调用checkElementIndex()方法检查索引是否超过链表长度,超过则抛出异常。然后把原先结点的元素的值存储起来,替换后返回原结点的元素值。

public void add(int index, E element)

功能:把元素插入到指定索引结点前。

过程:首先判断索引是否越界,如果是则抛出异常。否则,判断索引是否为最后一个元素之后的元素(即index == size),如果是则调用linkLast()方法,把结点插入最后,否则调用linkBefore()方法,把新结点插入到指定索引结点前。

public E remove(int index)

功能:删除指定索引出的结点。

过程:先调用checkElementIndex()方法判断索引是否越界,是则抛出异常。然后调用unlink()方法将指定结点删除,并返回unlink()的返回值。

private boolean isElementIndex(int index)

功能:判断索引值是否大于等于0且小于size,即索引对应的结点是否存在。

过程:如果小于0或大于等于size则返回false,反之,则返回true.

private boolean isPositionIndex(int index)

功能:判断索引值是否大于等于0且小于等于size,即索引位置对于迭代器和add()方法来说是否合法。

过程:如果小于0或大于size则返回false,反之,则返回true.

private String outOfBoundsMsg(int index)

功能:返回索引越界异常的字符串提示信息。

过程:返回索引越界异常的字符串提示信息。

private void checkElementIndex(int index)

功能:如果索引对应结点不存在(index < 0 || index >= size),抛出越界异常。

过程:调用isElementIndex()方法判断索引是否有对应的结点,如果没有,抛出异常。

private void checkPositionIndex()

功能:如果索引不能用于迭代器和add()方法(index < 0 || index > size),抛出越界异常。

过程:调用isPositionIndex()方法判断索引是否有对应的结点,如果没有,抛出异常。

Node<E> node(int index)

功能:返回索引对应的结点。

过程:先判断index与size右移一位后(>>1即除以2)后,如果index在左半部分,则从head结点开始遍历,如果index在右半部分,则从last结点向前开始遍历。

private int indexOf(Object o)

功能:返回对应的o所在结点的索引值,如果有重复则返回第一个结点对应的索引值,如果不存在则返回-1.

过程:判断o是否为空,分为空或非空的分支情况然后从first结点遍历链表,若没有找到则返回-1.

private int lastIndexOf(Object o)

功能:返回对应的o所在结点的索引值,如果有重复则返回最后的一个结点的索引值,如果不存在则返回-1.

过程:判断o是否为空,分为空或非空的分支情况然后从last结点遍历链表,若没有找到则返回-1.

LinkedList模拟Queue方法

public E peek()

功能:返回头结点的元素值。

过程:判断头结点是否为空,为空则返回空,否则返回头结点对应元素。

public E element()

功能:返回头结点的元素值,如果为空则抛出异常。

过程:调用getFirst()方法,并将getFirst()方法的返回值返回。

public E poll()

功能:删除头结点。

过程:删除头结点,如果头为空则返回空,否则调用unlinkFirst()方法并返回该方法的返回值。

public E remove()

功能:删除头结点,如果头结点为空则抛出异常。

过程:调用removeFirst()方法并返回该方法的返回值。

public boolean offer(E e)

功能:添加一个结点至链表尾部。

过程:调用add()方法。

LinkedList模拟Deque方法

public boolean offerFirst(E e)

功能:添加一个结点至链表头部。

过程:调用addFirst()方法并返回true.

public boolean offerLast(E e)

功能:添加一个结点至链表尾部。

过程:调用addLast()方法并返回true.

public E peekFirst()

功能:返回头结点的元素值,如果为空则返回空。

过程:判断头结点是否为空,如果为空则返回null,否则返回头结点元素值。

public E peekLast()

功能:返回尾结点的元素值,如果为空则返回空。

过程:判断尾结点是否为空,如果为空则返回null,否则返回尾结点元素值。

public E pollFirst()

功能:返回头结点的元素值,如果为空则返回空,否则删除头结点。

过程:判断头结点是否为空,如果为空则返回null,否则调用unlinkFirst()并返回该方法的返回值。

public E pollLast()

功能:返回尾结点的元素值,如果为空则返回空,否则删除尾结点。

过程:判断尾结点是否为空,如果为空则返回null,否则调用unlinkLast()方法并返回该方法的返回值。

public void push(E e)

功能:把一个元素添加到链表的头。

过程:调用addFirst()方法。

public E pop()

功能:删除头结点并返回头结点元素值,如果为空链表则抛出异常。

过程:调用removeFirst()并返回该方法的返回值。

public boolean removeFirstOccurrence(Object o)

功能:删除对应元素第一次出现所在的结点。

过程:调用remove()方法并返回该方法返回值。

public boolean removeLastOccurrence(Object o)

功能:删除对应元素最后一次出现所在的结点。

过程:判断o是否为空,分两种情况分别操作。从链表尾部向前遍历链表,遇到第一个符合条件的结点时调用unlink()方法删除,并返回true.如果没有符合条件的结点,则返回false.

Iterator操作

public ListIterator<E> ListIterator(int index)

功能:返回对应索引的迭代器。如果索引越界则抛出异常。

过程:调用checkPositionIndex(index),然后返回一个ListItr(此类中的内部类)的实例。

内部类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结点为索引对应链表中的结点,如果为空则返回空。初始化nextIndex为index.

过程:判断index是否等于size,如果等于则复制next为空,否则调用node()方法把索引对应的结点让next引用指向。最后把index赋值nextIndex.

public boolean hasNext()

功能:判断链表是否有下一结点。

过程:返回nextIndex < size结果。

public E next()

功能:判断迭代过程中是否对链表对象进行更改,如果有则抛出异常。然后判断是否有下个元素,如果没有抛出异常。然后返回迭代器指向的下一结点的元素值,然后把迭代器指向下一位。

过程:调用checkForComodification()方法检查在迭代过程中是否对链表对象进行操作(只能使用迭代器提供的方法对链表进行操作),然后调用hasNext()方法判断是否有下一结点,如果没有抛出NoSuchElementException()异常。最后使用内部类成员变量lastReturned指向next指向的结点位置,然后让next引用指向后一结点对象,为nextIndex进行加一操作,返回lastReturned的元素值。

public boolean hasPrevious()

功能:判断当前结点是否还有前结点。

过程:返回nextIndex > 0结果(nextIndex为初始化是传递进来的索引值)。

public E previous()

功能:判断迭代过程中是否对链表对象进行更改,如果有则抛出异常。然后判断是否有上个元素,如果没有抛出异常。然后返回迭代器指向的上一结点的元素值,然后把迭代器指向上一位。

过程:调用checkForComodification()方法检查在迭代过程中是否对链表对象进行操作(只能使用迭代器提供的方法对链表进行操作),然后调用hasPrevious()方法判断是否有下一结点,如果没有抛出NoSuchElementException()异常。最后使用内部类成员变量lastReturned指向next指向的结点位置,然后让next引用指向前一结点对象(为空则置空),为nextIndex进行减减操作,返回lastReturned的元素值。

public int nextIndex()

功能:返回当前结点的索引值。

过程:返回nextIndex.

public int previousIndex()

功能:返回前一结点的索引值。

过程:返回nextIndex – 1.

public void remove()

功能:判断是否在迭代过程中使用非迭代器方法对链表进行操作了(会对链表长度产生变化),如果有则抛出异常。然后判断迭代器是否移动了,如果未移动则抛出异常。然后删除迭代器移动之前所指向结点。

过程:调用checkForComodification()方法判断迭代过程中是否有非迭代器方法对链表长度改变的操作,然后判断lastReturned是否为空,即是否使迭代器位置发生改变。如果未发生改变则抛出异常。然后把lastReturned的下一结点赋值给临时结点引用,调用unlink()方法删除目标结点(迭代器移动前所指向的结点),如果要删除的结点是尾结点,那么next结点引用指向被删结点的next指向结点,否则,nextIndex计数器减减操作。

public void set(E e)

功能:把上一次迭代器改变位置的结点置新值。

过程:判断lastReturned变量是否为空来判断迭代器是否移动过,如果没有移动过则抛出异常,然后调用checkForComodification()方法判断是否有非迭代器方法改变了链表长度,如果有则抛出异常。然后把lastReturned结点的item值更换为传递过来的引用。

public void add(E e)

功能:如果迭代器移动过,则把新元素添加到迭代器上次指向的结点之后。

过程:调用checkForComodification()判断迭代器是否移动过,如果上次移动的位置是结尾,则调用linkLast()方法把元素添加至链表尾部,否则调用linkBefore()方法把元素添加至目标结点后。

public void foreachRemaining(Consumer<? super E> action)

暂时不明确该方法使用方法及实现过程。

final void checkForComodification()

功能:判断是否有非迭代器方法使得链表长度发生改变。

过程:比较modCount和expectedModCount变量,如果在迭代期间调用了操作链表长度的非迭代器内方法,则modCount值会与expectedModCount不同步,抛出异常。

内部类private static class Node<E>

成员变量:E item;          代表一个结点的元素值。泛型E表示。

Node<E> next;              代表指向下一结点的引用。

Node<E> prev;              代表指向前一结点的引用。

Node(Node<E> prev, E element, Node<E> next)

含参构造器,用于初始化。

迭代器方法

public Iterator<E> descendingIterator()

功能:返回一个逆向迭代器的对象。

过程:返回一个DescendingIterator实例。

内部类 private class DescendingIterator implements Iterator<E>

成员变量:private final ListItr itr = new ListItr(size());

建立一个迭代器的实例,让其初始指向链表尾部。

public boolean hasNext()

功能:判断是否有前驱结点并返回真假。

过程:调用ListItr内部类中hasPrevious()方法并返回其返回值。

public E next()

功能:返回前驱结点的元素值。

过程:调用ListItr内部类中previous()方法并返回其返回值。

public void remove()

功能:删除迭代器上次操作指向结点。

过程:调用ListItr内部类中remove()方法。

其他方法

private LinkedList<E> superClone()

功能:调用Object(基类)的clone()方法进行复制操作。

过程:如果不能克隆则抛出异常,否则用super调用Object的clone方法并返回。

public Object clone()

功能:重写Object的clone()方法,用于链表的复制。

过程:调用superClone()方法进行一次浅复制,然后把这个复制的链表对象置空,遍历原链表,然后进行复制,最后返回。

public Object[] toArray()

功能:把链表的元素以Object数组的形式返回。

过程:建立一个大小为size的Object数组,遍历链表把每个结点的元素值赋值给Object数组,最后返回该数组。

public <T> T[] toArray(T[] a)

功能:返回以适当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组;返回数组的运行时类型为指定数组的类型。如果指定数组能容纳列表,则在其中返回该列表。否则,分配具有指定数组的运行时类型和此列表大小的新数组。

如果指定数组能容纳列表,并有剩余空间(即数组比列表元素多),则紧跟在列表末尾的数组元素会被设置为 null。(只有 在调用者知道列表不包含任何 null 元素时,才可使用此方法来确定列表的长度。)

private void writeObject(java.io.ObjectOutputStream s)

private void readObject(java.io.ObjectInputStream s)

暂时不明确该方法功能及过程。

public Spliterator<E> spliterator()

功能:返回一个Spliterator迭代器。

过程:返回一个LLSpliterator<E>的实例。

内部类 static final class LLSpliterator<E> implements Spliterator<E>

暂时不明确用法及功能。

上一篇:System类学习笔记


下一篇:Anatomy of a Database System学习笔记 - 存储管理