I. 第一部分：常见数据结构
首先简单说下数据结构.
什么是数据结构？数据结构就是组织数据的方式.
常见的数据结构：栈，堆，树，图，数组，队列，链表.
这里主要介绍与java集合体系相关的栈、数组和链表.
栈
特点：压栈弹栈，先进后出.
如：手枪弹夹装弹过程，最先压入的子弹在最下面；而在射击时，最先弹入枪膛的是最上面的子弹，即最后压入弹夹的子弹.
队列
特点：先进先出.
如：子弹射出的过程，先进入枪膛的子弹最先被射出.
数组
概述：用来存储同一种类型元素的容器。
特点：在内存中是连续的，每个元素都有编号（从0开始的），方便获取。但增删就比较麻烦，需要将目标位置后的所有数据前移动或后移.
查询快，增删慢.
链表
概述：把一些结点通过链子连接起来的数据结构。每个结点由地址域和数值域组成.
特点：增删快，查询慢. 增删时，只需要把所插入处的前后节点链条断开，增加或移除目标节点，速度很快。反之，查询时则需要遍历所有节点，直到找到目标节点，速度自然要慢。
II. 第二部分：Java中的Collection(集合)体系
2.1 集合体系概览：
集合体系分为4大块：
Collection接口:
Collection是最基本集合接口，它定义了一组允许重复的对象.
它有两个子接口：List和Set.
1. List下3个实现类：ArrayList, LinkedList, Vector. List是有序的。
1.1 List接口的三个儿子的特点：
1.1.1 ArrayList：底层数据结构是数组，查询快，增删慢。线程不安全（不同步），效率高。
1.1.2 Vector：底层数据结构是数组，查询快，增删慢。线程安全，效率低。
1.1.3 LinkedList：底层数据结构是链表，增删快，查询慢。 线程不安全的，效率高。
1.2 如何来选择使用哪个仔呢？
keywords: 看需求!
step1: 看是否考虑安全? 安全, 则Vector.
step2: 如果不考虑安全，那么是查询多还是增删多?
查询多, 则ArrayList; 增删多，则LinkedList.
什么都不知道，用ArrayList。
2. Set下2个实现类：HashSet, TreeSet. Set是无序的。
Map接口：
该接口描述了从不重复的键到值的映射。Map接口用于维护键/值对.
特征：它描述了从不重复的键到值的映射.
两个重要的实现类：HashMap和TreeMap.
1.HashMap，中文叫散列表，基于哈希表实现，特点就是键值对的映射关系。一个key对应一个Value。
HashMap中元素的排列顺序是不固定的。更加适合于对元素进行插入、删除和定位。
2.TreeMap，基于红黑树实现。TreeMap中的元素保持着某种固定的顺序。更加适合于对元素的顺序遍历。
Comaprable接口：
Comparable可以用于比较的实现，实现了Comparable接口的类可以通过实现comparaTo方法从而确定该类对象的排序方式。
Iterator接口：
用于循环访问集合中的对象。
所有实现了Collection接口的容器类都有iterator方法，用于返回一个实Iterator接口的对象。
Iterator对象称作迭代器，Iterator接口方法能以迭代方式逐个访问集合中各个元素，并可以从Collection中除去适当的元素。
2.2 Collection的接口概览(List 和 Set)
2.2.1 List接口
三个子类：
ArrayList
底层数据结构是数组，查询快，增删慢。
线程不安全（不同步），效率高。
-Vector
底层数据结构是数组，查询快，增删慢。
线程安全，效率低。
特有功能:
添加：
void addElement(Object obj);
获取：
Object elementAt(int index);
Enumeration elements(); //它返回此向量的组件的枚举,类似于迭代器Iterator
boolean hasMoreElements() //类似于hasNext()
Object nextElement(); //类似于next();
-LinkedList
底层数据结构是链表，增删快，查询慢。
线程不安全的，效率高。
特有方法：
添加：
void addFirst(Object obj);//头部添加元素
void addLast(Object obj);//尾部添加元素
获取：
Object getFirst();//获取头部元素
Object getLast();//获取尾部元素
删除：
Object removeFirst();//移除头部元素
Object removeLast();//移除尾部元素
#问：以后用List体系的那个子类？
看是否考虑安全。
安全：用Vector
不安全：继续考虑是查询多还是增删多
查询多：ArrayList
增删多：LinkedList
什么都不知道，用ArrayList。
#练习题：
1.一个字符串集合ArrayList中含有如下元素：hello, world, java, hello, .net, java, php, ios, java, android，world。要求编写程序，获得一个没有重复元素的新集合。
#思路：
1、创建两个集合对象，A，B。
2、把字符串添加到集合A中。
3、遍历集合A，并且判断集合B中是否包含A集合当前遍历到的元素。
4、如果包含，不添加，如果不包含，就将该元素添加到集合B中。
5、迭代结束后，集合B中存的就是去重后的元素。
练习题
#请用LinkedList来模拟栈的数据结构。
刚我们知道栈的结构为：先进后出.
咱们可以使用LinkedList集合，对这个类进行包装来实现先进先出的效果，但不能直接使用它。
具体实现时，先往集合里添加一个新数据，add(); 取自己写类，对LinkedList进行封装：
1、需要提供添加元素的方法add() //内部封装的是：addFirst()
2、需要提供获取元素的方法get(int index) //内部封装的是：List体系的get(int index)方法
3、需要提供获取集合长度的方法size() //内部分装的是：LinkedList的size()方法
以后遇到类似的题，怎么做？
解题思路：
1、分析要模拟的数据结构的特点。
2、对可用的类进行包装，然后提供对应的方法就可以了。
2.2 Set集合
set集合的特点: 无序,唯一
2.2.1 HashSet集合
A:底层数据结构是哈希表(是一个元素为链表的数组)
B:哈希表底层依赖两个方法：hashCode()和equals()
如何保证元素唯一性?
由hashCode()和equals()保证的，先调用hashCode()在调用equals().
执行顺序：
首先比较哈希值是否相同:
若相同：
继续执行equals()方法；
-返回true：元素重复了，不添加；
-返回false：直接把元素添加到集合；
若不同：
就直接把元素添加到集合；
2.2.2 TreeSet集合
A:底层数据结构是红黑树(是一个自平衡的二叉树)
B:保证元素的排序方式
排序方法：
a:自然排序(元素具备比较性)：让元素所属的类实现Comparable接口.
b:比较器排序(集合具备比较性)：让集合构造方法接收Comparator的实现类对象
2.3 Map接口概览
Map也是接口，但没有继承Collection接口。该接口描述了从不重复的键到值的映射。Map接口用于维护键/值对（key/value pairs）。
特征：它描述了从不重复的键到值的映射。
两个重要的实现类：HashMap和TreeMap
1.HashMap，中文叫散列表，基于哈希表实现，特点就是键值对的映射关系。一个key对应一个Value。HashMap中元素的排列顺序是不固定的。更加适合于对元素进行插入、删除和定位。
2.TreeMap，基于红黑书实现。TreeMap中的元素保持着某种固定的顺序。更加适合于对元素的顺序遍历。
总结
|-List
有序,可重复
|--ArrayList
底层数据结构是数组，查询快，增删慢.
线程不安全，效率高.
|--Vector
底层数据结构是数组，查询快，增删慢.
线程安全，效率低.
|--LinkedList
底层数据结构是链表，查询慢，增删快.
线程不安全，效率高.
|-Set
无序,唯一
|--HashSet
底层数据结构是哈希表.
保证元素唯一性: 依赖两个方法：hashCode()和equals().
|--LinkedHashSet
底层数据结构是链表和哈希表
由链表保证元素有序
由哈希表保证元素唯一
|--TreeSet
底层数据结构是红黑树。
如何保证元素排序? 自然排序; 比较器排序.
如何保证元素唯一性的呢? 根据比较的返回值是否是0来决定.
4:针对Collection集合我们到底使用谁?
唯一么? 是：Set; 否：List.
若用Set： 排序么? 是：TreeSet; 否：HashSet. 如果知道是Set，但是不知道是哪个Set，就用HashSet. 要安全吗?是：Vector; 否：ArrayList或者LinkedList.
若用List: 查询多：ArrayList 增删多：LinkedList 如果你知道是List，但是不知道是哪个List，就用ArrayList.
如果你知道是Collection集合，但是不知道使用谁，就用ArrayList。
如果你知道用集合，就用ArrayList。
5:在集合中常见的数据结构(掌握)
ArrayXxx:底层数据结构是数组，查询快，增删慢； LinkedXxx:底层数据结构是链表，查询慢，增删快； HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals()； TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序；
