当前位置:首页>Java>Java 高级教程>常用Java数据结构及其算法的实现

常用Java数据结构及其算法的实现

作者:githubofrico发布时间:2019-09-14 15:25:54地址:https://dwz.cn/AMenD9kw

本文主要使用Java实现各种经典常用数据结构及其算法,包括但不仅限于链表、栈,队列,树,图等经典数据结构。

单向链表的数据结构及其相关算法

单向链表结构包含两个要素,即头结点head和链表大小size,具体操作包括:

  • 链表的增删

  • 链表是否为空

  • 链表的大小

  • 链表的打印输出

  • 删除链表重复节点

  • 链表倒数第K个元素

  • 链表的反转

  • 链表的倒序输出

  • 链表的中间节点

  • 链表是否有环

  • 链表节点的删除(不知道头结点的情况下)

  • 链表是否相交

  • 链表的交点

详细内容请参考专栏文章: Java链表

栈(顺序栈/链式栈)的数据结构及其相关算法

栈结构包含两个要素,即栈顶指针top和栈大小size,具体操作包括:

  • 压栈操作push

  • 弹栈操作pop

  • 查看栈顶元素peek

  • 查看栈的大小

  • 查看栈是否为空

  • 查看栈的最小元素(O(1)时间复杂度)

详细内容请参考专栏文章: Java栈

队列(基于数组的实现、基于链表的实现和基于栈的实现)的数据结构及其相关算法

队列结构包含三个要素,即队头指针head、队尾指针rear和队列大小size,具体操作包括:

  • 入队操作put

  • 出队操作pop

  • 查看队头元素peek

  • 查看队列的大小

  • 查看队列是否为空

详细内容请参考专栏文章: Java队列

二叉树(链式实现)的数据结构及其相关算法

二叉树结构包含一个要素,即二叉树的根结点,具体操作包括:

  • 以广义表形式的字符串构建二叉树:’()’前表示根结点,括号中左右子树用逗号隔开,逗号不能省略

  • 二叉树的层次/广序遍历算法(辅助队列)

  • 二叉树的前序、中序、后序遍历的递归/非递归算法(辅助栈):对每个节点而言,三种遍历方式都需要遍历该结点三次,三者唯一区别在于该结点的访问时机;特别注意后序遍历的迭代算法的实现

  • 根据二叉树的前序、中序或中序、后序遍历结果构建二叉树

  • 根据二叉树的根结点复制一颗二叉树

  • 二叉树的高度

  • 二叉树的结点总数

  • 二叉树的根结点、孩子节点的获取

  • 以广义表的形式打印二叉树

  • 判断两颗二叉树是否相等

详细内容请参考专栏文章: Java二叉树

堆(数组实现)的数据结构及其相关算法

堆结构实际上是一个完全二叉树,能方便地从中取出最小/大元素,其包含两个要素,即存储数组heap[]和堆大小size。本实现为最小堆,具体操作包括:

  • 堆的构建(创建一个空堆,基于数组的构建)

  • 堆的插入(插入到堆尾,再自下向上调整为最小堆)

  • 堆的删除(删除堆顶元素并用堆尾元素添补,再自上向下调整为最小堆)

  • 堆排序(时间复杂度:O(nlgn),空间复杂度O(1),不稳定):升序排序一般用最大堆,不断地将堆顶元素放到数组最后并缩小堆的范围

  • 堆的打印(树的前序遍历的应用)

详细内容请参考专栏文章: Java堆

二叉搜索树的数据结构及其相关算法

二叉搜索树也叫二叉排序树,其中序遍历及时序列的升序排序。此外,二叉搜索树能方便地从中搜索出指定元素,具体操作包括:

  • 二叉搜索树的构建(基于数组的构建(插入构建))

  • 二叉搜索树的插入(插入到合适位置,插入后仍然是一颗二叉搜索树),递归算法

  • 二叉搜索树的删除(分为删除节点为叶子节点、左子树为空、右子树为空、左右子树均不为空等四个方面,递归算法,删除后仍然是一颗二叉搜索树)

  • 二叉搜索树的搜索,O(lgn),递归算法

  • 二叉搜索树的遍历,特别是中序遍历(遍历结果为升序序列),递归算法

  • 二叉搜索树的打印(树的前序遍历的应用),递归算法

详细内容请参考专栏文章: Java二叉搜索树

八大排序算法及其实现

具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序,归并排序,基数排序在内的八种排序算法,同时对各种算法的基本特征做出了详细分析:

  • 算法基本思想

  • 算法的种类:插入排序(直接插入排序,希尔排序,折半插入排序),选择排序(直接选择排序,堆排序(升序/最大堆)),交换排序(冒泡排序,快速排序),归并排序,分配排序(基数排序)

  • 算法的时间复杂度

  • 算法的空间复杂度

  • 算法的稳定性

  • 内部排序/外部排序

详细内容请参考专栏文章: Java排序算法