List的知识整理

清疚 2022-01-25 20:04 307阅读 0赞

## 1.List的知识整理 ##

List是一个接口，而ArrayList是List接口的一个实现类。 ArrayList类继承并实现了List接口。说白了就是父子关系，当然接口是不能帮助我们干活的，我们可以使用Java中的多态去创建它的子类对象，让它的父类引用指向子类对象。  
**我们使用List作为一种变量来存储ArrayList类的对象，使用new关键字创建。这称为接口编程。**  
实际上，在需要声明引用变量的任何地方，都应该使用超类型，例如Map用于传递HashMap，Set用于传递HashSet和List用于传递ArrayList，LinkedList或Vector。您应该在返回类型的方法，参数类型等上使用interface作为类型，  
**现在有一个大问题，你为什么要那样做？**  
利用了Java的多态性。如果您使用接口而不是将来如果新的实现已发布，那么您不需要更改您的程序。例如，无论您传递LinkedList，Vector还是ArrayList，使用List编写的任何程序都将按预期工作，因为它们都实现了List接口，它们遵守List接口公开的契约。 唯一的区别在于性能，实际上是改变的驱动因素。  
**你应该在方法参数上使用接口类型**

public void sort(List <?extends Comparable>input){
    		//对列表进行排序的逻辑
    }

**并在返回类型的方法上使用接口类型**

public  List <Employee> getEmployees（int departmentId）{
            //返回给定部门员工的逻辑 
    }

**如果将ArrayList的对象存储到ArrayList的引用类型中，如下所示，那么如果传递LinkedList，则代码将不起作用，因为ArrayList不是LinkedList。**

说到这里再扩充一点知识：

## **2.数组、ArrayList、List和LinkedList的区别** ##

**数组**:许多集合的底层实现就使用数组完成。  
**优点**：在内存中时**连续的，速度较快，操作简单。**  
**缺点**：定义数组时要**定义其长度**，不是很灵活，过长过短都会造成问题。**不方便进行数据的添加、插入和移除。**  
**（1）数组的定义方式**

.数组类型［］ 数组名=new 数组类型［数组长度］;
    数组类型［］ 数组名={数组0，数组1，数组2，数组3.....};
    数组类型［］ 数组名=new 数组类型［］{数组0，数组1，数组2.......};

*  数组下标（从0开始）超出数组长度，数组越界异常（运行时异常）
 *  数组中每个元素都有默认值，默认值是该数据类型默认值
 *  数组名称.length（属性）：取得数组长度  
    **（2）集合ArrayList**  
    **优点**：命名空间System.Collections下的一部分。大小是动态扩充与收缩的。在声明ArrayList对象时不需要指定它的长度。ArrayList继承了IList接口，可以很方便的进行数据的添加、插入和移除.  
    **缺点**：当向集合插入不同类型的数据后（ArrayList将数据当作object存储），在进行数据处理时容易出现类型不匹配的错误，使用时需要进行类型转换处理，存在装箱与拆箱操作，造成性能大量损耗的现象。

ArrayList list = new ArrayList();  //最常见的创建方式

**（3）泛型List**  
**优点**：与集合ArrayList类似且继承IList接口，在声明List集合时也要声明集合内部数据的对象类型，避免了装箱和拆箱的问题。

List<int> list=new List<int>();

## 3.**这里重点提一下ArrayList和LinkedList的使用和区别：** ##

**LinkedList**：循环双向链表数据结构，由一系列表项连接而成。一个表项总是包含3个部分：**元素内容，前驱表和后驱表，如图所示：**  
![在这里插入图片描述][20190528203342140.png]  
在下图展示了一个包含3个元素的LinkedList的各个表项间的连接关系。在JDK的实现中，无论LikedList是否为空，链表内部都有一个header表项，它既表示链表的开始，也表示链表的结尾。表项header的后驱表项便是链表中第一个元素，表项header的前驱表项便是链表中最后一个元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70]  
下面以增加和删除元素为例比较ArrayList和LinkedList的不同之处：  
**1）增加元素到列表尾端：**  
在ArrayList中增加元素到队列尾端的代码如下：

public boolean add(E e){
       ensureCapacity(size+1);    	//确保内部数组有足够的空间
       elementData[size++]=e;		//将元素加入到数组的末尾，完成添加
       return true;      
    }

ArrayList中add()方法的性能决定于ensureCapacity()方法。ensureCapacity()的实现如下：

public vod ensureCapacity(int minCapacity){
      modCount++;
      int oldCapacity=elementData.length;
      if(minCapacity>oldCapacity){    				//如果数组容量不足，进行扩容
          Object[] oldData=elementData;
          int newCapacity=(oldCapacity*3)/2+1;   	//扩容到原始容量的1.5倍
          if(newCapacitty<minCapacity)   			//如果新容量小于最小需要的容量，则使用最小
                                                    //需要的容量大小
             newCapacity=minCapacity ;  			//进行扩容的数组复制
             elementData=Arrays.copyof(elementData,newCapacity);
      }
    }

可以看到，只要ArrayList的当前容量足够大，add()操作的效率非常高的。只有当ArrayList对容量的需求超出当前数组大小时，才需要进行扩容。扩容的过程中，会进行大量的数组复制操作。而数组复制时，最终将调用System.arraycopy()方法，因此add()操作的效率还是相当高的。  
LinkedList 的add()操作实现如下，它也将任意元素增加到队列的尾端：

public boolean add(E e){
       addBefore(e,header);//将元素增加到header的前面
       return true;
    }

其中addBefore()的方法实现如下：

private Entry<E> addBefore(E e,Entry<E> entry){
         Entry<E> newEntry = new Entry<E>(e,entry,entry.previous);
         newEntry.provious.next=newEntry;
         newEntry.next.previous=newEntry;
         size++;
         modCount++;
         return newEntry;
    }

