上次被 ArrayList 锤了一拳后，LinkedList 很不服气，做出最后一击(4)

2）LinkedList

遍历 LinkedList 找到某个元素的话，通常也有两种形式：

get(int)，找指定位置上的元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}      

既然需要调用 node(int) 方法，就意味着需要前后半段遍历了。

indexOf(Object)，找元素所在的位置
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}      

需要遍历整个链表，和 ArrayList 的 indexOf() 类似。

那在我们对集合遍历的时候，通常有两种做法，一种是使用 for 循环，一种是使用迭代器（Iterator）。

如果使用的是 for 循环，可想而知 LinkedList 在 get 的时候性能会非常差，因为每一次外层的 for 循环，都要执行一次 node(int) 方法进行前后半段的遍历。

LinkedList.Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        LinkedList.Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        LinkedList.Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}      

那如果使用的是迭代器呢？

LinkedList<String> list = new LinkedList<String>();

for (Iterator<String> it = list.iterator(); it.hasNext();) {

   it.next();

}

迭代器只会调用一次 node(int) 方法，在执行 list.iterator() 的时候：先调用 AbstractSequentialList 类的 iterator() 方法，再调用 AbstractList 类的 listIterator() 方法，再调用 LinkedList 类的 listIterator(int) 方法，如下图所示。

最后返回的是 LinkedList 类的内部私有类 ListItr 对象：

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new LinkedList.ListItr(index);
}
private class ListItr implements ListIterator<E> {
    private LinkedList.Node<E> lastReturned;
    private LinkedList.Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
    public boolean hasNext() {
        return nextIndex < size;
    }
    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
}      

执行 ListItr 的构造方法时调用了一次 node(int) 方法，返回第一个节点。在此之后，迭代器就执行 hasNext() 判断有没有下一个，执行 next() 方法下一个节点。

由此，可以得出这样的结论：遍历 LinkedList 的时候，千万不要使用 for 循环，要使用迭代器。

也就是说，for 循环遍历的时候，ArrayList 花费的时间远小于 LinkedList；迭代器遍历的时候，两者性能差不多。

06、总结

花了两天时间，终于肝完了！相信看完这篇文章后，再有面试官问你 ArrayList 和 LinkedList 有什么区别的话，你一定会胸有成竹地和他扯上半小时了。

这是《Java 程序员进阶之路》专栏的第 61 篇。Java 程序员进阶之路，风趣幽默、通俗易懂，对 Java 初学者极度友好和舒适😘，内容包括但不限于 Java 语法、Java 集合框架、Java IO、Java 并发编程、Java 虚拟机等核心知识点。

https://github.com/itwanger/toBeBetterJavaer

目前已更新或计划更新的内容，绿色✅的是已经更新的。

这么硬核的开源教程，还不赶紧 star 下？