常用的Java数据结构知识点汇总

目录
  • 1.数据结构分类
  • 2.线性数据结构
    • 2.1数组
    • 2.2可变数组
    • 2.3链表
    • 2.4栈
    • 2.5队列
  • 3.非线性数据结构
    • 3.1树
    • 3.2图
    • 3.3散列表
    • 3.4堆

1. 数据结构分类

按照线性和非线性可以将Java数据结构分为两大类:

①线性数据结构:数组、链表、栈、队列
②非线性数据结构:树、堆、散列表、图

2. 线性数据结构

2.1 数组

数组是一种将元素存储于连续内存空间的数据结构,并且要求元素的类型相同。

// 定义一个数组长度为5的数组array
int[] array = new int[5];
// 为数组的元素赋值
array[0] = 4;
array[1] = 3;
array[2] = 2;
array[3] = 1;
array[4] = 0;

直接赋值:

// 一种方式
int[] array = {4, 3, 2, 1, 0};
// 另一种方式
int[] array = new int[]{4, 3, 2, 1, 0};

2.2 可变数组

可变数组是在一般数组的基础上结合扩容机制进行改进的具有灵活长度的数组。

// 定义一个可变数组
List<Integer> changeable_array = new ArrayList<>();
// 向可变数组的尾部添加元素
array.add(4);
array.add(3);
array.add(2);
array.add(1);
array.add(0);

2.3 链表

链表可以定义为一个类,该类的包含两个成员变量的:节点的值val、后继节点的引用next。节点是构成链表的基本单位,这种数据结构在内存空间的存储地址是非连续的。

// 定义链表类
class ListNode {
    // 节点的值
    int val;
    // 后继节点的引用
    ListNode next;
    ListNode(int x){
        this. val = x;
    }
}

构建多个链表类的对象,并构建这些节点实例之间的引用指向:

  • ①节点head的节点值为2,其后继节点是值为1的节点n2。
  • ②节点n2的节点值为1,其后继节点是值为0的节点n3。
  • ③该链表的头节点为head,尾节点为n3。
// 实例化节点
ListNode head = new ListNode(2);
ListNode n2 = new ListNode(1);
ListNode n3 = new ListNode(0);
// 构建三个节点之间的引用指向
head.next = n2;
n2.next = n3;

2.4 栈

栈是一种抽象数据结构,特点是“后进先出”,可由数组或者链表实现。

// 定义一个栈,使用Java的Vector类的子类Stack
Stack<Integer> stack = new Stack<>();

入栈操作 push():

// 元素0入栈
stack.push(0);
// 元素1入栈
stack.push(1);

出栈操作 pop():

// 元素1出栈
stack.pop();
// 元素0出栈
stack.pop();

在Java中可以使用Stack、ArrayDeque、LinkedList实现栈,但通常情况下,不推荐使用Vector类以及其子类Stack,

一般使用LinkedList来实现栈:

LinkedList<Integer> stack = new LinkedList<>();

入栈操作 addLast():

// 元素0入栈
stack.addLast(0);
// 元素1入栈
stack.addLast(1);

出栈操作 removeLast():

// 元素1出栈
stack.removeLast();
// 元素0入栈
stack.removeLast();

2.5 队列

队列是一种抽象数据结构,特点是“先进先出”,可由链表实现。
LinkedList类实现了Queue接口,因此可以把LinkedList当成Queue来用。

Queue<Integer> queue = new LinkedList<>();

入队操作 offer():

// 元素0入队
queue.offer(0);
// 元素1入队
queue.offer(1);

出队操作poll(),该函数的返回值为出队的那个元素:

// 元素0出队
queue.poll();
// 元素1出队
queue.poll();

element():返回第一个元素
peek():返回第一个元素
区别:在队列元素为空的情况下,element() 方法会抛出NoSuchElementException异常,peek() 方法只会返回 null。

queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
queue.offer("e");
queue.element(); //输出a
queue.peek(); //输出a

3. 非线性数据结构

3.1 树

树是一种非线性的数据结构,可分为二叉树和多叉树。
二叉树可定义为一个类,该类包含三个成员变量:节点值val、左子节点left、右子节点right

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        this.val = x;
    }
}

二叉树各节点实例化:

// 根节点root
TreeNode root = new TreeNode(0);
TreeNode n2 = new TreeNode(1);
TreeNode n3 = new TreeNode(2);
TreeNode n4 = new TreeNode(3);
TreeNode n5 = new TreeNode(4);

构建二叉树各节点之间的引用指向:

// 根节点的左子节点为n2,其值为1
root.left = n2;
// 根节点的右子节点为n3,其值为2
root.right = n3;
// 节点n2的左子节点为n4,其值为3
n2.left = n4;
// 节点n2的右子节点为n5,其值为4
n2.right = n5;

