从Java源码上分析为什么LinkedList随机访问比顺序访问要慢这么多？

从Java源码上分析为什么LinkedList随机访问比顺序访问要慢这么多？

代码语言：javascript复制

// 随机访问
for(int i=0;i<list.size();i  ) {
    list.get(i);
}
// 顺序访问
Iterator<E> it = list.iterator();
while(it.hasNext()){
    it.next();
}

LinkedList的get()方法源码

代码语言：javascript复制

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 返回此列表中指定位置的元素。
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    // 判断参数是否是现有元素的索引。
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
    
    // 返回指定元素索引处的（非空）节点。
    Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            // index小于长度一半时，是从链表头部往后找
            for (int i = 0; i < index; i  )
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            // index大于长度一半时，是从链表尾部往前找
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

随机访问使用list.get(i)方法，从源码中我们可以得知，每次list.get(i)都遍历找到该元素位置再返回，当我们需要遍历一次list，其实list.get(i)会遍历很多次，做了重复性工作。

list.iterator()源码

代码语言：javascript复制

Iterator<E> it = list.iterator();

// AbstractList为LinkedList父类的父类
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    // 返回此列表中元素的列表迭代器（以正确的顺序）。
    public Iterator<E> iterator() {
        return listIterator();
    }
    // 返回参数为0的列表迭代器
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }
}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
    
    // 检查index范围
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    
    // 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) {
            // 


	

java linkedlist 遍历 集合 源码 


	




	
 0 人点赞