说⼀下ArrayList和LinkedList区别

1.1. ⾸先，他们的底层数据结构不同，ArrayList底层是基于数组实现的，LinkedList底层是基于链表实现的

1.2. 由于底层数据结构不同，他们所适⽤的场景也不同，ArrayList更适合随机查找，

        LinkedList更适合删除和添加，查询、添加、删除的时间复杂度不同

1.3. 另外ArrayList和LinkedList都实现了List接⼝，但是LinkedList还额外实现了Deque接⼝，所以

        LinkedList还可以当做队列来使⽤

 2.1.ArrayList实现了List接口

        public class ArrayList<E> extends AbstractList<E> implements List<E>{...}


 2.2.LinkedList实现了List和Deque接口，所以LinkedList可以当做双端队列来进行使用：因为Deque接口中有addFirst/addLast/getFirst/getLast等操作

        public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>{...}

1.arrayList.get(1);

     底层代码：基于下标获取

             public E get(int index) {

                rangeCheck(index);

                return elementData(index);

             }

2.linkedList.get(1);

     底层代码:基于链表的操作，所以获取在底层是进行循环获取的！

             public E get(int index) {

                ...

                Node<E> x = last;

                for (int i = size - 1; i > index; i--)

                    x = x.prev;

                return x;

                ...

            } 

1.arrayList的添加

    1.1添加元素：需要考虑底层数组的扩容，效率较慢

          arrayList.add(1);

    1.2：在指定的位置1，添加元素1：底层涉及到数组的移动，因为1位置后的数据都得往后移动，效率较慢

          arrayList.add(1,1);

2.linkedList的添加

     2.1添加元素：在末尾添加元素，因为底层是链表，所以添加速度较快

            linkedList.add(1);

     2.2：在指定的位置1，添加元素1:因为底层是链表，需要先循环找到要添加的位置，

如果下标数字过大，等于循环次数越多，效率就会越慢

下标数字小，循环次数小，效率快！所以此处的效率是决定于插入位置的数字大小

         linkedList.add(1,1);