java数据结构及算法总结 _java

数组：数组是一种连续存储线性结构，元素类型相同，大小相等，数组是多维的，通过使用整型索引值来访问他们的元素，数组尺寸不能改变。

数组的优点：
存取速度快
数组的缺点：
事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低

1.collection 和 collections
collection ：集合类的上层接口，子接口主要有list ，set，queue等
collections：提供对集合进行搜索，排序，替换和线程安全化等操作的工具类。
arrayList，LinkedList，Vector
arraylist：动态数组；基于数组实现；
linkedList：有序数组；基于双向链表实现；
vector：对象容器，可放入不同类的对象（基于数组实现）；
linkedHashMap ，TreeMap ,TreeSet
linkedHashMap：顺序存取hashMap（基于数组和双向链表实现）；
TreeMap：内部排序（基于黑色树实现）；
TreeSet：有序的set集合（基于二叉树）；
链表：n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。
确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来。

文章插图

链表优点
空间没有限制
插入删除元素很快
链表缺点
存取速度很慢

链表又细分了3类：

单向链表
一个节点指向下一个节点。
双向链表
一个节点有两个指针域。
循环链表
能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环。

操作链表要时刻记住的是：节点中指针域指向的就是另一个节点！
栈和队列数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用。
我们将栈可以看成一个放光盘的箱子，箱口与略大与光盘。然后

往箱子里面放东西叫做入栈
往箱子里面取东西叫做出栈
箱子的底部叫做栈底
箱子的顶部叫做栈顶

文章插图

说到栈的特性，有一句经典的言语来概括：先进后出，后进先出。
JAVA实现栈

使用数组实现的叫静态栈
使用链表实现的叫动态栈

队列队列非常好理解，我们将队列可以看成我们平时排队打饭。

有新的人加入了 -> 入队
队头的人打饭了 -> 出队

相对于栈而言，队列的特性是：先进先出，后进后出

文章插图

队列

使用数组实现的叫静态队列
使用链表实现的叫动态队列

二叉树树是一种非线性的数据结构，相对于线性的数据结构(链表、数组)而言，树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高)，
和现实中的树相比，编程的世界中的树一般是“倒”过来看，这样容易我们分析。

文章插图

现实中的树是有很多很多个分支的，分支下又有很多很多个分支，如果在程序中实现这个会非常麻烦。因为本来树就是非线性的，而我们计算机的内存是线性存储的，太过复杂的话无法设计出来。
因此，就有了简单又经常用的 -> 二叉树，顾名思义，就是每个分支最多只有两个的树，上图就是二叉树。

一棵树至少会有一个节点(根节点)
树由节点组成，每个节点的数据结构包括一个数据和两个分叉

堆和堆栈堆内存用来存放由new创建的对象和数组。
在堆中分配的内存，由Java虚拟机的自动垃圾回收器来管理。
'堆栈' 就是 '栈'，称呼不同而已。
【java数据结构及算法总结】栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。另外，栈数据可以共享。
堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。