Java常见基础数据结构

目录
  • 栈：
  • 队列：
  • 数组：
  • 链表：
  • 红黑树：
  • 总结

栈：

stack，又称堆栈，他是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

简单的来说，采用该结构的集合，对元素的存取有如下几个特点

1、先进后出。

2、栈的入口、出口都是栈的顶端位置。

压栈：就是存元素，把元素存储到栈的顶端位置，栈中已有元素一次向栈底方向移动一个位置。

弹栈：就是取元素，把栈顶端的元素取出，栈中已有元素依次向栈顶方向移动一个位置。

队列：

queue，简称队，它同堆栈一样，也是运算受限的线性表，其限制是只允许在表的一端进行插入，而在表的另一端进行删除。

简单来说，采用该结构的集合，对元素的存取有如下的特点：

1、先进先出

2、队列的入口、出口各占一侧，例如左侧为入口，右侧为出口

数组：

Array，是一个有序的元素序列，数组是在内存中开辟出一端连续的空间，并在此空间存放元素，可以通过索引快速找到对应的数据。

采用此方式存储数据有如下几个特点：

1、查找元素快，通过索引可以快速访问指定位置的元素。

2、增删元素慢，在指定索引位置增加元素，需要创建一个新的数组，将指定新元素存储在指定的索引位置，然后再把原数组元素根据索引，复制到新数组对应的索引位置

删除元素，需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。

链表：

Linked List，由一系列结点node组成，结点可以在运行时动态生成。每个结点包括两部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表分为单向链表和双向链表，双向链表是指有上一个结点的引用和下一个结点的指针，单向链表是只有下一个结点的指针。

简单的说，采用该数据结构的集合，对数据的存储有如下几个特点：

  • 多个结点之间，通过地址进行连接。
  • 查询慢，如果想查找某个元素，需要通过连接的结点依次向后查找。
  • 增删快，只需要修改连接下一个元素的地址即可。

红黑树：

二叉树：是每个结点不超过2的有序树

简单理解，二叉树是每个结点最多有两个子树的树结构。顶上的叫根节点，两边被称作为左子树和右子树。

红黑树本身就是一颗二叉查找数，将节点插入后，该数仍然是一颗二叉查找数，也就意味之数的键值仍然是有序的。

红黑树的约束：

  • 节点可以是红色的或者黑色的
  • 根节点是黑色的
  • 叶子节点是黑色的
  • 每个红色节点的子节点都是黑色的
  • 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点：

速度特别快，趋近平衡树，查找叶子元素最少和最多次数不多于两倍。

总结

