基于最近面试发现基础掌握不牢靠，重新梳理一下各个知识。

数据结构：数据元素相互之间的关系称为结构。

逻辑结构：

• 集合结构：除了同属于一种类型外，没有其他关系
• 线性结构：元素之间存在一对一关系常见类型有:数组,链表,队列,栈,它们之间在操作上有所区别。
• 树形结构：元素之间存在一对多关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等)。
• 图形结构：元素之间存在多对多关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。

物理结构：

• 顺序存储结构：用物理位置的相邻关系表示数据元素之间的逻辑关系。
• 链式存储结构：对每一个数据元素用一块较小的连续区域存放，称为节点，然后用指针表示逻辑关系，在节点中设置一个或多个指针，指向它的前驱或后继元素的地址。
• 索引存储结构：这是一种顺序加链式的存储方式，数据元素按顺序结构存放，然后将每个数据元素的关键字和存储地址构造一个索引表单独储存，这种存储结构不表示元素之间的关系。
• 哈希存储结构：数据元素按顺序或链式存储，并在数据元素的关键字与存储地址之间建立一种映射，这种存储结构不表示元素之间的关系。

常用的数据结构有：

• 数组： 存储多个相同类型的数据的集合。

  特点：
  • 数组中的数据元素可以是基本数据类型，也可以是引用数据类型；
  • 数组具有下标，下标从0开始计数，用于快速获取数组中的数据，比如a[0]，表示数组中的第一个数据；
  • 数组在创建的时候，需要在内存中申请一段固定长度的内存，如果申请的长度超过内存剩余的长度，则容易产生碎片，导致存储失败；
  • 数组分为数值数组，字符数组，指针数组，结构数组等；

  数组的优点是：get和set操作时间上都是O(1)的；缺点是：add和remove操作时间上都是O(N)的。

• 栈：一种只能在一端进行数据插入和删除操作的线性表，又名堆栈。允许插入、删除操作的一端是栈顶、另一端是栈底。

  特点：

  • 按照先进后出的原则存储数据；
  • 栈分为顺序栈和链式栈；

• 队列：一种特殊的线性表，只能在队头进行删除数据操作，在队尾进行增加数据操作。

  特点：
  • 遵循先进先出的原则存储数据；
  • 队列分为顺序队列和循环队列；

• 链表：一种非连续，非顺序的存储方式，通过指针将数据进行连接的方式实现。 特点：

  • 在创建的时候，不需要指定长度，可以动态调整长度，不易产生碎片；
  • 链表的每个元素分为数据和指针，指针指向下一个数据的地址，从而形成串联；
  • 便于数据增删，不便于数据查询；
  • 链表分为单向链表，双向链表，循环列表；

  链表的优点是：add和remove操作时间上都是O(1)的；缺点是：get和set操作时间上都是O(N)的，而且需要额外的空间存储指向其他数据地址的项。查找操作对于未排序的数组和链表时间上都是O(N)。

• 树：由一个根节点和若干个子树构成的集合。 特点：

  • 有且仅有一个根节点；
  • 子树之间不可以有交集；
  • 树的深度指的是树的有多少层；
  • 一个节点的度指的是该节点下有多少个子节点；
  • 二叉树指的是每个结点的度≤2的树。
  • 树的遍历方式分为三种，分别是前序遍历（根左右），中序遍历（左根右），后序遍历（左右根）；
  • 树分为无序树，有序树，二叉树等；

• 堆：用于动态分配和释放程序所使用的对象。 特点：

  • 堆是一棵完全二叉树；
  • 分为最小堆和最大堆，区别在于所有父节点是否大于等于其子节点，是则是最大堆，否则反之；

• 散列表： 散列表也叫哈希表，是根据关键键值(Keyvalue)进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数。 特点：
  • 便于插入，查找等操作；
  • key以数组的方式存储在栈内存中，value以链表的方式存储在堆空间中；
  • 不同的key通过哈希函数可能得到相同的结果，这时候就发生了哈希碰撞；