ArrayList和LinkedList源码初看

约定不等于承诺〃 2022-11-12 10:53 127阅读 0赞

**无论是是ArrayList还是LinkedList，都是List的子类，因此它就自然而然的继承了List的特点；**

特点：

*  有序排列，存取的规律为先进先出，如存入的顺序为\[1,2,3,4\]，那么取出时的顺序也为\[1,2,3,4
 *  允许重复元素，与Set集合相反
 *  自带索引，通过索引就可以操作集合中的每个元素。

> ArrayList的存储的结构是数组结构。内部的实现原理能够让其动态增长和缩减

**正因为是动态的数组结构，因此ArrayList元素增删慢，查找快**

ArrayList底层源码是基于数组来实现的，并且默认初始的容量为10

transient Object[] elementData; // non-private to simplify nested class access
       private int size;
    	/**
         * Default initial capacity.
    	*/
        private static final int DEFAULT_CAPACITY = 10;

get(int index)方法:

public E get(int index) {
        
            rangeCheck(index); //检查数组是否越界
            return elementData(index);//直接返回数组的下标
        }

add(E e) 方法

public boolean add(E e) {
        
            ensureCapacityInternal(size + 1);  // 判断是否需要扩容
            elementData[size++] = e; //执行添加操作
            return true;
        }

此时，add方法中调用了ensureCapacityInternal(size + 1); ,继续翻阅该方法

private void ensureCapacityInternal(int minCapacity) {
        
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); //此处嵌套了两个方法
        }

此时又继续调用方法ensureExplicitCapacity方法，且内部执行了calculateCapacity用于扩容

private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0) //判断是否需要执行扩容，如果该长度大于数组的长度，就执行扩容，且每次扩容按1.5进行
            grow(minCapacity);
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }

**最终调用了grow方法**

private void grow(int minCapacity) {
        
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

此处第三四行代码：

*  int oldCapacity = elementData.length;
 *  int newCapacity = oldCapacity + (oldCapacity >> 1); //

oldCapacity >> 1)执行了右移操作，相当于 oldCapacity / 2

**这里就是扩容大小确定的地方，相当于新的最大容量是 旧的数组长度+旧数组的0.5长度**

> LinkedList是一个双向链表,因此除了头结点外的每一个节点都有前驱指针和后继指针

正因为LinkedList的存储结构为链式存储，因此具备了链表的特点：

1.  LinkedList的查询速度慢
2.  LinkedList的增加和删除操作速度快

当我们需要对LinkedList进行遍历操作时，可以使用迭代器完成。学过数据结构这门课，就常因为那绕来绕去的前后指针而留下坏印象，但是java当中提供了丰富的类库

//new一个String类型的LinkedList，插入三个元素
    LinkedList<String> linkedList = new LinkedList<>();
            linkedList.add("1");
            linkedList.add("2");
            linkedList.add("3");
    Iterator<String> iterator = linkedList.iterator();
    //使用迭代器的next方法
     String next = iterator.next();
     System.out.println(next);

linkedList.add()方法是在链表的尾部进行插入，当我们需要对链表的中间位置进行增删操作时，可以使用迭代器listIterator，这是Iteraror的子接口。

//访问链表的下一节点，并在下一节点处插入字符“123”
    ListIterator<String> it = linkedList.listIterator();
            String next = it.next();
            it.add("123");
            System.out.println(next);
            System.out.println(linkedList);

linkedList也有通过所谓的索引来获取链表的值:

LinkedList<String> linkedList = new LinkedList<>();
            linkedList.add("1");
            linkedList.add("2");
            linkedList.add("3");
            linkedList.add("4");
    		//根据索引值获取 "2"
            String s = linkedList.get(1);
            System.out.println(s); //结果为2

但可以通过翻阅源码查看LinkedList的get方法：

public E get(int index) {
        
            checkElementIndex(index);//检查是否越界
            return node(index).item;
      }

可以看到此处调用了一个node方法去查找该位置的Element,继续查看node()的源码：

Node<E> node(int index) {
        
        if (index < (size >> 1)) {
        // >>将链表的长度size右移1一位，即判断index跟size/2的大小
            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;
        }
    }

可以看到，这种从索引位置获取的元素的方式，是通过循环的方式来获得，对比ArrayList的索引获取，效率非常的低。