list集合

arraylist接口

linkedlist接口

底层基于数组实现，实现了长度可变的数组，其最大特点是内存空间连续，优点是遍历元素和随机访问效率比较高；

①数据是插入有序的
②数据是可以重复的
③可以存储null
④底层数据结构是数组
⑤可以动态扩容的，默认容量是10
⑥扩容是按照原大小的1.5倍进行扩容

    数组

//扩容大小  
int newCapacity = oldCapacity + (oldCapacity >> 1);

Arraylist集合扩容时按照1.5倍进行扩容

add（E e）
1、如果存储数组为空，获取默认的大小值是10
2、如果需要大小超过数组大小、考虑扩容，按照原数组大小的1.5倍扩容
3、通过创建新数组，将元素组大小拷贝到新数组中
4、将新增元素插入最后的size位置并对size进行加1操作

get(int index)

public E get(int index) {
        //检查下标的合法性   0<= index = size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

remove(Object o) 删除

1、ArrayList底层封装数组，提供了丰富API操作
2、存储数据：ArrayList存储的是自定义对象，基本包装类型 数组可以存放自定义类型，包装类型、基类类型（int）
3、ArrayList是可以自动扩容的 ，数组不能自动扩容

1、数据插入有序
2、数据可重复
3、可以存储null
4、底层数据结构是链表

LinkedList是List接口的试下实现类，具有List接口提供的所有方法

public interface Deque extends Queue {
    void addFirst(E e); //将元素添加在队列第一个位置
    void addLast(E e); //将元素添加到最后位置
    boolean offerFirst(E e); //将元素添加在队列第一个位置
    boolean offerLast(E e);//将元素添加到最后位置
    E removeFirst(); //删第一个
    E removeLast(); //删最后一个
    E pollFirst(); //删除
    E pollLast(); //删除
    E getFirst();
    E getLast();
    E peekFirst();  //获取第一个
    E peekLast();   //获取最后一个
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
    void push(E e);
    E pop();
    boolean remove(Object o);
    boolean contains(Object o);
    public int size();
    Iterator iterator();
    Iterator descendingIterator();
}

总结：

底层基于双向链表实现，其最大特点是内存空间不连续，其中元素允许为null，优点是增加元素和删除元素效率比较高；
LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.

①ArrayList基于动态数组，LinkedList基于链表。
②对于增加元素和删除元素LinkedList效率比较高，因为ArrayList要移动元素。
③对于遍历元素和随机访问ArrarList效率比较高，因为LinkedList要移动指针。