java 集合LinkedList与ArrayList源码分析

一、LinkedList

1、结构，废话不多说吧，直接看条件应该就大概懂了。

transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

主要有三个元素，容量，第一节点，最后节点。每一个node中又包含了前节点跟下一个节点。这个node的构造器很重要，第一个参数是prev节点我个人就叫他前置节点，next我就叫他后置节点。双向链表由此体现。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

2、新增

public boolean add(E e) {
        linkLast(e);
        return true;
    }

void linkLast(E e) {
        final Node<E> l = last;
        //上面node的构造器，重复一遍参数，前置节点，元素，后置节点。
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

首先获取最后一个节点，然后在最后节点上新增节点，判断最后节点是否为空，如果为空设置为第一节点，不为空增加到最后节点后面称为最后节点。size加1，更改次数加1。所以说默认的就是加到末尾。

2.1在指定下标进行新增

public void add(int index, E element) {
 	//检查是否越界等等不截图了很简单
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
	//如果新增index 与size相等 就直接加到后面
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    //succ为之前下标元素，获取之前下标元素的前置节点pred。
    //然后通过构造器建立pred为前置节点，succ(之前下标对应元素)为后置节点的新node。
    //把新node设置为succ的前置节点pred的后置节点。
        void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

3、删除，先判断删除下标是否越界很简单的就不截图了，获取要删除的元素节点，

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

//获取要的元素 这个地方get也会用到
    Node<E> node(int index) {
        // assert isElementIndex(index);
		//与size一半进行比较 
		//虽然取了一半但是还有大大的for循环
        if (index < (size >> 1)) {
            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;
        }
    }

移除元素，获取此元素的pre节点跟next节点。判断pre节点是否为空，为空next节点设置为第一节点，否则此节点的next节点设置为pre节点的next节点。判断next节点是否为空，为空pre节点设置为最后节点，否则pre节点设置为next节点的pre节点。

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

4、获取制定下标元素

public E get(int index) {
  	//同样的先校验
        checkElementIndex(index);
        //上面删除指点元素有哈
        return node(index).item;
    }

二、ArrayList

1、结构是一个Object数组

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        //Object 数组么这不是
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        //哟这个也是长度为空的数组
        //private static final Object[] EMPTY_ELEMENTDATA = {}
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

2、新增

public boolean add(E e) {
    	//数组长度跟新增之后长度进行比较
    	//size+1 就是后面minCapacity 可以先有个印象
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //如果初始长度满足新增
        elementData[size++] = e;
        return true;
    }

首先咱们先看下，这个方法在指定下标新增也会用到哟。

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    //我直接把calculateCapacity方法粘过来
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
	//进行比较看看是不是默认的默认的就是10
	// private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         //private static final int DEFAULT_CAPACITY = 10;
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

	
    private void ensureExplicitCapacity(int minCapacity) {
    //更改次数自增，不重要忽略~
        modCount++;

        // overflow-conscious code
        //数组长度跟新增之后长度进行比较
        if (minCapacity - elementData.length > 0)
        //
            grow(minCapacity);
    }

//扩容集合长度
	//minCapacity 为更新之后长度
    private void grow(int minCapacity) {
        // overflow-conscious code
        //获取原来集合的长度
        int oldCapacity = elementData.length;
        //新长度为原来长度的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
 //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        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);
    }
        private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

应该是很简单吧看着，最后回到数组下标赋值。

public boolean add(E e) {
    	//数组长度跟新增之后长度进行比较
    	//size+1 就是后面minCapacity 可以先有个印象
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //如果初始长度满足新增
        elementData[size++] = e;
        return true;
    }

2.1 在指定下标新增

public void add(int index, E element) {
        rangeCheckForAdd(index);
		//似曾相识 就是上面的那个
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //好了这个 System 已经说明一切了
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
      /*
        从指定的源数组复制数组，从指定位置，到目标数组的指定位置。
        从源中复制阵列组件的子序列由<code>src</code>引用到目标数组的数组由<code>dest</code>引用。
        复制的组件数为等于<code>长度</code>参数。
        组件位于位置<code>srcPos</code>到将源数组中的<code>srcPos+length-1</code>
        复制到位置<code>destPos</code>到目的地的<code>destPos+length-1数组。
        */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

3、指定下标删除

public E remove(int index) {
    //同样的先校验
        rangeCheck(index);

        modCount++;
        //直接把下面的方法粘贴过来
        /*   
         E elementData(int index) {
        return (E) elementData[index]; }
        */
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
        //这个东西再一次出现了
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

4、获取指点下标元素

public E get(int index) {
        rangeCheck(index);
 		/*   也是直接粘贴过来
         E elementData(int index) {
        return (E) elementData[index]; }
        */
        return elementData(index);
    }

list 小总结：

1、LinkedList

没有容量的限制，采用的双向链表的方式。
新增只需要构建新node，更新原来下标元素前置节点的后置节点，跟原来下标元素的前置节点。其实新增节点，更改引用。所以说会快一点。
删除只需要更改原来下标元素前置节点的next，跟原来下标元素后置节点的pre。其实就是更改引用。所以说会快一点。
获取元素需要先取size的一半然后进行遍历。

2、ArrayList

会有容量扩容的机制，采用的Object数组的方式。
新增要判断数组是否需要扩容，然后调用System的方法进行对数据迁移。
删除调用System的方法进行对数据迁移。
直接通过数组下标进行获取。

java 集合LinkedList与ArrayList源码分析

一、LinkedList

二、ArrayList

list 小总结：

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method