数据结构部分总结-创新互联

数组（Array）：

• 数组是有序元素的序列，在内存中的分配是连续的，数组会为存储的元素都分配一个下标（索引），此下标是一个自增连续的，访问数组中的元素通过下标进行访问；数组下标从0开始访问；

• 数组的优点是：查询速度快；

• 数组的缺点是：删除增加、删除慢；由于数组为每个元素都分配了索引且索引是自增连续的，因此一但删除或者新增了某个元素时需要调整后面的所有元素的索引；

总结：数组查询快，增删慢，适用于频繁查询，增删较少的情况；

链表：

• 链表的优点：新增节点、删除节点快；
• 链表的缺点：
  • 1）查询速度慢，查询从头部开始一直查询到尾部，如果元素刚好是在最尾部那么查询效率势必非常低；
  • 2）链表像对于数组多了一个指针域的开销，内存相对占用会比较大；
  • 总结：数据量较小，需要频繁增加，删除操作的场景，查询操作相对较少；

    ---

栈（Stack）：是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出从栈顶放入元素的操作叫入栈（压栈），取出元素叫出栈（弹栈）。

栈的特点：先进后出，Java中的栈内存就是一个栈的数据结构，先调用的方法要等到后调用的方法结束才会弹栈（出栈）；

队列（Queue）：队列与栈一样，也是一种线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。队列的特点是先进先出，从一端放入元素的操作称为入队，取出元素为出队；

队列的特点：先进先出；

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

1）每个节点有0个或多个子节点；
2）没有父节点的节点称为根节点；
3）每一个非根节点有且只有一个父节点；
4）除了根节点外，每个子节点可以分为多个不相交的子树；
5）右子树永远比左子树大，读取顺序从左到右；
树的分类有非常多种，平衡二叉树（AVL）、红黑树RBL（R-B Tree）、B树（B-Tree）、B+树（B+Tree）等，但最早都是由二叉树演变过去的；

二叉树的特点：每个结点最多有两颗子树

堆的特性：如果一个结点的位置为k，则它的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从arr[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆；

(ki<= k2i,ki<= k2i+1)或者(ki >= k2i,ki >= k2i+1)满足前者的表达式的成为小顶堆（小根堆），满足后者表达式的为大顶堆（大根堆）

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