java中的容器类和接口总结（二）：List

缺乏、安全感 2022-05-29 13:26 189阅读 0赞

![70][]

官方API文档：

Interface List<E>

Type Parameters:

E - the type of elements in this list

All Superinterfaces:  
Collection<E>, Iterable<E>

List 接口  
一个 List 是一个元素有序的、可以重复、可以为 null 的集合（有时候我们也叫它“序列”）。  
Java 集合框架中最常使用的几种 List 实现类是 ArrayList，LinkedList 和 Vector。在各种 List 中，最好的做法是以 ArrayList 作为默认选择。 当插入、删除频繁时，使用 LinkedList，Vector 总是比 ArrayList 慢，所以要尽量避免使用它。  
为什么 List 中的元素 “有序”、“可以重复”呢?

List 的数据结构就是一个序列，存储内容时直接在内存中开辟一块连续的空间，然后将空间地址与索引对应。List接口的实现类在实现插入元素时，都会根据索引进行排列。

ArrayList：底层的数据结构使用的是数组结构（数组长度是可变的百分之五十延长）（特点是查询很快，但增删较慢）线程不同步  
LinkedList：底层的数据结构是链表结构（特点是查询较慢，增删较快）

Vector：底层是数组数据结构 线程同步（数组长度是可变的百分之百延长）（无论查询还是增删都很慢，被ArrayList替代了）

由于 List 的元素在存储时互不干扰，没有什么依赖关系，自然可以重复（这点与 Set 有很大区别）。  
List 接口定义的方法  
List 中除了继承 Collection 的一些方法，还提供以下操作：  
位置相关：List 和 数组一样，都是从 0 开始，我们可以根据元素在 list 中的位置进行操作，比如说 get, set, add, addAll, remove;  
搜索：从 list 中查找某个对象的位置，比如 indexOf, lastIndexOf;  
迭代：使用 Iterator 的拓展版迭代器 ListIterator 进行迭代操作;

范围性操作：使用 subList 方法对 list 进行任意范围的操作。

常用方法：

voidadd(int index, E element)

Inserts the specified element at the specified position in this list (optional operation).

Eget(int index)

Returns the element at the specified position in this list.

intindexOf(Object o)

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

ListIterator<E>listIterator()  
Returns a list iterator over the elements in this list (in proper sequence).  
ListIterator<E>listIterator(int index)

Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list.

Eset(int index, E element)  
Replaces the element at the specified position in this list with the specified element (optional operation).  
intsize()  
Returns the number of elements in this list.  
default voidsort(Comparator<? super E> c)

Sorts this list according to the order induced by the specified Comparator.

List<E>subList(int fromIndex, int toIndex)  
Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.  
Object\[\]toArray()  
Returns an array containing all of the elements in this list in proper sequence (from first to last element).  
<T> T\[\]toArray(T\[\] a)

Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

局部范围操作  
List.subList(int fromIndex, int toIndex) 方法返回 List 在 fromIndex 与 toIndex 范围内的子集。注意是左闭右开，\[fromIndex,toIndex)。  
  
  
注意！ List.subList 方法并没有像我们想的那样：创建一个新的 List，然后把旧 List 的指定范围子元素拷贝进新 List，根！本！不！是！

subList 返回的扔是 List 原来的引用，只不过把开始位置 offset 和 size 改了下。

所以，重点来了！

由于 subList 持有 List 同一个引用，所以对 subList 进行的操作也会影响到原有 List：

![70 1][]

运行结果：![70 2][]

Arraylist和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以插入数据慢，查找有下标，所以查询数据快，Vector由于使用了synchronized方法-线程安全，所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项前后项即可，插入数据较快。

List接口  
　　List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。  
和下面要提到的Set不同，List允许有相同的元素。  
　　除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。  
　　实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。  
  
  
ArrayList类  
　　ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。  
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。  
　　每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。  
　　和LinkedList一样，ArrayList也是非同步的（unsynchronized）。  
  
  
Vector类  
　　Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。  
  
  
Stack 类

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

同步性  
Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。  
数据增长  
从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。  
使用模式  
在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢？  
这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他的集合操作类。比如，LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1)，但它在索引一个元素的使用缺比较慢－O(i),其中i是索引的位置.使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。LinkList也会为每个插入的元素创建对象，所有你要明白它也会带来额外的开销。

最后，在《Practical Java》一书中Peter Haggar建议使用一个简单的数组（Array）来代替Vector或ArrayList。尤其是对于执行效率要求高的程序更应如此。因为使用数组(Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作。

import java.util.ArrayList;
    import java.util.Iterator;
    
    public class CollectionTest1 {
    	public static void main(String[] args){
    		ArrayList<Integer> arrayList = new ArrayList<Integer>();
    		arrayList.add(12);
    		arrayList.add(10);
    		arrayList.add(35);
    		arrayList.add(100);
    		//获取容器的迭代器
    		Iterator<Integer> iterator = arrayList.iterator();
    		while(iterator.hasNext()){
    			Integer value = iterator.next();
    			System.out.println(value);
    		}
    		System.out.println("通过ArrayList容器获取一个数组arr:");
    		Object[] arr = arrayList.toArray();
    		for(int i = 0; i < arr.length; i++)
    			System.out.println(arr[i]);
    	}
    }

ArrayList本质是一个数组：

![70 3][]

而LinkedList是一个双向链表：

![70 4][]

总结：

ArrayList和Vector的区别  
ArrayList与Vector主要从二方面来说.  
一.同步性:  
Vector是线程安全的，也就是说是同步的，而ArrayList是线程序不安全的，不是同步的。  
二.操作:  
由于Vector支持多线程操作，所以在性能上就比不上ArrayList了。  
三.数据增长:  
ArrayList和Vector都有一个初始的容量大小，当存储进去它们里面的元素个数超出容量的时候，就需要增加ArrayList和Vector的存储空间，每次增加存储空间的时候不是只增加一个存储单元，是增加多个存储单元。  
Vector默认增加原来的一倍，ArrayList默认增加原来的0.5倍。  
Vector可以由我们自己来设置增长的大小，ArrayList没有提供相关的方法。  
  
LinkedList与ArrayList的区别  
两者都实现的是List接口，不同之处在于：  
（1）、ArrayList是基于动态数组实现的，LinkedList是基于链表的数据结构。  
（2）、get访问List内部任意元素时，ArrayList的性能要比LinkedList性能好。LinkedList中的get方法是要按照顺序从列表的一端开始检查，直到另一端  
（3）、对于新增和删除操作LinkedList要强于ArrayList，因为ArrayList要移动数据  
LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。  
注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：  
List list = Collections.synchronizedList(new LinkedList(…));  
  
数组(Array)和列表集合(ArrayList)的区别  
Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。  
Array大小是固定的，ArrayList的大小是动态变化的。  
ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等。

[70]: /images/20220529/5d3e14b08228470f8f4213d2af3d6af2.png
[70 1]: /images/20220529/9721949f82774d669060fa011cebc512.png
[70 2]: /images/20220529/51944bfaeea948a1bfa3971b7281b607.png
[70 3]: /images/20220529/6357024317774c68ad84d92230036d78.png
[70 4]: /images/20220529/0a059999ce6d438f984d8e0bfb7a6ca7.png