简单数据结构

数据结构简单的可分为线性结构（主要是线性表）和非线性结构（主要是树和图）。

线性表定义：由n个数据元素（节点）组成的有限序列。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。
在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。
线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

顺序存储结构：

用一组地址连续的存储单元一次存放线性表的元素；数据元素的物理关系和逻辑关系是一致的。 底层通常采用数组来存储数据元素。 loc（ai）=loc(a0)+i*b; 一种随机存取的存储结构。（ArrayList）

链式存储结构：

简称为链表，采用一组地址任意的存储单元存放数据元素。 由于不必按顺序存储，所以插入、删除元素比顺序线性表快很多，但查找慢。缺点是（基于数组）需要预先知道数据大小。同时增加了节点的指针域，空间开销更大。 节点=数据元素+下一个节点的引用+上一个节点的引用。

单链表：每个节点只保留一个引用，指向下一个节点。    插入方式：头和尾；     查找方式：index  指定element元素。  随机存储性能较好，插入删除较差（对比顺序存储结构）
循环链表：首尾相连的链表。   tail.next=header。伪循环链表在访问到最后一个节点之后，手工地跳转到第一个节点。 
双向链表：每个节点保留两个引用prev 和next。对称结构，克服了单链表上指针单向性的缺点，即每个节点可以向前和向后引用，更快的插入、删除数据。（LinkedList） 

栈和队列：

栈是一种特殊的线性表，不支持普通线性表中的：获取指定索引值；查找；插入制定位置；删除指定位置 操作。只允许在栈顶插入、删除数据。
顺序栈：基于数组， 出栈入栈效率高，缺点是数组需要确定长度。
链栈：基于链表， 操作效率略低，但是空间利用率高。

队列

是一种只允许一端插入一端删除的线性表。
顺序队列： 基于数组，会出现假满现象（数组下标移动到数组末尾，而前面已删除），所以有循环队列（归零处理）。
链式队列：基于链式存储结构。

双向队列：（Deque）可以在两端同时插入和删除。 （LinkedList） 即可以说是Queue的子接口也可以是Stack（并不是接口）的子接口。

非线性表：

树和二叉树：

节点的度：节点拥有的子树个数 树的深度：节点的最大层次（高度）
树的两种表示方法：父节点表示法（每个节点都可以快速地找到它的父节点）和子节点表示法（每个节点都可以快速地找到它的子节点）。

二叉树：每个节点最多只能包含左、右节点。

顺序存储：基于数组，可能造成内存浪费（如果不是完全二叉树）。
二叉链表存储：基于链式存储，让每个节点都能记住它的左右子节点。
三叉链表存储：增加了父节点

遍历二叉树：针对基于链表存储的二叉树。

哈夫曼树：带权路径最短的二叉树。

排序二叉树：左子节点->父节点->右子节点 由小到大 （按照中序遍历可得到有序序列） 如果插入的数列本就有序，那么排序二叉树会得到只有左子树（序列从小到大排序）或者只有右子树（序列从大到小排序）。那么排序二叉树就变成了普通链表，检索效率就会很差。

红黑树：改进的二叉树。（TreeMap）
重要性质：根节点为黑，叶节点为空节点且为黑；从任意节点到其子树中每个子节点的路径包含相同数量的黑色节点；红节点的两个子节点都为黑。
带来的效果：并不是平衡二叉树，但检索性能更好。

参考：《疯狂Java：突破程序员基本功的16课》

最后

以上就是勤恳牛排为你收集整理的简单数据结构的全部内容，希望文章能够帮你解决简单数据结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。