Java集合(三)—List和Queue集合

- 日理万妓 2022-12-13 04:18 158阅读 0赞

### 文章目录 ###

*   *   *  Java集合—List集合
         *   *  ArrayList和Vector
             *  Stack类(Vector的子类)
             *  固定长度的List
         *  Java集合-Queue集合
         *   *  PriorityQueue类
             *  Deque接口与ArrayDeque
             *  LinkedList类
         *  线性表性能分析

### Java集合—List集合 ###

与Set集合不同，List集合是有序，可重复的，而且默认以添加顺序设置索引。`List`子接口是继承了`Collection`接口，则可以使用其中的方法。

特别的是`List`增加了根据索引插入、替换、删除集合元素的方法，此外，Java8为`List`接口添加了两个默认方法：

*  void replaceAll()：根据指定规则重新设置List集合的所有元素
 *  void sort(Comparator c)：根据参数对List集合的元素排序

List books = new ArrayList();
    books.add(new String("ledon"));
    books.add(new String("Android"));
    books.sort((o1,o2)->((String)o1).length()-((String)o2).length());
    //字符串将由短到长排序
    System.out.println(books);
    books.replaceAll(e->((String)e).length());
    System.out.println(e);//[5,7]

**值得注意的是**：`List`判断两个对象相等，只要通过`equals`方法比较返回true即可，不像`Set`集合，还需要判断哈希值是否相等来避免重复。

删除元素时，`List`会调用对象的`equals`方法依次与集合元素比较，如果返回true，则会删除该元素。如果重写了`equals`方法，使它总是返回true，则List总会删除第一个元素。在使用`set(index,object)`方法时，index不能超过集合的长度，也不能改变长度。

List不仅有`iterator()`方法，还有`listIterator()`方法，该方法返回一个`ListIterator`对象，`ListIterator`接口继承了`Iterator`接口，提供了专门的方法操作`List`，增加了如下方法(类似Iterator的方法)：

*  boolean hasPrevious()：返回该集合是否还有上一个元素
 *  Object previous()：返回上一个元素
 *  void add(Object o)：在指定位置插入一个元素

不难发现该接口还能向前迭代，不止能删除元素，并且还能通过`add()`方法，添加元素。

#### ArrayList和Vector ####

它们两个封装了 一个动态的Object\[ \]数组，允许再分配。`ArrayList`及`Vector`对象使用`initialCapacity`参数来设置数组的长度，当超出数组容量时，`initialCapacity`会自动增加，可使用`ensureCapacity(int minCapacity)`方法一次性增加`initialCapacity`。如果事先知道元素的个数，可指定初始大小；如果没有指定初始容量，默认为10。

`ArrayList`和`Vector`提供了两个方法重新分配`Object[]`数组：

*  void ensureCapacity(int minCapacity)：将`ArrayList`和`Vector`集合的`Object[]`数组长度增加到大于或等于minCapacity值
 *  void trimToSize()：调整`ArrayList`及`Vector`的数组长度为当前元素个数，减少占用空间

`ArrayList`和`Vector`的用法几乎完全相同，`Vector`也是实现了`List`接口，从`JDK1.0`就有了，很古老！此外，`ArrayList`是线程不安全的，原理一样；但`Vector`是线程安全的，即无需保证线程的同步性，因而`Vector`的性能比`ArrayList`低。但是还是用`ArrayList`更多，要想线程安全，也可以把`ArrayList`变成线程安全。

#### Stack类(Vector的子类) ####

翻译过来就是“栈”，模拟进栈`push`，出栈`pop`等操作。作为集合的一种，它也是储存对象(Object)的，有如下方法：

*  Object peek()：返回栈顶元素，但并不弹出该元素，元素还会在栈内
 *  Object pop()：返回栈顶元素，并弹出栈
 *  void push(Object item)：推元素进栈

`Stack`继承了`Vector`，所以它也非常古老，线程安全、性能较差。后面还会介绍一种“栈”结构——ArrayDeque，它不仅实现了`List`接口，还实现了`Deque`接口，如果需要栈结构，可以使用它而不是`Stack`。

#### 固定长度的List ####

有一种操作数组的工具类`Arrays`，该工具类提供了`asList()`方法，该方法把一个数组或指定个数的对象换成一个`List`集合，这个集合不是以上所介绍的集合类的实例，不是`ArrayList`的，不是`Vector`的，而是`Arrays`的内部类`ArrayList`的实例。`Arrays.ArrayList`是一个固定长度的`List`集合，不允许添加、删除操作，只能遍历访问，否则程序将出现`UnsupportedOperationException`异常。

### Java集合-Queue集合 ###

在`Queue`接口中定义了如下的方法：

*  void add(Object e)：添加元素到队尾
 *  boolean offer(Object e)：将指定元素加入队列的尾部，成功返回true
 *  Object element()：获取队列头部的元素，但不是删除该元素
 *  Object remove()：获取头部元素，并删除该元素
 *  Object peek()：获取队列头部的元素，但不是删除，如果为空返回null
 *  Object poll()：获取并删除头部元素，为空，返回null

Queue有一个`PriorityQueue`实现类，除此外还有一个`Deque`接口，代表双端队列，即两端可以添加删除元素。其实现类为`ArrayDeque`和`LinkedList`两个实现类。

#### PriorityQueue类 ####

PriorityQueue并不是一个标准的队列，其保存队列的顺序是重新排序了的(按元素的大小)，显然不符合队列的规则。如果调用`poll`方法，可以看到元素从小到大移出队列。另外需要注意的是，`PriorityQueue`不允许插入null元素！

它的排序有两种，自然排序、定制排序，排序规则与`TreeSet`类似：

*  自然排序：自然排序时，元素必须实现了`Comparable`接口，而且是同一类的实例。
 *  定制排序：创建队列时，传入一个`Comparator`对象，该对象负责排序，但是不要求元素实现`Comparable`接口

#### Deque接口与ArrayDeque ####

`Deque`接口是`Queue`的子接口，允许对队列两端进行操作，同时，还可以当作“栈”来使用，因为它还有`pop`、`push`方法。典型的实现类是`ArrayDeque`，一个基于数组的双端队列，在创建`Deque`时，同样可以指定一个`numElement`元素个数参数，指定Object\[ \]数组的长度；如果不指定，则默认长度为16。

`ArrayList`与`ArrayDeque`的实现原理差不多，底层采用一个动态的、可再分配的数组实现，初始化可指定初始长度等，当元素个数超出容量时，系统会重新分配一个`Object[]`数组储存元素。

#### LinkedList类 ####

`LinkedList`实现了`List`接口，是`List`集合，还实现了`Deque`接口，可以当双端队列使用，还能当"栈"使用。 但它的实现机制与`ArrayList`、`ArrayDeque`的不一样，它两是用数组实现，而`LinkedList`是以链表的形式来保存元素，随机访问性能较差，但插入、删除操作比较溜！

### 线性表性能分析 ###

一般来说，数组由一块连续的内存来保存数据，所以数组随机访问性能好，类似的，以数组为底层实现的类，随机访问性能都比较好；而链表的插入、删除操作性能好。综合来讲，还是用`ArrayList`比较妥。

*  如果需要遍历：对于`ArrayList`，`Vector`集合，使用随机访问方法遍历即可；对于`LinkedList`集合，采用`Iterator`迭代器遍历比较好。
 *  如果经常要执行插入、删除操作，可以使用`LinkedList`集合，而使用以数组为底层的线性表要重新分配内部数组大小，性能较差。
 *  如果有多个线程同时访问，可以使用工具类包装成线程安全的集合。