image.png

1，数组

优点：
按照索引查询元素的速度很快；
按照索引便利数组也很快
缺点：
数组的大小在创建后就确定了，无法扩容（只能创建新的数组）
数组只能存储一种类型的数组（类型定义后就不能修改）
添加，删除元素的操作很消耗时间，因为要移动其他元素

2 链表

链表是一种递归的数据结构，他或者为空(null)，或者指向一个节点的引用，
该节点还有一个元素和一个指向另外一条链表的引用。
java的LinkedList 类可以很形象的通过代码的形式来表示一个链表的结构

public class LinkedList<E> {
    transient Node<E> first;
    transient Node<E> last;
 
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
 
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

linkedlist在jdk1.6以前是双向循环链表，1.7以后是双向链表
这是一种双向链表，当前元素item既有prev又有next,不过first的prev为null。last
的next为null.如果是单向链表的话，就只有next，没有prev.

image.png

单向链表的缺点是只能从头到尾依次遍历，而双向链表可进可退，既能找到上一个
也可以找到下一个，每个节点上都需要分配有个存储空间。
链表中的数据按照"链式"的结构存储，因此可以达到内存上非连续的效果，数组必须是一块连续的内存。

image.png

由于不必按照顺序的方式存储，链表在插入，删除的时候达到o（1）的时间复杂度(只需要指向引用即可，不需要想数组那样移动其他元素)。除此之外。链表还克服了数组必须预先知道数据大小的缺点从而可以灵活的内存动态管理。
优点：
不需要初始化容量
可以添加任意元素
插入和删除的时候只需要更新引用
缺点
含有大量的引用，占用的空间比较大
查找元素需要遍历整个链表，耗时。

3栈

栈就像水桶一样底部是密封的，顶部是开口，水可以进可以出，用过水桶的小伙伴可以明白，这样一个道理：先进入的水在底部，后进入的水在顶部；后进入的水被先到出来，先进入的水被后到出来，
同理： 栈按照“后进先出”，“先进后出”的原则来存储数据，先插入的数据被压入栈低，后插入的数据在栈顶，读出的数据的时候，从栈顶开始依次读出。

image.png

4 队列

队列就像一段水管一样，2端都是开口的，水从一端进去，然后从另一端出来，先进去的水先出来，后进入的水后出来
和水管有些不同的是，队列会对2端进行定义，一端叫做队头、另一端叫做队尾。队头只允许删除操作（出队），队尾只允许插入的操作（入队）。

image.png
image.png

5树

树是一种典型的非线性结构，他是由n (n>0) 个有限节点组成的一个具有层次关系的集合。

image.png

之所以叫树，是因为这种数据结构看起来就像是一个倒挂的树，只不过根在上，叶在下。树形结构有以下特点：
每个节点都只有有限个子节点或无子节点
没有父节点的节点称为根节点
每个非根节点有且只有一个父节点。
除了根节点外，每个子节点分为多个不相交的子树。

image.png
image.png

6 堆：
堆可以被看做是一颗树的数组对象，具有以下特点：
堆中某个节点的值总是不大于或者不小于其父节点的值
堆总是一颗完全二叉树
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

image.png

再线性结构中，数据元素之间满足唯一的线性关系，每个数据元素（除开第一个和最后一个外均有唯一的前驱和后继）；
在树形结构中，数据元素之间有着明显的层次关系，并且诶个数据元素只与上一层中的一个元素（父节点）以及下一层的多个元素（子节点相关）；
而在图形结构中，节点之间的关系是任意的，图中任意2个数据元素之间都可能相关。
8，哈希表
哈希表（Hash Table），也叫散列表，是一种可以通过关键码值（key-value）直接访问的数据结构，他的最大特点就是可以快速实现查找，插入和删除
数组的最大特点是查找容易，插入和删除困难，而链表正好想法，查找困难，插入和删除容易。哈希表很完美的结合了2者的优点，java的Hashmap在此基础上还加入了树的优点

image.png

哈希函数在哈希表中起着非常重要的作用，他可以把任意长度此输入变换成固定的长度输出，该输出的是哈希值，哈希函数使得一个数据序列的访问过程变得更加迅速有效。通过哈希函数，数据元素能够被很快的进行定位。
若关键字为k，则其值存放在hash(k)的存储位置上。由此，不需要遍历就可以直接取得k对应的值。
对于任意2个不相同的数据块，其哈希值相同的可能性极小，也就是说，对于一个给定的数据块，找到和他哈希值相同的数据块极为困难。再者，对于一个数据块，哪怕改动他的一个比特位，其哈希值的改动也会非常的大----这正是hash存在的价值。
尽管可能性极小，但仍然可能会发生，如果hash冲突了，java的hashmap会在数组的同一个位置上增加链表。如果链表的长度大于8.将会进行红黑树处理---这就是所谓的拉链法（数组加链表）。