您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > JAVA

java数据结构及算法总结

时间:2019-08-12 11:04:01  来源:  作者:

数组:

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

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

1.collection 和 collections

collection :集合类的上层接口,子接口主要有list ,set,queue等

collections:提供对集合进行搜索,排序,替换和线程安全化等操作的工具类。

arrayList,LinkedList,Vector

arraylist:动态数组;基于数组实现;

linkedList:有序数组;基于双向链表实现;

vector:对象容器,可放入不同类的对象(基于数组实现);

linkedHashMap ,TreeMap ,TreeSet

linkedHashMap:顺序存取hashMap(基于数组和双向链表实现);

TreeMap:内部排序(基于黑色树实现);

TreeSet:有序的set集合(基于二叉树);

链表:

n个节点离散分配,彼此通过指针相连,每个节点只有一个前驱节点,每个节点只有一个后续节点,首节点没有前驱节点,尾节点没有后续节点。

确定一个链表我们只需要头指针,通过头指针就可以把整个链表都能推出来。

java数据结构及算法总结

 

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

链表又细分了3类:

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

操作链表要时刻记住的是:节点中指针域指向的就是另一个节点!

栈和队列

数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用。

我们将栈可以看成一个放光盘的箱子,箱口与略大与光盘。然后

  • 往箱子里面放东西叫做入栈
  • 往箱子里面取东西叫做出栈
  • 箱子的底部叫做栈底
  • 箱子的顶部叫做栈顶
java数据结构及算法总结

 

说到栈的特性,有一句经典的言语来概括:先进后出,后进先出。

JAVA实现栈

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

队列

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

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

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

 

java数据结构及算法总结

 

 

队列

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

二叉树

树是一种非线性的数据结构,相对于线性的数据结构(链表、数组)而言,树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高),

和现实中的树相比,编程的世界中的树一般是“倒”过来看,这样容易我们分析。

java数据结构及算法总结

 

现实中的树是有很多很多个分支的,分支下又有很多很多个分支,如果在程序中实现这个会非常麻烦。因为本来树就是非线性的,而我们计算机的内存是线性存储的,太过复杂的话无法设计出来。

因此,就有了简单又经常用的 -> 二叉树,顾名思义,就是每个分支最多只有两个的树,上图就是二叉树。

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

堆和堆栈

堆内存用来存放由new创建的对象和数组。

在堆中分配的内存,由Java虚拟机的自动垃圾回收器来管理。

'堆栈' 就是 '栈',称呼不同而已。

栈的优势是,存取速度比堆要快,仅次于直接位于CPU中的寄存器。但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性。另外,栈数据可以共享。

堆的优势是可以动态地分配内存大小,生存期也不必事先告诉编译器,Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是,由于要在运行时动态分配内存,存取速度较慢。

散列表

无论是Set还是Map,我们会发现都会有对应的-->HashSet,HashMap

首先我们也先得回顾一下数据和链表:

  • 链表和数组都可以按照人们的意愿来排列元素的次序,他们可以说是有序的(存储的顺序和取出的顺序是一致的)
  • 这会带来缺点:想要获取某个元素,就要访问所有的元素,直到找到为止,会消耗很多时间。

所以我们需要另外的存储结构:不在意元素顺序,能快速查找元素。其中就有一种常见方式:散列表。

散列表工作原理

散列表为每个对象计算出一个整数,称为散列码。根据这些计算出来的整数(散列码)保存在对应的位置上!即,散列码就是索引。

在Java中,散列表用的是链表数组实现的,每个列表称之为桶。

红黑树

是一种平衡二叉树,TreeSet、TreeMap底层都是红黑树来实现的。

二叉查找树也有个例(最坏)的情况(线性):

java数据结构及算法总结

 

上面符合二叉树的特性,但是它是线性的,完全没树的用处,树是要“均衡”才能将它的优点展示出来,比如下面这种:

 

java数据结构及算法总结

 

因此,就有了平衡树这么一个概念~红黑树就是一种平衡树,它可以保证二叉树基本符合均衡的金字塔结构。都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

它的统计性能要好于平衡二叉树

上图就是一个红黑树,红黑树就字面上的意思,有红色的节点,有黑色的节点。

  • 性质1. 节点是红色或黑色。
  • 性质2. 根节点是黑色。
  • 性质3. 每个叶节点(NIL节点,空节点)是黑色的。
  • 性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

b树:

平衡二叉树的查找效率为O(log2N)与树的深度相关,通过降低树的深度,可以提高查找效率,但是还有一个瓶颈就是,每次查找一次就只能得到一个节点元素,如果查找一次能得到多个节点元素,那么在同样的高度就能够查找更多的元素,从而提高查找效率,因此提出多路查找树。

多路查找树(muitl-way search tree),其每一个结点的孩子数可以多于两个,且每个结点出可以存储多个元素。由于它是查找树,所有元素之间存在某种特定的排序关系。

B树就是一种平衡的多路查找树。

B-树

中所有结点中孩子结点个数的最大值成为B-树的阶,通常用m表示,从查找效率考虑,一般要求m>=3。一棵m阶B-树或者是一棵空树,或者是满足以下条件的m叉树。

1)每个结点最多有m个分支(子树);而最少分支数要看是否为根结点,如果是根结点且不是叶子结点,则至少要有两个分支,非根非叶结点至少有ceil(m/2)个分支,这里ceil代表向上取整。

