您的位置: 首页  >  文章  >  java_集合体系之List体系总结、应用场景

java_集合体系之List体系总结、应用场景

分类: 文章 • 2023-11-26 18:10:22

感谢原作者！！

摘要：

            总结很重要、他能客观的体现出你对这个体系的理解程度、首先要对整体的结构框架要掌握、再细化到每个分支的特点、再比较不同分支之间的相同点、不同点、再根据他们不同的特性分析他们的应用场景。

 

一：List的整体框架图

 java_集合体系之List体系总结、应用场景


线条简单说明：

        1、上图中虚线且无依赖字样、说明是直接实现的接口

        2、虚线但是有依赖字样、说明此类依赖与接口、但不是直接实现接口

        3、实线是继承关系、类继承类、接口继承接口

类或接口说明：

        1、Collection：高度抽象出来的集合、定义某一类集合所具有的基本的方法、标准。

        2、Iterable：标识性接口、要求子类提供获取Iterator方法、并且要实现Iterator具有的几个方法。

        3、Iterator：迭代器、用于迭代Collection中元素、要求子类必须实现获取Iterator的方法、

        4、ListIterator：用于迭代List集合的迭代器、要求List子类必须实现获取ListIterator方法、并且实现其必须方法。

        5、List：以队列的形式存储、操作元素、定义了这种形式的集合所具有的基本方法、以及方法的定义。要求List实现类集合中每个元素都有索引、索引值从0开始、

        6、Queue：以队列的数据结构存储、操作元素、Queue对于插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。

        7、Deque：实现Queue、使子类可以以双向链表的数据结构形式存储、操作数据、从这可以看出其子类的灵活性较大。

        8、Enumeration：枚举、用于Vector及其子类迭代元素、他避免了fail-fast机制、使得Vector及其子类在迭代元素的时候可以保证线程安全。

        9、AbstractCollection：Collection的实现类、要求需要实现Collection接口的类都必须从它继承、目的是用于简化编程。

        10、           AbstractList：继承AbstractCollection、实现List接口中定义方法、目的也是简化编程、并且其内部提供了获取Iterator、ListIterator的方法。

        11、           AbstractSequencedList：继承AbstractList、使得List支持有序队列、比如链表形式存储操作元素。

        12、           ArrayList：继承AbstractList、以动态数组的形式存储、操作元素、

        13、           LinkedList：继承AbstractSequencedList、实现Deque、List接口、以双向链表的形式存储、操作元素。

        14、           Vector：继承AbstractList、以动态数组的形式存储、操作元素、线程安全

        15、           Stack：继承Vector、在Vector的基础上新增以栈的形式存储、操作元素。

 

二：LinkedList与ArrayList


        1、相同之处

                a）都直接或者间接继承了AbstractList、都支持以索引的方式操作元素

 

                b）都不必担心容量问题、ArrayList是通过动态数组来保存数据的、当容量不足时、数组会自动扩容、而LinkedList是以双向链表来保存数据的、不存在容量不足的问题

 

                c） 都是线程不安全的、一般用于单线程的环境下、要想在并发的环境下使用可以使用Collections工具类包装。

        2、不同之处


        a）ArrayList是通过动态数组来保存数据的、而LinkedList是以双向链表来保存数据的

 

        b）相对与ArrayList而言、LinkedList实现了Deque接口、Deque继承了Queue接口、同时LinkedList继承了AbstractSequencedList类、使得LinkedList在保留使用索引操作元素的功能的同时、也实现了双向链表所具有的功能、这就决定了LinkedList的特定

      

        c）对集合中元素进行不同的操作效率不同、LinkedList善于删除、添加元素、ArrayList善于查找元素。本质就是不同数据结构之间差异。

 

三：ArrayList与Vector


        1、相同之处：

                a）    都是继承AbstractList、拥有相同的方法的定义、

 

                b）内部都是以动态数组来存储、操作元素的、并且都可以自动扩容。

 

        2、不同之处：

                a）   线程安全：ArrayList是线程不安全的、适用于单线程的环境下、Vector是线程安全的、使用与多线程的环境下。

 

                b）构造方法：Vector有四个构造方法、比ArrayList多一个可以指定每次扩容多少的构造方法

 

                c） 扩容问题：每当动态数组元素达到上线时、ArrayList扩容为：“新的容量”=“(原始容量x3)/2 + 1”、 而Vector的容量增长与“增长系数有关”，若指定了“增长系数”，且“增长系数有效(即，大于0)”；那么，每次容量不足时，“新的容量”=“原始容量+增长系数”。若增长系数无效(即，小于/等于0)，则“新的容量”=“原始容量 x 2”。

 

                d）    效率问题：因为Vector要同步方法、这个是要消耗资源的、所以效率会比较低下

 

                e）Vector为摆脱fail-fast机制、自己内部多提供了一种迭代方法Enumeration、

 