可见，LinkeList由于使用了链表的结构，因此不需要维护容量的大小。从这点上说，它比ArrayList有一定的性能优势，然而，每次的元素增加都需要新建一个Entry对象，并进行更多的赋值操作。在频繁的系统调用中，对性能会产生一定的影响。  
**（2）增加元素到列表任意位置**  
除了提供元素到List的尾端，List接口还提供了在任意位置插入元素的方法：void add(int index,E element);  
由于实现的不同，ArrayList和LinkedList在这个方法上存在一定的性能差异，由于ArrayList是基于数组实现的，而数组是一块连续的内存空间，如果在数组的任意位置插入元素，必然导致在该位置后的所有元素需要重新排列，因此，其效率相对会比较低。  
以下代码是ArrayList中的实现：

public void add(int index,E element){
       if(index>size||index<0)
          throw new IndexOutOfBoundsException(
            "Index:"+index+",size: "+size);
             ensureCapacity(size+1);
             System.arraycopy(elementData,index,elementData,index+1,size-index);
             elementData[index] = element;
             size++;
    }

可以看到每次插入操作，都会进行一次数组复制。而这个操作在增加元素到List尾端的时候是不存在的，大量的数组重组操作会导致系统性能低下。并且插入元素在List中的位置越是靠前，数组重组的开销也越大。  
而LinkedList此时显示了优势：

public void add(int index,E element){
       addBefore(element,(index==size?header:entry(index)));
    }

可见，对LinkedList来说，在List的尾端插入数据与在任意位置插入数据是一样的，不会因为插入的位置靠前而导致插入的方法性能降低。  
**（3）删除任意位置元素**  
对于元素的删除，List接口提供了在任意位置删除元素的方法：

public E remove(int index);

对ArrayList来说，remove()方法和add()方法是雷同的。在任意位置移除元素后，都要进行数组的重组。ArrayList的实现如下：

public E remove(int index){
       RangeCheck(index);
       modCount++;
       E oldValue=(E) elementData[index];
      int numMoved=size-index-1;
      if(numMoved>0)
         System.arraycopy(elementData,index+1,elementData,index,numMoved);
         elementData[--size]=null;
         return oldValue;
    }

可以看到，在ArrayList的每一次有效的元素删除操作后，都要进行数组的重组。并且删除的位置越靠前，数组重组时的开销越大。

public E remove(int index){
      return remove(entry(index));         
    }
    private Entry<E> entry(int index){
      if(index<0 || index>=size)
          throw new IndexOutBoundsException("Index:"+index+",size:"+size);
          Entry<E> e= header;
          if(index<(size>>1)){//要删除的元素位于前半段
             for(int i=0;i<=index;i++)
                 e=e.next;
         }else{
             for(int i=size;i>index;i--)
                 e=e.previous;
         }
             return e;
    }

在LinkedList的实现中，首先要通过循环找到要删除的元素。如果要删除的位置处于List的前半段，则从前往后找；若其位置处于后半段，则从后往前找。因此无论要删除较为靠前或者靠后的元素都是非常高效的；但要移除List中间的元素却几乎要遍历完半个List，在List拥有大量元素的情况下，效率很低。  
**（4）容量参数**  
容量参数是ArrayList和Vector等基于数组的List的特有性能参数。它表示初始化的数组大小。当ArrayList所存储的元素数量超过其已有大小时。它便会进行扩容，数组的扩容会导致整个数组进行一次内存复制。因此合理的数组大小有助于减少数组扩容的次数，从而提高系统性能。

public  ArrayList(){
      this(10);  
    }
    public ArrayList (int initialCapacity){
       super();
       if(initialCapacity<0)
           throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity)
          this.elementData=new Object[initialCapacity];
    }

ArrayList提供了一个可以制定初始数组大小的构造函数：

public ArrayList(int initialCapacity)

现以构造一个拥有100万元素的List为例，当使用默认初始化大小时，其消耗的相对时间为125ms左右，当直接制定数组大小为100万时，构造相同的ArrayList仅相对耗时16ms。  
**（5）遍历列表**  
遍历列表操作是最常用的列表操作之一，**在JDK1.5之后，至少有3中常用的列表遍历方式：forEach操作，迭代器和for循环。**

String tmp;
    	long start=System.currentTimeMills();    //ForEach 
    			for(String s:list){
    			    tmp=s;
    			}
    		System.out.println("foreach spend:"+(System.currentTimeMills()-start));
    			start = System.currentTimeMills();
    				for(Iterator<String> it=list.iterator();it.hasNext();){    
    				   tmp=it.next();
    				}
    			System.out.println("Iterator spend;"+(System.currentTimeMills()-start));
    			start=System.currentTimeMills();
    			int size=;list.size();
    				for(int i=0;i<size;i++){                     
    				    tmp=list.get(i);
    				}
    			System.out.println("for spend;"+(System.currentTimeMills()-start));

构造一个拥有100万数据的ArrayList和等价的LinkedList，使用以上代码进行测试，测试结果的相对（来自互联网统计）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 1]  
可以看到，**最简便的ForEach循环并没有很好的性能表现，综合性能不如普通的迭代器，而是用for循环通过随机访问遍历列表时，ArrayList表项很好，但是LinkedList的表现却无法让人接受，甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时，总会进行一次列表的遍历操作。性能非常差，应避免使用。**

[20190528203342140.png]: /images/20220126/afabf325a38542fa9ce0123967669329.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70]: /images/20220126/153b6e5ca8d04ff99aff8e1499a88f70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 1]: /images/20220126/a3d90d64442f4f149d058607ce43b63b.png