devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

ArrayList、Vector和LinkedList的区别及使用场景

作者：从前慢现在也慢 | 2024-03-27 05:08:52

赞

踩

arraylist、vector和linkedlist的区别及使用场景

一、前言

ArrayList、Vector和LinkedList都是实现了List接口（允许数据重复）的容器类，它们都能对元素做增删改查的操作。

二、具体介绍

  • ArrayList

ArrayList是基于数组实现的，采用懒加载策略（第一次add时才初始化内部数组，默认初始化大小为10）。它允许对元素的快速随机访问以及在链表尾部进行插入或删除元素操作。但是当随机插入元素时，如果此时数组大小已经不能满足再插入元素时就会进行扩容操作【扩容为原来集合容量的1.5倍】，然后将已插入元素复制到新的存储空间中。如果从中间插入或删除数据势必会导致大量数据的复制，搬移等，这样的话代价会很高。由此看来，ArrayList适合随机访问，而不适合插入和删除。采用异步处理，线程不安全，性能较高

  1. /**
  2.      * The array buffer into which the elements of the ArrayList are stored.
  3.      * The capacity of the ArrayList is the length of this array buffer. Any
  4.      * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  5.      * will be expanded to DEFAULT_CAPACITY when the first element is added.
  6.      */
  7. 	 //ArrayList的元素是存储在缓冲数组中的，并且ArrayList的容量就是缓冲数组的长度
  8. 	 //任何一个属性值elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的ArrayList都会在第一次添加元素的时候扩容为默认容量DEFAULT_CAPACITY
  9.     transient Object[] elementData; // non-private to simplify nested class access
  10. 	
  11. 	/**
  12.      * The size of the ArrayList (the number of elements it contains).
  13.      *
  14.      * @serial	
  15.      */
  16. 	 //ArrayList的大小（所含元素的个数）
  17.     private int size;
  18. 	
  19. 	 /**
  20.      * Default initial capacity.
  21.      */
  22. 	 //默认的容量
  23.     private static final int DEFAULT_CAPACITY = 10;
  24. 	
  25. 	 /**
  26.      * Shared empty array instance used for default sized empty instances. We
  27.      * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
  28.      * first element is added.
  29.      */
  30.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  31. 	
  32. 	/**
  33.      * Constructs an empty list with an initial capacity of ten.
  34.      */
  35. 	 //构造一个空集合
  36.     public ArrayList() {
  37.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  38.     }
  39. 	
  40. 	
  41. 	/**
  42.      * Appends the specified element to the end of this list.
  43.      *
  44.      * @param e element to be appended to this list
  45.      * @return <tt>true</tt> (as specified by {@link Collection#add})
  46.      */
  47. 	 //向集合尾部添加特定元素
  48.     public boolean add(E e) {
  49.         ensureCapacityInternal(size + 1);  // Increments modCount!!
  50.         elementData[size++] = e;
  51.         return true;
  52.     }
  53. 	
  54. 	private void ensureCapacityInternal(int minCapacity) {
  55. 		//第一次插入元素的情况，此时才开始初始化数组，长度为DEFAULT_CAPACITY（10）
  56. 		//minCapacity=Math.max(10,1)=10;
  57.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  58.             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  59.         }
  60.  
  61.         ensureExplicitCapacity(minCapacity);
  62.     }
  63. 	
  64. 	/**
  65.      * The number of times this list has been <i>structurally modified</i>.
  66.      * Structural modifications are those that change the size of the
  67.      * list, or otherwise perturb it in such a fashion that iterations in
  68.      * progress may yield incorrect results.
  69. 	 */
  70. 	 //modCount记录的是list的结构被修改的次数
  71. 	 //结构被修改指的是改变了list的大小【添加或者删除元素的时候】
  72. 	 //否则，如果在进行迭代器循环的时候如果修改了modCount的值可能会导致错误的结果
  73.     protected transient int modCount = 0;
  74.  
  75. 	
  76. 	private void ensureExplicitCapacity(int minCapacity) {
  77. 		//modCount=0
  78.         modCount++;  
  79. 		//modCount=1
  80.  
  81.         // overflow-conscious code
  82. 		//加上正准备插入的这个元素，此时的总元素个数如果大于了数组elementData的长度才会扩容
  83. 		//也就是说如果elementData的长度为10，那么只有在准备插入11的元素的时候才会扩容
  84.         if (minCapacity - elementData.length > 0)
  85.             grow(minCapacity);
  86.     }
  87. 	
  88. 	/**
  89.      * Increases the capacity to ensure that it can hold at least the
  90.      * number of elements specified by the minimum capacity argument.
  91.      *
  92.      * @param minCapacity the desired minimum capacity
  93.      */
  94. 	 //扩容操作
  95. 	 //每次扩容为原集合容量的1.5倍: newCapacity = oldCapacity + (oldCapacity >> 1)
  96.     private void grow(int minCapacity) { //minCapacity=10
  97.         // overflow-conscious code
  98.         int oldCapacity = elementData.length;  //oldCapacity=0
  99.         int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity=0+(0>>1)=0
  100.         if (newCapacity - minCapacity < 0)   //0-10=-10
  101.             newCapacity = minCapacity;  //newCapacity=10
  102.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  103.             newCapacity = hugeCapacity(minCapacity);
  104.         // minCapacity is usually close to size, so this is a win:
  105.         elementData = Arrays.copyOf(elementData, newCapacity);   //进行数组拷贝，此时的newCapacity=10
  106.     }
  • Vector