3.2 图

图是一种非线性数据结构,由顶点(vertex)和边(edge)组成,每条边都连接着两个顶点。
图分为有向图和无向图。

以无向图为例:

  • ①顶点集合: vertices = {1, 2, 3, 4, 5}
  • ②边集合: edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

(1)图的表示方法:邻接矩阵(无向图的邻接矩阵是一个斜对角对称矩阵)
邻接矩阵适用于存储稠密图,即顶点较多、边较少。

// 存储图的顶点
int[] vertices = {1, 2, 3, 4, 5};
// 存储图的边
int[][] edges = {{0, 1, 1, 1, 1},
                 {1, 0, 0, 1, 0},
                 {1, 0, 0, 0, 1},
                 {1, 1, 0, 0, 1},
                 {1, 0, 1, 1, 0}};
int[] vertices = {1, 2, 3, 4, 5};

(2)图的表示方法:邻接表

邻接表适用于存储稀疏图,即顶点多、边较少。

// 存储图的顶点
int[] vertices = {1, 2, 3, 4, 5};
// 存储边的集合
List<List<Integer>> edges = new ArrayList<>();
// edge[i]表示图的顶点i对应的边集合
List<Integer> edge_1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
List<Integer> edge_2 = new ArrayList<>(Arrays.asList(0, 3));
List<Integer> edge_3 = new ArrayList<>(Arrays.asList(0, 4));
List<Integer> edge_4 = new ArrayList<>(Arrays.asList(0, 1, 4));
List<Integer> edge_5 = new ArrayList<>(Arrays.asList(0, 2, 3));
edges.add(edge_1);
edges.add(edge_2);
edges.add(edge_3);
edges.add(edge_4);
edges.add(edge_5);

3.3 散列表

散列表是一种非线性的数据结构,实质是将键(key)通过Hash函数完成到值(value)的映射。

// 初始化散列表
Map<String, Integer> dict = new HashMap<>();

添加键 - 值对:

dict.put("python", 101);
dict.put("c", 102);
dict.put("java", 103);

通过键 key查找对应的值 value:

dict.get("python");    // 101
dict.get("c");        // 102
dict.get("java");    // 103

设计一个简单的Hash函数构建 编程语言 ==> 编号 的映射,构建一个散列表(假设不考虑低碰撞率、高鲁棒性):

String[] program_lang = {"python", "c", "java"};

int hash(int idx){
    int index = (idx -1 % 100);
    return index;
}

names[hash(101)];    // python
names[hash(101)];    // c
names[hash(101)];    // java

3.4 堆

  • (1)堆是一种基于完全二叉树的数据结构,可由数组实现。
  • 完全二叉树:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1 ≤ i ≤ n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
  • (2)基于堆的原理实现的排序算法称为堆排序。
  • (3)基于堆实现的数据结构称为优先队列。
  • (4)堆分为大顶堆、小顶堆:①大顶堆:任意节点的值不大于其父节点的值,即根节点最大,任意子节点小于等于父节点。②小顶堆:任意节点的值不小于其父节点的值,即根节点最小,任意子节点大于等于父节点。
// 初始化小顶堆,操作为 优先队列
Queue<Integer> heap = new PriorityQueue<>();

元素入堆add():

// 元素入堆
heap.add(0);
heap.add(4);
heap.add(2);
heap.add(6);
heap.add(8);

元素出堆 poll():

// 元素出堆(从小到大)
heap.poll(); // -> 0
heap.poll(); // -> 2
heap.poll(); // -> 4
heap.poll(); // -> 6
heap.poll(); // -> 8