四：LinkedList、ArrayList、Vector、Stack、Array


        1、不同操作的效率对比        

                关于上面四个集合加一个数组、在这里给出一个表格用于表示他们的不同的操作的效率的排名、这样更直观、


 

实现机制

随机访问

迭代操作

插入操作

删除操作

数组

连续内存区保护元素

1

不支持

不支持

不支持

ArrayList

以数组保存元素

2

2

2

2

Vector

以数组保存元素

3

3

3

3

Stack

以数组保存元素

3

3

3

3

LinkedList

以链表保存元素

4

1

1

1

 

        通过实例来验证上面表格的内容、由于数组比较特殊、他是牺牲的长度的变化直接在内存中开辟空间来存储元素、所以查询效率是毋庸置疑的、同时由于size一旦确定就不能改变、所以插入删除不支持。所以下面验证没有关于Array的的验证        

 

        2、示例：

 

[java] view plain copy
 java_集合体系之List体系总结、应用场景java_集合体系之List体系总结、应用场景
  1. package com.chy.collection.example;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.Iterator;  
  5. import java.util.LinkedList;  
  6. import java.util.List;  
  7. import java.util.Stack;  
  8. import java.util.Vector;  
  9.   
  10. public class EfficiencyTest {  
  11.       
  12.     private static ArrayList<String> arrayList = new ArrayList<String>();  
  13.     private static Vector<String> vector = new Vector<String>();  
  14.     private static Stack<String> stack = new Stack<String>();  
  15.     private static LinkedList<String> linkedList = new LinkedList<String>();  
  16.   
  17.     /** 
  18.      * 测试插入方法（每次都将新增加的元素插入到集合开始处）、注意不要写成 add(Object o)方法、具体原因自己分析 
  19.      */  
  20.     private static void testInsert(){  
  21.         testInsert(arrayList);  
  22.         testInsert(vector);  
  23.         testInsert(stack);  
  24.         testInsert(linkedList);  
  25.     }  
  26.       
  27.     /** 
  28.      * 测试随机访问效率 
  29.      */  
  30.     private static void testRandomAccess(){  
  31.         testRandomAccess(arrayList);  
  32.         testRandomAccess(vector);  
  33.         testRandomAccess(stack);  
  34.         testRandomAccess(linkedList);  
  35.     }  
  36.       
  37.     /** 
  38.      * 测试Iterator迭代效率  
  39.      */  
  40.     private static void testIterator(){  
  41.         testIterator(arrayList);  
  42.         testIterator(vector);  
  43.         testIterator(stack);  
  44.         testIterator(linkedList);  
  45.     }  
  46.       
  47.     /** 
  48.      * 测试删除效率 
  49.      */  
  50.     private static void testDelete(){  
  51.         testDelete(arrayList);  
  52.         testDelete(vector);  
  53.         testDelete(stack);  
  54.         testDelete(linkedList);  
  55.     }  
  56.       
  57.     private static void testInsert(List<String> list){  
  58.         long start = currentTime();  
  59.         for (int i = 0; i < 10000; i++) {  
  60.             list.add(0,"a");  
  61.         }  
  62.         long end = currentTime();  
  63.         System.out.println("the add method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");  
  64.     }  
  65.       
  66.     private static void testRandomAccess(List<String> list){  
  67.         long start = currentTime();  
  68.         for (int i = 0; i < list.size(); i++) {  
  69.             list.get(i);  
  70.         }  
  71.         long end = currentTime();  
  72.         System.out.println("the random access method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");  
  73.     }  
  74.       
  75.     private static void testIterator(List<String> list){  
  76.         long start = currentTime();  
  77.         Iterator<String> it = list.iterator();  
  78.         while(it.hasNext()){  
  79.             it.next();  
  80.         }  
  81.         long end = currentTime();  
  82.         System.out.println("the iterator method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");  
  83.     }  
  84.       
  85.     private static void testDelete(List<String> list){  
  86.         long start = currentTime();  
  87.         for (int i = 0; i < 10000; i++) {  
  88.             if(!list.isEmpty()){  
  89.                 list.remove(0);  
  90.             }  
  91.         }  
  92.         long end = currentTime();  
  93.         System.out.println("the delete method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");  
  94.     }  
  95.       
  96.     private static long currentTime(){  
  97.         return System.currentTimeMillis();  
  98.     }  
  99.       
  100.     public static void main(String[] args) {  
  101.         testInsert();  
  102.         System.out.println("==========================================================");  
  103.         testRandomAccess();  
  104.         System.out.println("==========================================================");  
  105.         testIterator();  
  106.         System.out.println("==========================================================");  
  107.         testDelete();  
  108.     }  
  109. }  

        运行结果：