Vector和ArrayList一样，也是基于数组实现的。在实例化对象时就初始化内部数组（大小为10） ，且Vector支持线程同步，即在多线程的环境下，能保证同一时间只有一个线程能够操控Vector，保证了数据的一致性【采用synchronized修饰增删改查方法】。但正是由于Vector保证了线程同步（锁的粒度太粗，将当前集合对象锁住，读读都互斥），所以导致了其性能较ArrayList低很多。

  1. /**
  2.      * The array buffer into which the components of the vector are
  3.      * stored. The capacity of the vector is the length of this array buffer,
  4.      * and is at least large enough to contain all the vector's elements.
  5.      *
  6.      * <p>Any array elements following the last element in the Vector are null.
  7.      *
  8.      * @serial
  9.      */
  10. 	 //vector的元素也是存放在数组中的
  11.     protected Object[] elementData;
  12. 	
  13. 	/**
  14.      * Constructs an empty vector so that its internal data array
  15.      * has size {@code 10} and its standard capacity increment is
  16.      * zero.
  17.      */
  18. 	 //首先初始化一个容量为10的数组
  19.     public Vector() {
  20.         this(10);
  21.     }
  22. 	
  23. 	/**
  24.      * Appends the specified element to the end of this Vector.
  25.      *
  26.      * @param e element to be appended to this Vector
  27.      * @return {@code true} (as specified by {@link Collection#add})
  28.      * @since 1.2
  29.      */
  30. 	 //synchronized修饰方法，向集合尾部添加元素
  31.     public synchronized boolean add(E e) {
  32.         modCount++;
  33.         ensureCapacityHelper(elementCount + 1);
  34.         elementData[elementCount++] = e;
  35.         return true;
  36.     }
  37. 	
  38. 	/**
  39.      * This implements the unsynchronized semantics of ensureCapacity.
  40.      * Synchronized methods in this class can internally call this
  41.      * method for ensuring capacity without incurring the cost of an
  42.      * extra synchronization.
  43.      *
  44.      * @see #ensureCapacity(int)
  45.      */
  46. 	 //加上正准备插入的这个元素，此时的总元素个数如果大于了数组elementData的长度才会扩容
  47. 	 //也就是说如果elementData的长度为10，那么只有在准备插入11的元素的时候才会扩容
  48.     private void ensureCapacityHelper(int minCapacity) {
  49.         // overflow-conscious code
  50.         if (minCapacity - elementData.length > 0)
  51.             grow(minCapacity);
  52.     }
  53. 	
  54. 	//扩容操作
  55. 	//扩容为原集合容量的2倍
  56. 	private void grow(int minCapacity) {
  57.         // overflow-conscious code
  58.         int oldCapacity = elementData.length;
  59.         int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
  60.                                          capacityIncrement : oldCapacity);
  61.         if (newCapacity - minCapacity < 0)
  62.             newCapacity = minCapacity;
  63.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  64.             newCapacity = hugeCapacity(minCapacity);
  65.         elementData = Arrays.copyOf(elementData, newCapacity);  //进行数组拷贝，此时的newCapacity=10
  66.     }
  67. 	
  68. 	/**
  69.      * Replaces the element at the specified position in this Vector with the
  70.      * specified element.
  71.      *
  72.      * @param index index of the element to replace
  73.      * @param element element to be stored at the specified position
  74.      * @return the element previously at the specified position
  75.      * @throws ArrayIndexOutOfBoundsException if the index is out of range
  76.      *         ({@code index < 0 || index >= size()})
  77.      * @since 1.2
  78.      */
  79.     public synchronized E set(int index, E element) {
  80.         if (index >= elementCount)
  81.             throw new ArrayIndexOutOfBoundsException(index);
  82.  
  83.         E oldValue = elementData(index);
  84.         elementData[index] = element;
  85.         return oldValue;
  86.     }
  87.  
  88. 	
  89. 	
  90. 	/**
  91.      * Returns the element at the specified position in this Vector.
  92.      *
  93.      * @param index index of the element to return
  94.      * @return object at the specified index
  95.      * @throws ArrayIndexOutOfBoundsException if the index is out of range
  96.      *            ({@code index < 0 || index >= size()})
  97.      * @since 1.2
  98.      */
  99.     public synchronized E get(int index) {
  100.         if (index >= elementCount)
  101.             throw new ArrayIndexOutOfBoundsException(index);
  102.  
  103.         return elementData(index);
  104.     }
  105. 	
  106. 	/**
  107.      * Removes the element at the specified position in this Vector.
  108.      * Shifts any subsequent elements to the left (subtracts one from their
  109.      * indices).  Returns the element that was removed from the Vector.
  110.      *
  111.      * @throws ArrayIndexOutOfBoundsException if the index is out of range
  112.      *         ({@code index < 0 || index >= size()})
  113.      * @param index the index of the element to be removed
  114.      * @return element that was removed
  115.      * @since 1.2
  116.      */
  117.     public synchronized E remove(int index) {
  118.         modCount++;
  119.         if (index >= elementCount)
  120.             throw new ArrayIndexOutOfBoundsException(index);
  121.         E oldValue = elementData(index);
  122.  
  123.         int numMoved = elementCount - index - 1;
  124.         if (numMoved > 0)
  125.             System.arraycopy(elementData, index+1, elementData, index,
  126.                              numMoved);
  127.         elementData[--elementCount] = null; // Let gc do its work
  128.  
  129.         return oldValue;
  130.     }
  • LinkedList

