List详解（ArrayList、LinkedList、Vect

2019-02-28 本文已影响0人朱朱今天撸代码了吗

List详解

List	我们需要保留存储顺序，并且保留重复元素，使用List
ArrayList	查询较多的时候使用ArrayList
LinkedList	存取较多的时候使用LinkedList
Vector	需要保证线程安全的时候使用Vector

Arraylist： Object数组
LinkedList： 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)
Vector： Object数组

ArrayList

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。

它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

继承关系

↳ java.util.AbstractCollection<E>  
  ↳ java.util.AbstractList<E>  
    ↳ java.util.ArrayList<E>

public class ArrayList<E> extends AbstractList<E>  implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

构造函数

// 默认构造函数  
ArrayList()
// capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时，容量会添加上一次容量大小的一半。  
ArrayList(int capacity)
// 创建一个包含collection的ArrayList  ArrayList(Collection<? extends E> collection)

底层原理实现

ArrayList包含了两个重要的对象：elementData 和 size。

transient Object[] elementData;

elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长。

private int size;

size 则是动态数组的实际大小。

遍历方式

第一种，通过迭代器遍历。

    Integer value = null;  Iterator iter = list.iterator();  while (iter.hasNext()) {  value = (Integer)iter.next();  }

第二种，随机访问，通过索引值去遍历。

    Integer value = null;  int size = list.size();  for (int i=0; i<size; i++) {  value = (Integer)list.get(i); }

第三种，for循环遍历。

Integer value = null;  for (Integer integ:list) {  value = integ;  }

遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！

API

// Collection中定义的API
boolean             add(E object)
boolean             addAll(Collection<? extends E> collection)
void                clear()
boolean             contains(Object object)
boolean             containsAll(Collection<?> collection)
boolean             equals(Object object)
int                 hashCode()
boolean             isEmpty()
Iterator<E>         iterator()
boolean             remove(Object object)
boolean             removeAll(Collection<?> collection)
boolean             retainAll(Collection<?> collection)
int                 size()
<T> T[]             toArray(T[] array)
Object[]            toArray()
// AbstractCollection中定义的API
void                add(int location, E object)
boolean             addAll(int location, Collection<? extends E> collection)
E                   get(int location)
int                 indexOf(Object object)
int                 lastIndexOf(Object object)
ListIterator<E>     listIterator(int location)
ListIterator<E>     listIterator()
E                   remove(int location)
E                   set(int location, E object)
List<E>             subList(int start, int end)
// ArrayList新增的API
Object               clone()
void                 ensureCapacity(int minimumCapacity)
void                 trimToSize()
void                 removeRange(int fromIndex, int toIndex)

LinkedList

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

LinkedList 是非同步的。

继承关系

java.lang.Object  
  ↳ java.util.AbstractCollection<E>  
    ↳ java.util.AbstractList<E> 
     ↳ java.util.AbstractSequentialList<E> 
       ↳ java.util.LinkedList<E>

public class LinkedList<E>  extends AbstractSequentialList<E>  
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

构造函数

// 默认构造函数  
LinkedList()
// 创建一个LinkedList，保护Collection中的全部元素。  LinkedList(Collection<? extends E> collection)

底层原理