本篇文章就到这里了，希望可以帮到你，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • Java数据结构之链表相关知识总结

    Java数据结构之链表相关知识总结

    一.链表 1.1 概述 链表是真正动态的数据结构,最简单的动态数据结构,基本用于辅助组成其他数据结构. 数据存储在"节点"(Node)中 优点:真正的动态,不需要处理固定容量的问题 缺点:丧失了随机访问的能力 1.2 链表使用的基本功能 定义Node节点 private class Node{ public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public

  • Java数据结构之链表实现（单向、双向链表及链表反转）

    Java数据结构之链表实现（单向、双向链表及链表反转）

    前言 之前学习的顺序表查询非常快,时间复杂度为O(1),但是增删改效率非常低,因为每一次增删改都会元素的移动.可以使用另一种存储方式-链式存储结构. 链表是一种物理存储单元上非连续.非顺序的存储结构.链表由一序列的结点(链表中的每一个元素成为结点)组成. 结点API设计: 类名 Node 构造方法 Node(T t,Node next) 创建Node对象 成员变量 T item:存储数据 Node next :指向下一个结点 结点类: public class Node<T>{ Node ne

  • 详解Java集合中的基本数据结构

    详解Java集合中的基本数据结构

    集合中三大数据结构 数组 内存地址连续 可以通过下标的成员访问,下标访问的性能高 增删操作有较大的性能消耗(需要动态扩容) 链表(双向链表) 灵活的空间要求,存储空间不要求连续 不支持下标访问,支持顺序遍历搜索 针对增删操作找到对应的节点改变链表的头尾指针指向即可,无需移动元数据存储位置 树(Java中二叉树特性) 某节点的左子树节点仅包含小于该节点的值 某节点的右子树节点仅包含大于该节点的值 节点必须是二叉树 顺序排列 存在问题:树可以认为是介于数组和链表二者之间的一种数据结构,拥有较快的查询

  • 浅谈Java数据结构之稀疏数组知识总结

    浅谈Java数据结构之稀疏数组知识总结

    稀疏数组 当一个数组中的元素大多为0或者相同元素的时候,可以用稀疏数组来压缩 稀疏数组只记录 行row 列col 值value 将下列的二维数组转为稀疏数组,如下两图所示 1.实现二维数组转为稀疏数组的步骤: 遍历数组,得到数组中 不为0的个数,并记录为sum,作为稀疏数组第0行的 value 遍历数组,将数组中不为0的数的行和列和值分别写入稀疏数组的 row col val 中 代码实现: public class SparseArray { public static void main(S

  • Java数据结构之链表的增删查改详解

    Java数据结构之链表的增删查改详解

    一.链表的概念和结构 1.1 链表的概念 简单来说链表是物理上不一定连续,但是逻辑上一定连续的一种数据结构 1.2 链表的分类 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构. 单向和双向,带头和不带头,循环和非循环.排列组合和会有8种. 但我这只是实现两种比较难的链表,理解之后其它6种就比较简单了 1.单向不带头非循环链表 2.双向不带头非循环链表 二.单向不带头非循环链表 2.1 创建节点类型 我们创建了一个 ListNode 类为节点类型,里面有两个成员变量,val用来存储数值

  • Java常见基础数据结构

    目录 栈: 队列: 数组: 链表: 红黑树: 总结 栈: stack,又称堆栈,他是运算受限的线性表,其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行添加.查找.删除等操作. 简单的来说,采用该结构的集合,对元素的存取有如下几个特点 1.先进后出. 2.栈的入口.出口都是栈的顶端位置. 压栈:就是存元素,把元素存储到栈的顶端位置,栈中已有元素一次向栈底方向移动一个位置. 弹栈:就是取元素,把栈顶端的元素取出,栈中已有元素依次向栈顶方向移动一个位置. 队列: queue,简称队

  • Java常见基本数据结构概览

    Java数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科.在Java数据结构中最常用的类型无外乎以下几种: Map接口 请注意,Map没有继承Collection接口,Map提供key到value的映射.一个Map中不能包含相同的key,每个key只能映射一个value. Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射. List接口 List是有序的Collection,用户能

  • Java编程基础测试题分享

    单选题:(每道题目2分) 1. 下列哪个声明是错误的?(B) A.  int i=10; B.  float f=1.1;     //float f=1.1f C.  double d=34.4; D.  byte b=127; long类型的数据加后缀L或者l float类型的数据加后缀F或者f 整数默认是int类型 浮点数默认是double类型 2. 下面哪个不是java中的关键字?(C) A. public B.  true C.  main D.  class 3. 下面程序哪个语句是

  • Java异常基础知识解析

    Java异常基础知识解析

    Java程序运行的非正常现象叫做运行错误,根据其性质可分为两类:错误(Error)和异常(Exception); 他们有一个共同的父类(也是所有异常的顶级父类):Throwable. 异常类结构 Error Error(错误)由JVM生成并抛弃不做处理:此类错误通常与代码和执行的操作无关,是虚拟机中出现了比较严重的问题,程序本身无法解决(常见的错误有死循环.内存泄漏等). 一个常见的错误为Java虚拟机错误(VirtualMachineError),当JVM不再有继续执行操作所需的内存资源时,将

  • Java递归基础与递归的宏观语意实例分析

    本文实例讲述了Java递归基础与递归的宏观语意.分享给大家供大家参考,具体如下: 1.什么是递归 本质上,将原来的问题,转化为更小的同一问题 2.例子分析 假设我们需要对数组进行求和操作(只是为了更好理解递归程序) 要求如下:求解从索引为0到n-1的数组元素和. 分析: 为了能求解从索引为0到n-1的数组元素和,可以分解为第0个数加上索引从1到n-1的数组元素和,如下: 此时求解索引从1到n-1的数组元素和的规模比求解从索引为0到n-1的数组元素和要少一个数以此类推,如下: ....... 最基

  • Java 常见的并发问题处理方法总结

    Java 常见的并发问题处理方法总结

    好像挺久没有写博客了,趁着这段时间比较闲,特来总结一下在业务系统开发过程中遇到的并发问题及解决办法,希望能帮到大家

  • 浅谈Java常见的排序算法

    浅谈Java常见的排序算法

    目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 七.归并排序 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(String[] args) { int [] ar

  • Java最简洁数据结构之冒泡排序快速理解

    Java最简洁数据结构之冒泡排序快速理解

    目录 一.什么是冒泡排序 二.图解冒泡排序 三.代码实现 四.代码的优化 1.整体的思路 2.代码示例 一.什么是冒泡排序 冒泡排序的英文是bubble sort,它是一种基础的交换排序.说到冒泡是不是就想起了快乐肥宅水呢?汽水中有许多小小的水泡哗啦哗啦的浮到上面来.这是因为组成小气泡的二氧化碳比水轻,所以小气泡可以一点一点地向上浮动. 而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身的大小,一点一点的向着数组的一侧移动. 二.图解冒泡排序 我们先看一个例

  • Java编程基础元素-运算符

    Java编程基础元素-运算符

    目录 1 前言 2 算术运算符 2.1 四则运算 2.2 字符串运算符 2.3 一元运算符 3 关系运算符 4 逻辑运算符 5 位运算符 6 码农洞见 6.1 运算符思维导图 6.2 运算符优先级 1 前言 运算符就是在用变量或常量进行运算时,经常需要用到的运算符,Java 提供了丰富的运算符,可分为4类:算术运算符.关系运算符.逻辑运算符和位运算符. 2 算术运算符 2.1 四则运算 算术运算符的用途类似一般数学运算中的加(+).减(-).乘(×)和除(/)四则运算,是经常使用的数学运算符.这

  • Java深入了解数据结构之哈希表篇

    Java深入了解数据结构之哈希表篇

    目录 1,概念 2,冲突-避免 3,冲突-避免-哈希函数设计 4,冲突-避免-负载因子调节 5,冲突-解决-闭散列 ①线性探测 ②二次探测 6,冲突-解决-开散列/哈希桶 7,完整代码 1,概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较.顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中 元素的比较次数. 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素. 如果构造一

随机推荐