LinkedList是基于双向链表实现的，它支持对数据的随机插入和删除。但是如果要访问元素的话就比较慢了，它必须从头遍历。

  1. /**
  2.      * Pointer to first node.
  3.      * Invariant: (first == null && last == null) ||
  4.      *            (first.prev == null && first.item != null)
  5.      */
  6.     transient Node<E> first;
  7.  
  8.     /**
  9.      * Pointer to last node.
  10.      * Invariant: (first == null && last == null) ||
  11.      *            (last.next == null && last.item != null)
  12.      */
  13.     transient Node<E> last;
  14.  
  15.     /**
  16.      * Constructs an empty list.
  17.      */
  18.     public LinkedList() {
  19.     }
  20. 	
  21. 	
  22. 	
  23. 	private static class Node<E> {
  24.         E item;
  25.         Node<E> next;
  26.         Node<E> prev;
  27.  
  28.         Node(Node<E> prev, E element, Node<E> next) {
  29.             this.item = element;
  30.             this.next = next;
  31.             this.prev = prev;
  32.         }
  33.     }

三、区别

1、从初始化、扩容、线程安全三方面对比ArrayList与Vector

ArrayList采用懒加载策略（第一次add时才初始化内部数组，默认初始化大小为10）   扩容为原先数组大小的1.5倍。采用异步处理，线程不安全，性能较高       ArrayList在大部分场合（80%，频繁查找、在集合末端插入与删除）都采用ArrayList

Vector在实例化对象时就初始化内部数组（大小为10），capacityIncrement默认为0，扩容为原先数组大小的2倍。采用synchronized修饰增删改查方法，线程安全，性能较低（锁的粒度太粗，将当前集合对象锁住，读读都互斥），即使要用性能安全的集合，也不推荐使用Vector

2.LinkedList采用异步处理，线程不安全  频繁在任意位置的插入与删除考虑使用LinkedList  LinkedList是Queue接口的常用子类

四、使用场景

如果你的程序更多的是进行元素的随机访问或者从集合末端插入或删除元素，建议使用ArrayList；如果更多的是进行随机插入和删除操作，LinkedList会更优。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号