2)如果一个结点有n-1个关键字,那么该结点有n个分支。这n-1个关键字按照递增顺序排列。

3)每个节点的结构为

节点个数:n;

关键字数组: k[n],这n个关键字按照递增顺序排列

孩子指针数组:p[n + 1], p0<=k1, 之后所有 ki < pi <= ki+1;

B+树

1)在B+树中,具有n个关键字的结点有n个分支,而在B-树中,具有n个关键字的结点含有n+1个关键字。

2)在B+树中,每个结点(除根结点外)中的关键字个数n的取值为ceil(m/2) <= n <=m,根结点的取值范围为1<=n<=m,b树他们的取值范围分别是ceil(m/2) -1<= n <=m-1和1<=n<=m-1。

3)在B+树中叶子结点包含信息,并且包含了全部关键字,叶子结点引出的指针指向记录。

4)在B+树中的所有非叶子结点仅起到一个索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针。

算法:

1.二分查找:又称折半查找;优点是比较次数少,查询速度快,平均性能好,占用系统内存较少,其缺点是:要求待查表为有序表,且插入删除困难。

2.递归算法

递归简单理解就是方法自身调用自身。

排序算法:1.直接插入排序;2.希尔排序,3,选择排序,4.堆排序;5,冒泡排序6,快速排序,7,归并排序,8.基数排序

1.冒泡排序:他重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来,走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成、整个算法的名字由来是因为越小的元素会经由交换慢慢‘浮’到数列的顶端。



Tags:java 数据结构   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
数组:数组是一种连续存储线性结构,元素类型相同,大小相等,数组是多维的,通过使用整型索引值来访问他们的元素,数组尺寸不能改变。 数组的优点: 存取速度快 数组的缺点: 事先必须知道...【详细内容】
2019-08-12  Tags: java 数据结构  点击:(279)  评论:(0)  加入收藏
▌简易百科推荐
面向对象的特征之一封装 面向对象的特征之二继承 方法重写(override/overWrite) 方法的重载(overload)和重写(override)的区别: 面向对象特征之三:多态 Instanceof关键字...【详细内容】
2021-12-28  顶顶架构师    Tags:面向对象   点击:(2)  评论:(0)  加入收藏
一、Redis使用过程中一些小的注意点1、不要把Redis当成数据库来使用二、Arrays.asList常见失误需求:把数组转成list集合去处理。方法:Arrays.asList 或者 Java8的stream流式处...【详细内容】
2021-12-27  CF07    Tags:Java   点击:(3)  评论:(0)  加入收藏
文章目录 如何理解面向对象编程? JDK 和 JRE 有什么区别? 如何理解Java中封装,继承、多态特性? 如何理解Java中的字节码对象? 你是如何理解Java中的泛型的? 说说泛型应用...【详细内容】
2021-12-24  Java架构师之路    Tags:JAVA   点击:(5)  评论:(0)  加入收藏
大家好!我是老码农,一个喜欢技术、爱分享的同学,从今天开始和大家持续分享JVM调优方面的经验。JVM调优是个大话题,涉及的知识点很庞大 Java内存模型 垃圾回收机制 各种工具使用 ...【详细内容】
2021-12-23  小码匠和老码农    Tags:JVM调优   点击:(12)  评论:(0)  加入收藏
前言JDBC访问Postgresql的jsonb类型字段当然可以使用Postgresql jdbc驱动中提供的PGobject,但是这样在需要兼容多种数据库的系统开发中显得不那么通用,需要特殊处理。本文介绍...【详细内容】
2021-12-23  dingle    Tags:JDBC   点击:(13)  评论:(0)  加入收藏
Java与Lua相互调用案例比较少,因此项目使用需要做详细的性能测试,本内容只做粗略测试。目前已完成初版Lua-Java调用框架开发,后期有时间准备把框架进行抽象,并开源出来,感兴趣的...【详细内容】
2021-12-23  JAVA小白    Tags:Java   点击:(11)  评论:(0)  加入收藏
Java从版本5开始,在 java.util.concurrent.locks包内给我们提供了除了synchronized关键字以外的几个新的锁功能的实现,ReentrantLock就是其中的一个。但是这并不意味着我们可...【详细内容】
2021-12-17  小西学JAVA    Tags:JAVA并发   点击:(11)  评论:(0)  加入收藏
一、概述final是Java关键字中最常见之一,表示“最终的,不可更改”之意,在Java中也正是这个意思。有final修饰的内容,就会变得与众不同,它们会变成终极存在,其内容成为固定的存在。...【详细内容】
2021-12-15  唯一浩哥    Tags:Java基础   点击:(17)  评论:(0)  加入收藏
1、问题描述关于java中的日志管理logback,去年写过关于logback介绍的文章,这次项目中又优化了下,记录下,希望能帮到需要的朋友。2、解决方案这次其实是碰到了一个问题,一般的情况...【详细内容】
2021-12-15  软件老王    Tags:logback   点击:(19)  评论:(0)  加入收藏
本篇文章我们以AtomicInteger为例子,主要讲解下CAS(Compare And Swap)功能是如何在AtomicInteger中使用的,以及提供CAS功能的Unsafe对象。我们先从一个例子开始吧。假设现在我们...【详细内容】
2021-12-14  小西学JAVA    Tags:JAVA   点击:(22)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条