到此这篇关于常用的Java数据结构知识点汇总的文章就介绍到这了,更多相关常用的Java数据结构分享内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java 数据结构与算法系列精讲之队列

    目录 概述 队列 队列实现 enqueue方法 dequeue方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 队列 队列 (Queue) 遵循先进先出的原则 (First-In-First-Out). 举个例子, 早上我们排队买早餐的时候, 先排的人先买后排的人后买. 队列只能在队首进行删除操作, 在队尾进行插入操作. 队列实现 enqueue 方法 // 入队 public void enqueue(E element) { array

  • Java 数据结构与算法系列精讲之数组

    目录 概述 数组 声明数组的两个方法 创建数组的两个方法 索引 自定义数组 泛型 构造函数 元素操作 调用 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 数组 数组 (Array) 是有序数据的集合, 在 Java 中 java.util.Arrays包含用来操作数组的各种方法, 比如排序和搜索等. 其所有方法均为静态方法, 调用起来非常简单. 声明数组的两个方法 方法一: 数据类型[] array; 方法二: 数据类型 array[]; 创建数组的两

  • Java 数据结构与算法系列精讲之环形链表

    目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li

  • Java数据结构之优先级队列(堆)图文详解

    目录 一.堆的概念 二.向下调整 1.建初堆 2.建堆 三.优先级队列 1.什么是优先队列? 2.入队列 3.出队列 4.返回队首元素 5.堆的其他TopK问题 总结: 总结 一.堆的概念 堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时: (1)ki >= k2i 且 ki >= k(2i+1) ——大根堆 (2) ki <= k2i 且 ki <= k(2i+1) ——小根堆 简单来说: 堆是具有以下性质的完全二叉树:(1)每个结点的

  • Java 数据结构与算法系列精讲之单向链表

    目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表

  • Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

    目录 概述 算法的衡量标准 时间复杂度 最优时间复杂度 平均时间复杂度 最坏时间复杂度 O(1) O(n) O(n^2) O(logN) 空间复杂度 O(1) O(n) 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 算法的衡量标准 当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量. 时间复杂度 时间复杂度 (Time Complexity) 通常用 O(n)

  • Java 数据结构与算法系列精讲之栈

    目录 概述 栈 栈实现 push方法 pop方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈 栈 (Stack) 是一种运算受限的线性表, 遵循先进后出的原则 (Last-In-First-Out). 举个例子, 当我们灌调料的时候, 后灌进去的调料会先被使用. 栈只能在表尾部进行插入和删除的操作. 开口的一端被称为栈顶, 另一端则被称为栈底. 如图: 栈实现 push 方法 栈 (Stack) 的 push 方法, 把项压入栈顶部.

  • 常用的Java数据结构知识点汇总

    目录 1.数据结构分类 2.线性数据结构 2.1数组 2.2可变数组 2.3链表 2.4栈 2.5队列 3.非线性数据结构 3.1树 3.2图 3.3散列表 3.4堆 1. 数据结构分类 按照线性和非线性可以将Java数据结构分为两大类: ①线性数据结构:数组.链表.栈.队列②非线性数据结构:树.堆.散列表.图 2. 线性数据结构 2.1 数组 数组是一种将元素存储于连续内存空间的数据结构,并且要求元素的类型相同. // 定义一个数组长度为5的数组array int[] array = new

  • Java中Map接口使用以及有关集合的面试知识点汇总

    目录 Map接口 存储特点 常用实现类 创建方法 常用方法 遍历方法 不同实现类的使用 集合面试知识点补充 结语 Map接口 存储特点 以键(key)值(value)对的形式存储 键无序.无下标.元素不可重复 值无序.无下标.元素可以重复 常用实现类 HashMapJDK1.2 底层哈希表实现 线程不安全,效率高 LinkedHashMapJDK1.2 是HashMap的子类,底层哈希表实现 线程不安全,效率高 TreeMapJDK1.2 是SortedMap的实现类,底层红黑树实现 线程不安全

  • 关于ES6新特性最常用的知识点汇总

    目录 1.关键字 2.解构 3.字符串 4.正则 5.数组 6.函数 7.对象 8.Symbol 9.集合 10.Proxy配合Reflect的观察者模式 11. Promise 12.遍历器 13.Generator 14.async 15.Class 16.修饰器 17.Moudle 总结 1.关键字 Let 关键字 在let所在的代码块中起作用.在let之前对于改该变量是不能进行赋值的 Const关键字  为只读变量,因此在定义的时候就需要去赋值. 2.解构 变量的解构, 1>.数组结构利

  • Java数据结构之单链表的实现与面试题汇总

    目录 1 单链表 1.1 单链表介绍 1.2 单链表的实现思路分析 1.3 实现代码 2 单链表的面试题 2.1 统计单链表中有效节点数量 2.2 新浪–倒数第k个节点 2.3 腾讯–单链表的反转 2.4 百度–逆序打印单链表 1 单链表 1.1 单链表介绍 由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表.单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻.

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • Pandas-DataFrame知识点汇总

    目录 1.DataFrame的创建 根据字典创建 读取文件 2.DataFrame轴的概念 3.DataFrame一些性质 索引.切片 修改数据 重新索引 丢弃指定轴上的值 算术运算 函数应用和映射 排序和排名 汇总和计算描述统计 处理缺失数据 1.DataFrame的创建 DataFrame是一种表格型数据结构,它含有一组有序的列,每列可以是不同的值.DataFrame既有行索引,也有列索引,它可以看作是由Series组成的字典,不过这些Series公用一个索引.DataFrame的创建有多种

  • Java数据结构之有效队列定义与用法示例

    本文实例讲述了Java数据结构之有效队列定义与用法.分享给大家供大家参考,具体如下: /** * @描述 有序对列 * 从任何位置插入数据都是有序的 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin */ public class SequeQueue { private long[] arr; private int maxSize;// 最大空间 private int len;// 有效长度

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • java数据结构与算法之快速排序详解

    本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

随机推荐