[java] view plain copy
 java_集合体系之List体系总结、应用场景java_集合体系之List体系总结、应用场景
  1. the add method of java.util.ArrayList use time : 32ms  
  2. the add method of java.util.Vector use time : 47ms  
  3. the add method of java.util.Stack use time : 31ms  
  4. the add method of java.util.LinkedList use time : 15ms  
  5. ==========================================================  
  6. the random access method of java.util.ArrayList use time : 15ms  
  7. the random access method of java.util.Vector use time : 16ms  
  8. the random access method of java.util.Stack use time : 17ms  
  9. the random access method of java.util.LinkedList use time : 47ms  
  10. ==========================================================  
  11. the iterator method of java.util.ArrayList use time : 16ms  
  12. the iterator method of java.util.Vector use time : 15ms  
  13. the iterator method of java.util.Stack use time : 17ms  
  14. the iterator method of java.util.LinkedList use time : 16ms  
  15. ==========================================================  
  16. the delete method of java.util.ArrayList use time : 47ms  
  17. the delete method of java.util.Vector use time : 31ms  
  18. the delete method of java.util.Stack use time : 32ms  
  19. the delete method of java.util.LinkedList use time : 15ms  

        不同的运行环境、差异可能比较大。


        3、差异原因分析：

                在这里不会主要讨论所有的差异、而是通过源码的方式分析LinkedList与Arraylist、ArrayList与Vector在随机访问、插入、删除元素方面的差异原因、至于迭代Iterator、他们都是用从AbstractList继承的获取Iterator方法、差异不大、不再比较。

                  ArrayList与LinkedList

                a）ArrayList的随机访问效率高于LinkedList：

                        随机访问是通过索引去查找元素的、LinkedList关于获取指定索引处值的源码：

[java] view plain copy
 java_集合体系之List体系总结、应用场景java_集合体系之List体系总结、应用场景
  1. /** 获取index处的元素*/  
  2.     public E get(int index) {  
  3.         return entry(index).element;  
  4.     }  
  5.     /**  获取双向链表LinkedList中指定位置的节点、是LinkedList实现List中通过index操作元素的关键*/  
  6.     private Entry<E> entry(int index) {  
  7.         if (index < 0 || index >= size)  
  8.             throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);  
  9.         Entry<E> e = header;  
  10.         if (index < (size >> 1)) {  
  11.             for (int i = 0; i <= index; i++)  
  12.                 e = e.next;  
  13.         } else {  
  14.             for (int i = size; i > index; i--)  
  15.                 e = e.previous;  
  16.         }  
  17.         return e;  
  18.     }  

关于获取指定索引处的值的源码：

[java] view plain copy
 java_集合体系之List体系总结、应用场景java_集合体系之List体系总结、应用场景
  1.    /** 检测下标是否越界*/  
  2.    private void RangeCheck(int index) {  
  3. if (index >= size)  
  4.     throw new IndexOutOfBoundsException(  
  5.     "Index: "+index+", Size: "+size);  
  6.    }  
  7.    /** 获取ArrayList中索引为index位置的元素*/  
  8.    public E get(int index) {  
  9.     RangeCheck(index);  
  10.   
  11.     return (E) elementData[index];  
  12.    }  

                对比两者源码可以看出、LinkedList获取指定索引处的值是通过二分法先确定索引所在范围之后、在逐个查找、直到找到指定索引处、并且对每个索引都是如此、相比于ArrayList直接定位到index处的值来讲、无疑是非常浪费时间、消耗资源的、

 

                b）ArrayList的插入、删除操作效率低于LinkedList的原因：

                                 对于指定index处的插入、删除、ArrayList和LinkedList都是先通过索引查找到指定位置、然后进行下一步的插入删除操作、上面我们知道LinkedList是先通过二分法查找index范围再确定index具体位置、但是ArrayList是直接定位到index处、为什么LinkedList反而快？依然通过源码找原因。

ArrayList关于指定位置的元素的插入：

