数据结构与算法基础（十六）集合

　　摘要
　　集合 最重要的特点就是它里面的元素是不会存在重复的，所以集合的内部实现中，添加元素函数是需要先判断是否已经存在这个元素，是代码实现的核心部分。
　　集合 是一个存储数据的序列，序列中的元素不会存在重复，这个就是集合最重要的特点。
　　就是因为这个特点，它可以被用作序列中元素的 去重 处理，比如存放新增加的 IP，统计新增的 IP 数量，存放词汇或者统计词汇量等。
　　集合 的内部实现可以直接利用之前学过的数据结构来实现，比如 动态数组 、 链表 、 AVL 树或者红黑树（属于二叉搜索树） 。
　　这里先用 动态数组 来实现集合。首先创建一个 动态数组的对象 来存放元素。 private List list = new LinkedList<>();
　　集合中的其他函数，比如 集合中的元素数量 、 集合是否为空 、 清除集合中的所有元素 和 集合中是否包含某个元素 这4个函数可以直接调用  list   的函数来处理，比如实现集合中的元素数量： // 集合中的元素数量 public int size() {   return list.size(); }
　　移除集合中的元素函数需要先在  list   中找到元素的  index  ，然后再移除  list   中的  index   位置元素。 // ELEMENT_NOT_FOUND：集合空元素标识符，常量为 -1 public void remove(E element) {   int index = list.indexOf(element);   if (index != List.ELEMENT_NOT_FOUND) {     list.remove(index);   } }
　　最后就是实现集合的主要函数，即添加元素函数。因为 集合 要满足元素不可以重复的要求，所以在添加元素的时候需要先判断集合中是否已经存在该元素： public void add(E element) {   int index = list.indexOf(element);   if (index != List.ELEMENT_NOT_FOUND) {     // 存在，则替换     list.set(index, element);   } else {     // 不存在，则直接添加     list.add(element);   } }
　　如果用AVL树或者红黑树，那么添加元素的逻辑就更简单 。因为这两种树中的元素都是不会有重复的，所以使用这两种树来实现，就直接调用树的添加函数就可以实现。 public void add(E element) {   tree.add(element); }
　　集合中的其他函数，就可以直接使用树已经有的函数来直接调用，和套用动态数组的方式是一样的。