让我们看下集合（容器）所属继承关系

Relationship

其中，我们首先来看Collection接口中实现的方法。

Collection接口

其中实现的方法都比较常见，可以打开源码看看，比如size就返回了容器中元素的数量等等。。。

接下来讲讲List接口下的几个实现类。

list接口常用的实现类有3个：ArrayList，LinkedList和Vector。

• ArrayList底层是一个数组，相当于一个线性表，和数组不同的，ArrayList可以通过数组扩容方式可以存放任意数量的对象。他的特点是查找效率高，增删效率低，线程不安全。使用的比较多。

数组扩容实现方式在jdk1.8中为：如果存储的数据超过默认的大小（10），会新建一个数组，数组大小增加原数组大小的一半（10+10/2），并将原数组的元素复制到新数组中，再把指向原数组的地址指向新数组，原数组就被java的垃圾回收机制回收了，并使用新数组存储数据。实现代码如下：

 public void add(E element){
        if(size==elementDate.length){
            /*
             * 开始扩容
             */
            Object[] newArray=new Object[elementDate.length+(elementDate.length>>1)];
            System.arraycopy(elementDate, 0, newArray, 0, elementDate.length);
            elementDate=newArray;
            
            
        }
        elementDate[size++]=element;
    }

• LinkedList底层是个链表，可以看成一个双向链表，他的特点是查找效率低（需要依次遍历），增删效率高。

实现对 LinkedList的查找可以通过查找的索引如果小于链表的长度的一半可以从头部开始遍历，大于链表的长度的一半从尾部开始遍历部分提高算法效率。实现代码如下：

private Node getNode(int index){ //通过index获得该节点
        checkRange(index);    //判断index是否合法
        Node temp=null;
        if(index<=(size>>2)){   //size>>2 相当于size/2
            temp=first;
            for(int i=0;i<index;i++){
                temp=temp.next;
            }           
        }else{
            temp=last;
            for(int i=size-1;i>index;i--){
                temp=temp.previous;
        }
        
      }
        return temp;
    }

• Vector底层是用数组实现的List，相关方法都加了同步检查，因此，“线程安全，效率低”。

对于list接口常用的3个实现类总结可以为：

如何选用ArrayList、LInked List、Vector