[java] view plain copy
 java_集合体系之List体系总结、应用场景java_集合体系之List体系总结、应用场景
  1.   /** 
  2.    * 确保此ArrayList的最小容量能容纳下参数minCapacity指定的容量、 
  3.    * 1、minCapacity大于原来容量、则将原来的容量增加(oldCapacity * 3)/2 + 1; 
  4.    * 2、若minCapacity仍然大于增加后的容量、则使用minCapacity作为ArrayList容量 
  5.    * 3、若minCapacity不大于增加后的容量、则使用增加后的容量。 
  6.    */  
  7.   public void ensureCapacity(int minCapacity) {  
  8. modCount++;  
  9. int oldCapacity = elementData.length;  
  10. if (minCapacity > oldCapacity) {  
  11.     Object oldData[] = elementData;  
  12.     int newCapacity = (oldCapacity * 3)/2 + 1;  
  13.         if (newCapacity < minCapacity)  
  14.             newCapacity = minCapacity;  
  15.            // minCapacity is usually close to size, so this is a win:  
  16.            elementData = Arrays.copyOf(elementData, newCapacity);  
  17. }  
  18.   }  
  19.   /** 将指定元素添加到指定的索引处 、 
  20.    *    注意： 
  21.    *    1、如果指定的index大于Object[] 的size或者小于0、则抛IndexOutOfBoundException 
  22.    *    2、检测Object[]是否需要扩容 
  23.    *    3、 将从index开始到最后的元素后移一个位置、 
  24.    *    4、将新添加的元素添加到index去。 
  25.    */  
  26.   public void add(int index, E element) {  
  27. if (index > size || index < 0)  
  28.     throw new IndexOutOfBoundsException(  
  29.     "Index: "+index+", Size: "+size);  
  30.   
  31. ensureCapacity(size+1);  // Increments modCount!!  
  32. <span style="color:#ff0000;">System.arraycopy(elementData, index, elementData, index + 1,  
  33.          size - index);</span>  
  34. elementData[index] = element;  
  35. size++;  
  36.   }  

LinkedList关于指定位置的元素的插入：

 

[java] view plain copy
 java_集合体系之List体系总结、应用场景java_集合体系之List体系总结、应用场景
  1.   /** 在index前添加节点，且节点的值为element*/  
  2.   public void add(int index, E element) {  
  3.      <span style="color:#ff0000;"> addBefore(element, (index==size ? header : entry(index)));</span>  
  4.   }  
  5.   /**  获取双向链表LinkedList中指定位置的节点、是LinkedList实现List中通过index操作元素的关键*/  
  6.   private Entry<E> <span style="color:#ff0000;">entry(int index) </span>{  
  7.       if (index < 0 || index >= size)  
  8.           throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);  
  9.       Entry<E> e = header;  
  10.       if (index < (size >> 1)) {  
  11.           for (int i = 0; i <= index; i++)  
  12.               e = e.next;  
  13.       } else {  
  14.           for (int i = size; i > index; i--)  
  15.               e = e.previous;  
  16.       }  
  17.       return e;  
  18.   }  
  19. //新建节点、节点值是e、将新建的节点添加到entry之前  
  20.   private Entry<E> <span style="color:#ff0000;">addBefore(E e, Entry<E> entry)</span> {  
  21.     //觉得难理解的可以先花个几分钟看一下链式结构资料、最好是图片形式的  
  22.     //新建节点实体  
  23. Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  
  24. //将参照节点原来的上一个节点（即插在谁前面的）的下一个节点设置成newEntry  
  25. newEntry.previous.next = newEntry;  
  26. //将参照节点（即插在谁前面的）的前一个节点设置成newEntry  
  27. newEntry.next.previous = newEntry;  
  28. size++;  
  29. modCount++;  
  30. return newEntry;  
  31.   }  

         对比上面代码可以看出来ArrayList每当插入一个元素时、都会调用System.arraycopy()将指定位置后面的所有元素后移一位、重新构造一个数组、这是比较消耗资源的、而LinkedList是直接改变index前后元素的上一个节点和下一个节点的引用、而不需要动其他的东西、所以效率很高。

        ArrayList与Vector：

                ArrayList、Vector都是继承与AbstractList、并且在类结构上没有多少差异、但是因为Vector要同步方法、所以在性能上不如ArrayList、从源码也可以看出Vector许多方法都是使用关键字synchronized修饰的。不再贴源码

 

总结：


              学以致用、最后总结下上述List集合体系的各个类的使用环境：

              1、当需要对集合进行大量的查询时、并且是单线程环境下使用ArrayList

              2、当需要对集合进行大量添加、删除时、并且是单线程环境下使用LinkedList、

              3、当多线程时、需要对集合进行大量的查询时、可以考虑使用Vector或者Stack、但是不建议、我们可以使用多次提到的Collections类包装。


相关推荐