Question

8种数据结构

Answer 1

常见的8种数据结构：数组、链表、栈、队列、树、堆、图、哈希表
1.数组：
优点：按照索引查询元素的速度很快
缺点：数组的大小在创建后就确定了，不方便扩容；数组只能存储一种类型的数据；添加，删除元素的操作很耗时间，因为要移动其他元素

2.链表：
优点：链表在插入，删除的时候可以达到O(1)的时间复杂度并且链表克服了数组必须预先知道数据大小的缺点，从而可以实现灵活的内存动态管理
缺点：含有其他结点的引用，占用内存空间大；查找元素需要遍历整个链表，耗时。

3.栈
栈按照“先进后出”的原则来存储数据，先插入的数据被压入栈底，后插入的数据在栈顶，读出数据的时候，从栈顶开始依次读出。

4.队列
与栈不同，队列对两端进行定义，一端叫队头，另外一端就叫队尾。队头只允许删除操作(出队)，队尾只允许插入操作(入队)。

5.树
<1>.二叉树:每个节点最多含有两个子树，按照左右不同的表现形式又可以分为多种。
<2>完全二叉树：对于一颗二叉树，假设其深度为d.除了第d层，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续的紧密排列
<3>满二叉树：一颗每一层的节点数都达到了最大值的二叉树。

：对于二叉查找树中的任意一个节点如果左子树不为空，那么左子树上所有节点的值均小于它的根节点的值；如果右子树不空，右子树上所有节点的值均大于它的根节点的值。
基于二叉树的特点，它相比较与其它数据结构的优势在于查找、插入的时间复杂度比较低,为O(logn)。

：平衡二叉树本质上也是一颗二叉查找树，不同的是该树中任意节点的两颗子树的高度差不大于1
注：平衡二叉树的难点在于，当删除或者增加节点的情况下，如何通过左旋或者右旋的方式来保持左右平衡。
java中最常见的平衡二叉树就是红黑树，它具有以下特点：
(1)每个节点都只能是红色或者黑色
(2)根节点是黑色
(3)每个叶节点是黑色的
(4)如果一个节点是红色的，则它两个子节点点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点
(5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树。

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

7. :由顶点的有穷非空集合和顶点之间边的集合组成

8. :是一种可以通过关键码值(key-value)直接访问的数据结构，它最大的特点就是结合了数组和链表的优点可以快速实现查找、插入和删除。
哈希函数在哈希表中起着非常关键的作用， ，该输出就是哈希值。

哈希表是是通过数组来实现的，首先对key值进行hash算法得到一个数，然后对该数进行寻址算法计算，得到一个数组中的下标，通过该下标对数据进行存取，解决地址冲突常用方法有链表法。Java里的HashMap使用的是链表法。