1、数据，指能够输入计算机中，由计算机所处理的元素。结构， 指数据之间的关系。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
常用的数据结构有：
链表
堆栈
队列
树
哈希表
说明：堆栈、队列、链表为线性存储结构（线性表），即多个元素的有序序列。堆栈，队列为操作受限的线性表。
2、链表：链表存储的数据元素称为结点，在链表中，各个结点是有序的。
每个结点分为两个部分：
数据域
指针域
根据链表指针域的数量，可以将链表分为：
单向链表
双向链表
单向链表：
双向链表：前一个指向上一个结点，中间是数据域，后一个指向下一个结点。（循环双向链表）
数组与链表的不同：
存储方式： 数组在内存中时连续存储，链表在内存中不是连续存储。
3、堆栈
堆栈（简称栈）是一种操作受限的线性表，只能在表头增加或删除元素。我们通常将栈使用竖直的方式来表示，因此，表尾称为“栈顶”，表头称为“栈底”。栈表现的特征为后进先出。（ LIFO）
4、队列
队列是一种操作受限的线性表。只能在队尾增加元素，在队头删除元素。
队列表现的特征为先进先出（FIFO）。
队列分为：单端队列、双端队列
当队列的两端都可以增加与删除元素时，这种队列称为双端队列。双端队列可以同时实现队列与堆栈的特征。
5、树
树是由结点集及连接每对结点的有向边集组成。
如果存在有向边连接A到B，则A为B的父节点（父亲），B为A的子节点（孩子）。没有父节点的结点称为根，没有子节点的结点称为叶子。具有相同父节点的各结点称为兄弟。
从根到某一节点经过的边数称为路径长度。
6、二叉树
二叉树是一种树形结构，其特征是任意结点的孩子数不超过两个。一棵二叉树要么为空，要么由根、左子树与右子树组成（左右子树可能为空）。
一棵深度（树的层数）为m，且具有2m-1个结点的二叉树称为满二叉树。
当一棵二叉树的所有结点编号（从上到下，从左到右进行）都与满二叉树一致时，该二叉树称为完全二叉树。
7、树的遍历
分为三种：先序遍历、中序遍历、后序遍历
先序：先根》左子树》右子树
中序：左子树》根》右子树
后序：左子树》右子树》根
8、哈希表
将一组关键字映射到一个有限的地址集上，这种表称为哈希（散列）表。哈希表中，关键字映射到相应的地址需要使用相关的算法，称为哈希函数。关键字映射后所得的存储地址称为哈希（散列）地址。
9、集合
集合就是一系列元素的整体。
集合就像是一个容器，可以存放与获取元素，与数组相似。不同的是，集合提供了很多有用的方法，用来操作与管理集合内的元素，而数组提供的方法很有限。
集合和数组对比：
缺点：集合的实现比数组更加复杂，因此，其性能上不如数组。
优点：
集合时不定长的，底层可以根据需要实现自动的扩容。而数组是定长的，我们在创建数组的时候就需要指定数组的长度。
集合提供了很多有用的方法，可以操作集合内的元素，而数组提供的功能相对有限。
10、集合框架
11、集合分类：
Collection接口提供元素存储。
Map接口提供映射存储（键值对）
package day14;
/*
* 集合
* 集合与数组类型，类比一个容器，可以向里面加入元素。
* 集合与数组的对比：
* 缺点：集合的实现比数组更加复杂，因此，其性能上不如数组。
* 优点：
* 1 集合是不定长的，底层可以根据需要实现自动的扩容。
* 而数组是定长的，我们在创建数组的时候就需要指定数组的长度。
* 2 集合提供了很多有用的方法，可以操作集合内的元素，而数组
* 提供的功能相对有限。
*/
public class CollectionTest {
public static void main(String[] args) {
}
}
12、
Collection 最基本的集合接口。用来存储一系列元素。
Set继承Collection接口，不含有重复元素。
List 继承Collection接口，List是有序集合，能精确控制每个元素插入的位置，可使用索引来访问List中的元素。
Queue继承Collection接口。通常实现先进先出（FIFO）的规则，但这不是必须的。删除（获取）元素时，会获取队列头部的元素。先进先出的队列中，增加元素会追加到队列的末尾。
Deque继承Queue接口。可同时在队列的两端增加与删除元素。
Map接口提供key(键)到value(值)的映射，是一组成对的键－值对象。一个Map中不能有相同的key，每个key只能映射一个value。
SortedSet继承Set接口，内部元素按照升序排列。
SortedMap继承Map接口，key按照升序排列。
13、collection常用方法
package day14;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class CollectionMethod {
public static void main(String[] args) {
Collection<Integer> c = new ArrayList<>();
for (int i = 0; i < 10; i++) {
c.add(i);
}
// 返回集合中元素的个数。
System.out.println(c.size());
// 判断集合是否为空（集合元素个数是否为0），为空
// 返回true，否则返回false。
System.out.println(c.isEmpty());
// 判断集合中是否含有参数指定的元素（根据元素的equals方法）。
// 有返回true，否则返回false。
System.out.println(c.contains(5));
// 返回集合的迭代器，可以用来遍历集合每一个元素。
Iterator<Integer> iter = c.iterator();
// 将集合转换成数组，数组中的元素就是之前集合中的元素。
// 返回Object[]类型。
Object[] o = c.toArray();
Integer[] inte = new Integer[c.size()];
Integer[] i = c.toArray(inte);
// 向集合中加入参数指定的元素。如果当前集合发生改变，
// 返回true，否则返回false。
c.add(11);
// 删除集合中参数指定的元素。如果当前集合发生改变，
// 返回true，否则返回false。
c.remove(1);
Collection<Integer> c2 = new ArrayList<>();
c2.add(5);
c2.add(100);
// 判断当前集合是否包含参数指定集合中所有的元素。是
// 则返回true，否则返回false。
System.out.println(c.containsAll(c2));
// 将参数集合中所有的元素加入到当前集合中。如果当前集合
// 发生改变，返回true，否则返回false。
System.out.println(c.addAll(c2));
// 删除当前集合中存在，并且参数集合中也存在的所有元素。
// 如果当前集合发生改变，返回true，否则返回false。
System.out.println(c.removeAll(c2));
// 删除满足条件的所有元素。
c.removeIf(t -> t > 5);
System.out.println(c);
Collection<Integer> c3 = new ArrayList<>();
c3.add(100);
c3.add(101);
Collection<Integer> c4 = new ArrayList<>();
c4.add(100);
c4.add(102);
// 保留当前集合中存在，并且参数集合中也存在的所有元素。
// 即删除所有当前集合中存在，参数集合中不存在的所有元素。
// 如果当前集合发生改变，返回true，否则返回false。
c3.retainAll(c4);
System.out.println(c3);
// 删除集合中所有的元素。
c3.clear();
}
}
14、遍历集合方式
可以使用以下方式来遍历集合： 使用iterator接口。（原始方法） 使用iterator接口。（新增方法） 使用增强型for循环。 使用forEach方法。 使用聚合操作。
package day14;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import org.omg.Messaging.SyncScopeHelper;
public class Tranverse {
public static void main(String[] args) {
Collection<Integer> c = new ArrayList<>();
for (int i = 0; i < 5; i++) {
c.add(i);
}
/*
* 1 使用Iterator迭代器（原始的方法）
*/
// 返回集合的迭代器，迭代器的指针初始指向第一个元素之前。
Iterator<Integer> iter = c.iterator();
// 判断是否还有下一个元素，如果存在下一个元素，返回true，
// 否则返回false。
while (iter.hasNext()) {
// 获取下一个元素。同时移动当前的指针，指向当前
// 返回的元素。
Integer integer = iter.next();
System.out.println(integer);
// System.out.println(iter.next());
// 使用迭代器迭代的过程中，不能通过集合引用
// 删除元素，否则会产生ConcurrentModificationException异常。
// c.remove(0);
// 如果要在迭代的过程中删除元素，可以调用迭代器的
// remove方法。该方法会删除最后一次调用next
// 返回的元素。
// iter.remove();
}
/*
* 2 使用Iterator接口迭代器（JDK1.8新增的方法）
*/
Iterator<Integer> iter2 = c.iterator();
// 对每一个剩下的元素（当前迭代器
// 指针之后的元素）执行指定的操作。
iter2.forEachRemaining(t -> System.out.println(t));
// 使用方法引用
iter2.forEachRemaining(System.out::println);
/*
* 3 使用增强型for循环遍历
*/
for (Integer i : c) {
System.out.println(i);
}
/*
* 4 使用集合类的forEach方法。
*/
c.forEach(t -> System.out.println(t));
c.forEach(System.out::println);
/*
* 5 使用聚合操作
*/
c.stream().forEach(System.out::println);
}
}
15、List接口的方法
/*
* List接口的方法
*/
package day14;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class ListMethod {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 5; i > 0; i--) {
list.add(i);
}
List<Integer> list2 = new ArrayList<>();
for (int i = 5; i < 10; i++) {
list2.add(i);
}
// 将参数集合中的元素加入到当前list的最后面。（追加）。
// list.addAll(list2);
// 将参数集合（第2个参数）中的所有元素加入到当前集合
// 指定的位置（第1个参数）处。
// list.addAll(3, list2);
// list.forEach(System.out::println);
// 对List中的每一个元素进行替换。
// list.replaceAll(t -> t * 2);
// 对list元素进行排序。参数为比较器，如果想实现元素
// 自然排序，参数传递null值。
// list.sort(null);
// list.sort((a, b) -> a - b);
// 返回指定索引位置的元素。
// list.get(0);
// 将索引位置的元素（第1个参数）使用第二个参数指定
// 的元素进行替换。
// list.set(0, 1000);
// 在索引位置（第1个参数）插入元素（第二个参数指定）
// list.add(0, 1000);
// 删除参数指定位置（索引）的元素。
// list.remove(0);
// 返回参数元素在List中首次出现的位置。
// 如果没有出现，返回-1。
System.out.println(list.indexOf(12));
// 返回参数元素在List中最后一次出现的位置。
// 如果没有出现，返回-1。
System.out.println(list.lastIndexOf(12));
// list.forEach(System.out::println);
// 返回List特有的迭代器。指针指向第一个元素之前。
ListIterator<Integer> li = list.listIterator();
// 返回List特有的迭代器。指针指向参数指定位置的元素之前。
// 下次调用next()方法会返回参数指定位置的那个元素。
li = list.listIterator(2);
// 返回子List，第1个参数指定开始点。第2个参数指定结束点。
// 包括起始点，不包括结束点。
List<Integer> sub = list.subList(1, 3);
}
}
16、
ArrayList与LinkedList List接口有两个常用的实现类： ArrayList LinkedList 二者的不同在于： ArrayList底层使用数组来实现的，而 LinkedList是使用链表（数据域+指针域）的方式实现的。当随 机访问元素操作多的时候，优先使用ArrayList，当增加与删除 操作多的时候，优先使用LinkedList。
package day14;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class ListIteratorMethod {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(11);
list.add(33);
ListIterator<Integer> i = list.listIterator(1);
// 判断是否存在前一个元素，如果存在，返回true，
// 否则返回false。
System.out.println(i.hasPrevious());
// 返回前一个元素。
i.previous();
// 返回下一个元素的索引。即下次调用next方法返回元素的索引。
i.nextIndex();
// 返回前一个元素的索引。即下次调用previous返回元素的索引。
i.previousIndex();
// 删除最后一次调用next或previous方法返回的元素。
i.remove();
// 将最后一次调用next或previous方法返回的元素设置（替换）
// 成参数指定的元素。
i.set(2);
// 在当前指针位置之前进行插入。（对下次调用next没有影响）。
i.add(100);
}
}
17、set接口
/*
* Set接口
* Set接口中的元素是不允许重复。是否重复
* 根据equals方法（或compareTo方法）进行判断的。
* Set接口没有新增的方法（相对Collection接口）。
*/
18、hashSet实现类
/*
* HashSet实现类
*/
package day14;
import java.util.HashSet;
import java.util.Set;
public class HashSetTest {
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
set.add(100);
set.add(-2);
set.add(16);
set.add(-212);
// 没有加入成功，返回false。因为元素重复了。
// System.out.println(set.add(-2));
// System.out.println(set.size());
// HashSet使用元素的哈希码（hashCode）来计算
// 元素的存储位置。因此，我们不能保证元素获取的顺序
// 与元素加入时的顺序是一致的。
set.forEach(System.out::println);
}
}
19、LinkedHashSet
package day14;
import java.util.LinkedHashSet;
import java.util.Set;
/*
* LinkedHashSet
* LinkedHashSet是HashSet的子类，其底层使用一个
* 双向链表来维护元素的顺序，因此，获取元素时（遍历元素
* 时），可以保证获取的顺序与元素加入时的顺序一致。
*/
public class LinkedHashSetTest {
public static void main(String[] args) {
Set<Integer> set = new LinkedHashSet<>();
set.add(100);
set.add(-2);
set.add(16);
set.add(-212);
set.forEach(System.out::println);
}
}
20、SortedSet
/*
* SortedSet接口
* 规范：加入的元素可以自动实现升序排列。
*/
package day14;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortedSetTest {
public static void main(String[] args) {
SortedSet<Integer> set = new TreeSet<>();
set.add(100);
set.add(20);
set.add(50);
set.forEach(System.out::println);
//TreeSet无参的构造器，使用自然排序。
SortedSet<Box> set2 = new TreeSet<>();
set2.add(new Box(100));
set2.add(new Box(20));
set2.add(new Box(50));
set2.forEach(System.out::println);
// 也可以在创建TreeSet对象时，指定比较器。
// 这样就可以指定自己的比较规则。如果我们显式的
// 指定了比较器，此时就不会使用自然排序。
SortedSet<Box> set3 = new TreeSet<>((a, b) -> b.getValue() - a.getValue());
set3.add(new Box(100));
set3.add(new Box(20));
set3.add(new Box(50));
set3.forEach(System.out::println);
}
}
class Box implements Comparable<Box> {
private int value;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Box(int value) {
super();
this.value = value;
}
@Override
public int compareTo(Box o) {
return value - o.value;
}
@Override
public String toString() {
return "Box [value=" + value + "]";
}
}
21、SortedSet接口
package day14;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortedSetMethod {
public static void main(String[] args) {
SortedSet<Integer> set = new TreeSet<>();
// SortedSet<Integer> set = new TreeSet<>((a, b) -> b - a);
for (int i = 0; i < 10; i++) {
set.add(i);
}
// 返回比较器，如果没有指定比较器，返回null。
// System.out.println(set.comparator());
// 返回子SortedSet，第1个参数指定起始点，第2个参数指定
// 终止点，包括起始点，不包括终止点。
SortedSet<Integer> subSet = set.subSet(3, 100);
// subSet.forEach(System.out::println);
// 返回子SortedSet，从头开始，到参数指定的位置结束。
// 不包括参数指定的位置（终止点）。
SortedSet<Integer> head = set.headSet(8);
// head.forEach(System.out::println);
// 返回子SortedSet，从参数指定的位置开始，到Set结束。
// 包括参数指定的位置（起始点）。
SortedSet<Integer> tail = set.tailSet(3);
tail.forEach(System.out::println);
// 返回最开始的元素（最小的元素）。
System.out.println(set.first());
// 返回最末的元素（最大的元素）。
System.out.println(set.last());
}
}
22、 NavigableSet接口 （NavigableSet接口是SortedSet接口的子接口。扩展了一些导航的方法。可以用于更准确的定位）
package day14;
import java.util.Iterator;
import java.util.NavigableSet;
import java.util.TreeSet;
public class NavigableSetMethod {
public static void main(String[] args) {
NavigableSet<Integer> set = new TreeSet<>();
for (int i = 10; i > 0; i--) {
set.add(i);
}
// set.forEach(System.out::println);
// 返回小于参数的最大元素。如果不存在，返回null。
System.out.println(set.lower(-1));
// 返回小于等于参数的最大元素。如果不存在，返回null。
System.out.println(set.floor(5));
// 返回大于等于参数的最小元素。如果不存在，返回null。
System.out.println(set.ceiling(2));
// 返回大于参数的最小元素。如果不存在，返回null。
System.out.println(set.higher(8));
// 删除并返回最开始的元素（最小的元素）。如果没有元素，
// 返回null。
// System.out.println(set.pollFirst());
// 删除并返回最末尾的元素（最大的元素）。如果没有元素，
// 返回null。
// System.out.println(set.pollLast());
// 返回降序排列的NavigableSet
NavigableSet<Integer> de = set.descendingSet();
// de.forEach(System.out::println);
// 返回降序的迭代器
Iterator<Integer> iter = set.descendingIterator();
iter.forEachRemaining(System.out::println);
set.subSet(2, 7);
// 第1个参数：起始点，第3个参数：终止点
// 第2个参数：是否包含起始点。
// 第4个参数：是否包含终止点。
set.subSet(2, true, 7, false);
set.headSet(8);
// 第2个参数指定是否包含终止点。
set.headSet(8, false);
set.tailSet(3);
// 第2个参数指定是否包含起始点。
set.tailSet(3, true);
}
}
23、NavigableSet接口的实现类
TreeSet是AbstractSet的子类，实现NavigableSet 接口。当
向TreeSet中添加元素时，这些元素会自动进行排序。
TreeSet默认情况下使用自然排序，但也可自己制定排序方式。
在创建TreeSet对象时，传递一个实现了Comparator接口的
类的对象。