创建和使用 ArrayList、 TreeSet、 TreeMap 和 ArrayDeque 对象

• 集合概述
  • 重要的接口
• List
  • ArrayList
  • LinkedList
• Set
  • Hashset
  • TreeSet
• Queue 队列和堆栈
  • ArrayDeque
    • 特殊的方法
  • 栈
• Map

集合概述

集合：对象容器的通用术语
Java集合框架是 java.util 包中的类和接口库，它提供了具有不同特征的集合

重要的接口

• Collection
  集合层次结构的基本接口，它包含以下方法add(),remove(),clear(),及size().
• Iterable
  实现这个接口允许通过 for-each 循环，Iterator, 以及全新的forEach()方法
  
• List
• Set
• Queue
  用于按特定顺序存储一组元素的集合，通常按先进先出顺序存储
• Map
  Map 是唯一既不实现 Collection 也不实现 Iterable 接口的接口，但它仍然被认为是一个集合，因为它包含一组元素
  

List

• 可以插入 null 元素

ArrayList

• ArrayList是基于Object数组实现的，不同于数组，ArrayList可以自动增长，通过将元素复制到一个更大的数组来实现这一点的，因此添加(和删除)的速度较慢

LinkedList

• 一个双向链接的列表，也实现了 Deque 接口
• Array.asList

List<String> list =
        Arrays.asList("a", "b", "c", "d");

它返回一个由指定数组支持的 List 实现(但它不是 ArrayList，也不实现 List 的所有方法) ，这个实现具有固定的大小，这意味着您不能向它添加元素。此外，对 List 的修改也反映在原始数组中。

Set

• 不允许重复
• HashSet 和 TreeSet。它们之间的区别在于 TreeSet 对元素进行排序，而 HashSet 并不保证顺序，或者随着时间的推移顺序将保持不变

Hashset

HashSet 将元素存储在散列表中（hash table）使用 HashMap 实例

• HashSet 接受null
• 元素必须实现 hashCode ()和 equals ()方法，检索对象并避免重复

TreeSet

将元素存储在红黑树数据结构中

• TreeSet不接受null，会引发NPE，当添加一个元素时，会将其(作为 Comparable 或与 Comparator)与其他值进行比较，以便按正确的顺序插入元素，但是不能使用 null 值进行比较
  
• 时间复杂度添加、删除、查找元素和获取集合大小 log(n)
• 元素必须实现 equals ()方法
• 元素必须实现 Comparable 接口，或者在构造函数中传递 Comparator 的实现

Queue 队列和堆栈

队列
队列中，元素通常以 FIFO (先进先出)的方式添加和删除

ArrayDeque

• 由一个数组支持
• 从队列的前端(作为一个堆栈)和后端(作为一个队列)添加和删除元素的功能，而不是像 ArrayList 中的任何位置
• 不允许插入null

特殊的方法

• boolean add(E e) 元素添加到队列末尾如果成功，则返回 true，否则将引发异常
• E remove() 移除并返回队列的第一个元素，或者在该元素为空时抛出异常
• boolean offer(E e) 将元素添加到队列末尾如果成功返回true，否则false
• E poll() 移除并返回队列的第一个元素，如果不存在则返回null
• E peek() 返回队列的下一个元素，如果队列为空则返回null
• 对于每个操作，都有一个版本引发异常，另一个版本返回 false 或 null

Queue<String> queue = new ArrayDeque<>();
System.out.println(queue.offer("a")); // true [a]
System.out.println(queue.offer("b")); // true [a, b]
System.out.println(queue.peek()); // a [a, b]
System.out.println(queue.poll()); // a [b]
System.out.println(queue.peek()); // b [b]
System.out.println(queue.poll()); // b []
System.out.println(queue.peek()); // null

栈

使用ArrayDeque的void push(E e)和E pop() 方法，可以使用这个类作为一个堆栈，一个对后进先出(LIFO)中的元素排序的数据结构

// Adds elements to the front of the queue
void push(E e)

// Removes and returns the next element 
// or throws an exception if the queue is empty
E pop() 

这些方法不定义在 Queue 接口中，而在Deque接口中

Map

映射不能包含重复的键，键与一个值相关联(可以是任何对象，甚至是另一个映射，或 null)
HashMap 和 TreeMap。

• 它们之间的区别在于，TreeMap 对键进行排序，添加和检索键时间复杂度log (n)，而 HashMap 不保证顺序，但添加和检索键更快
• 由于排序的方式(同样，就像 TreeSet 一样) ，TreeMap 不能将空值作为键，会引发NPE
• 用作键的对象必须实现 equals ()和 hashCode ()方法