ArrayList、LinkedList、Vector

青旅半醒 2021-11-29 05:16 320阅读 0赞

**1.相同点**  
（1）都实现了List接口  
（2）存储数据的特点相同：存储有序的，可重复的数据  
**2.不同点**  
ArrayList：作为List接口的主要实现类，线程不安全，效率高，底层使用Object\[\] elementData(数组)存储  
LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储  
Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object\[\] elementData(数组)存储

**3.源码分析**

（1）ArrayList（jdk7）  
ArrayList list = new ArrayList();//底层创建了长度为10的Object\[\] elementData数组;  
list.add(123);//elementData\[0\]=new Integer(123);  
…  
list.add(11);

1.调用ensureExplicitCapacity()方法判断数组容量是否够
    2.当elementData数组的容量不足时，就调用grow()方法进行扩容
    3.默认情况下，扩容为原来容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1)
    4.同时将原有数组中的数据复制到新的数组中， elementData = Arrays.copyOf(elementData, newCapacity)

**总结：建议开发中使用带参的构造器：ArrayList list = new ArrayList(initalCapacity)，不会造成容量不够而去扩容，效率高一些**

（2）ArrayList（jdk8）  
ArrayList list = new ArrayList();

private static final Object[] EMPTY_ELEMENTDATA = {};
     transient Object[] elementData;
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//得到单例的空数组{}，并没有创建长度为10的数组

list.add(123);//第一次调用add，给数组分配长度为10的空间，并将数据添加进去  
…  
后续的添加与扩容与jdk7相同  
**总结：jdk7中的ArrayList的对象的创建类似于单例的饿汉式，而jdk8的ArrayList的对象类似于单例的懒汉式，延迟了数组的创建，节省内存**

（3）LinkedList  
采用私有静态内部类Node表示链表中的结点

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;
            }
        }

LinkedList的基本使用

LinkedList list = new LinkedList();//内部声明了Node类型的first和last属性，默认值为null
    list.add(12);//将1233封装到Node中，创建了Node对象

总结：Node的定义体现LinkedList的双向链表的说法  
(4)Vector：调用空参构造器，底层创建了长度为10的数组，在扩容方面，默认扩容为原先的2倍