LinkedList的本质是双向链表。 (01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。 (02) LinkedList包含两个重要的成员：header 和 size。 header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。　　size是双向链表中节点的个数。

遍历方式

第一种，通过迭代器遍历。

for(Iterator iter = list.iterator(); iter.hasNext();)  iter.next();

通过快速随机访问遍历LinkedList

int size = list.size();  for (int i=0; i<size; i++) {  list.get(i); }

通过另外一种for循环来遍历LinkedList

for (Integer integ:list) ;

通过pollFirst()来遍历LinkedList

while(list.pollFirst() != null)  ;

通过pollLast()来遍历LinkedList

while(list.pollLast() != null)  ;

通过removeFirst()来遍历LinkedList

try {  while(list.removeFirst() != null)  ;  } catch (NoSuchElementException e) {  }

通过removeLast()来遍历LinkedList

try {  while(list.removeLast() != null)  ;  } catch (NoSuchElementException e) {  }

遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。 无论如何，千万不要通过随机访问去遍历LinkedList！

API

boolean       add(E object)
void          add(int location, E object)
boolean       addAll(Collection<? extends E> collection)
boolean       addAll(int location, Collection<? extends E> collection)
void          addFirst(E object)
void          addLast(E object)
void          clear()
Object        clone()
boolean       contains(Object object)
Iterator<E>   descendingIterator()
E             element()
E             get(int location)
E             getFirst()
E             getLast()
int           indexOf(Object object)
int           lastIndexOf(Object object)
ListIterator<E>     listIterator(int location)
boolean       offer(E o)
boolean       offerFirst(E e)
boolean       offerLast(E e)
E             peek()
E             peekFirst()
E             peekLast()
E             poll()
E             pollFirst()
E             pollLast()
E             pop()
void          push(E e)
E             remove()
E             remove(int location)
boolean       remove(Object object)
E             removeFirst()
boolean       removeFirstOccurrence(Object o)
E             removeLast()
boolean       removeLastOccurrence(Object o)
E             set(int location, E object)
int           size()
<T> T[]       toArray(T[] contents)
Object[]     toArray()

Vector

Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。

继承关系

java.lang.Object  
  ↳ java.util.AbstractCollection<E>  
    ↳ java.util.AbstractList<E>  
      ↳ java.util.Vector<E>

public class Vector<E>  extends AbstractList<E>  implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

构造函数

Vector共有4个构造函数  
// 默认构造函数  
Vector()
// capacity是Vector的默认容量大小。当由于增加数据导致容量增加时，每次容量会增加一倍。  
Vector(int capacity)
// capacity是Vector的默认容量大小，capacityIncrement是每次Vector容量增加时的增量值。  
Vector(int capacity, int capacityIncrement)
// 创建一个包含collection的Vector  
Vector(Collection<? extends E> collection)

底层原理

Vector的数据结构和ArrayList差不多，它包含了3个成员变量：elementData , elementCount， capacityIncrement。

(01) elementData 是"Object[]类型的数组"，它保存了添加到Vector中的元素。elementData是个动态数组，如果初始化Vector时，没指定动态数组的>大小，则使用默认大小10。随着Vector中元素的增加，Vector的容量也会动态增长，capacityIncrement是与容量增长相关的增长系数，具体的增长方式，请参考源码分析中的ensureCapacity()函数。

(02) elementCount 是动态数组的实际大小。

(03) capacityIncrement 是动态数组的增长系数。如果在创建Vector时，指定了capacityIncrement的大小；则，每次当Vector中动态数组容量增加时>，增加的大小都是capacityIncrement。

遍历方式

第一种，通过迭代器遍历。

Integer value = null;  int size = vec.size();  for (int i=0; i<size; i++) {  value = (Integer)vec.get(i); }

第二种，随机访问，通过索引值去遍历。

Integer value = null;  int size = vec.size();  for (int i=0; i<size; i++) {  value = (Integer)vec.get(i); }

第三种，另一种for循环。

Integer value = null;  for (Integer integ:vec) {  value = integ;  }

第四种，Enumeration遍历。

Integer value = null;  Enumeration enu = vec.elements();  while (enu.hasMoreElements()) {  value = (Integer)enu.nextElement();  }

总结：遍历Vector，使用索引的随机访问方式最快，使用迭代器最慢。

API

synchronized boolean        add(E object)
             void           add(int location, E object)
synchronized boolean        addAll(Collection<? extends E> collection)
synchronized boolean        addAll(int location, Collection<? extends E> collection)
synchronized void           addElement(E object)
synchronized int            capacity()
             void           clear()
synchronized Object         clone()
             boolean        contains(Object object)
synchronized boolean        containsAll(Collection<?> collection)
synchronized void           copyInto(Object[] elements)
synchronized E              elementAt(int location)
             Enumeration<E> elements()
synchronized void           ensureCapacity(int minimumCapacity)
synchronized boolean        equals(Object object)
synchronized E              firstElement()
             E              get(int location)
synchronized int            hashCode()
synchronized int            indexOf(Object object, int location)
             int            indexOf(Object object)
synchronized void           insertElementAt(E object, int location)
synchronized boolean        isEmpty()
synchronized E              lastElement()
synchronized int            lastIndexOf(Object object, int location)
synchronized int            lastIndexOf(Object object)
synchronized E              remove(int location)
             boolean        remove(Object object)
synchronized boolean        removeAll(Collection<?> collection)
synchronized void           removeAllElements()
synchronized boolean        removeElement(Object object)
synchronized void           removeElementAt(int location)
synchronized boolean        retainAll(Collection<?> collection)
synchronized E              set(int location, E object)
synchronized void           setElementAt(E object, int location)
synchronized void           setSize(int length)
synchronized int            size()
synchronized List<E>        subList(int start, int end)
synchronized <T> T[]        toArray(T[] contents)
synchronized Object[]       toArray()
synchronized String         toString()
synchronized void           trimToSize()

参考文献：

Java 集合系列目录(Category)

List详解（ArrayList、LinkedList、Vect

List详解

ArrayList

继承关系

构造函数

底层原理实现

遍历方式

API

LinkedList

继承关系

构造函数

底层原理

遍历方式

API

Vector

继承关系

构造函数

底层原理

遍历方式

API

猜你喜欢

热点阅读