基础数据结构（0）

date
May 8, 2023
slug
计算机基础
status
Published
tags
数据结构
summary
初学数据结构
type
Post

Array 数组

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。
 
优点：
1、按照索引查询元素速度快
2、按照索引遍历数组方便
缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。
适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况
 

String 字符串

严格说不是数据结构，是一种non-primitive data type(非原始数据类型)
primitive type指的是boolean, int, char, double, long, byte, short, float
 
String is a sequence of characters. But in Java, a string is an object that represents a sequence of characters. The java.lang.String class is used to create a string object.
字符串是一系列字符。但在Java中，字符串是表示字符序列的对象。java.lang.String类用于创建字符串对象。
 
常用method
  1. str.substring();用于从字符串中提取一个子字符串。它可以接受一个参数（起始索引）或两个参数（起始索引和结束索引）。
  1. str.charAt(index);用于获取字符串中指定索引位置的字符。索引从0开始。
  1. str1.compareTo(str2);用于比较两个字符串的字典顺序。如果两个字符串相等，则返回值为0；如果 str1 在字典顺序上小于 str2，则返回值为负数；如果 str1 在字典顺序上大于 str2，则返回值为正数。compareTo() 方法是区分大小写的，如果需要不区分大小写的比较，可以使用 compareToIgnoreCase() 方法。
 

Linked List 链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
 
常用method
赋值取值时间复杂度均为O(1)
初始化ListNode head = new ListNode(0);
赋值  head.next = new ListNode(1);
取值  head.val
在这里，我们在 Java 中使用链表节点 ListNode 的示例。首先，我们需要定义一个 ListNode 类，如下所示：
以下是所提到的方法的解释和示例：
初始化 ListNode head = new ListNode(0);
这行代码创建一个新的链表节点，并将其值设置为0。时间复杂度为 O(1)。
赋值 head.next = new ListNode(1);
这行代码创建一个新的链表节点，其值为1，并将其设置为当前 head 节点的下一个节点。时间复杂度为 O(1)。
取值 head.val
这行代码获取链表节点 head 的值。时间复杂度为 O(1)。
对于链表中的任何节点，赋值和取值操作的时间复杂度都是 O(1)，因为它们是基本的内存访问操作。
 
链表的优点：
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快
缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。
 
适用场景：
数据量较小，需要频繁增加，删除操作的场景
 

Tree 树

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
 
Binary Tree二叉树是树的特殊一种，具有如下特点：
1、每个结点最多有两颗子树
2、左子树和右子树是有顺序的
 
notion image
在这里，我们在 Java 中使用二叉树节点 TreeNode 的示例。首先，我们需要定义一个 TreeNode 类，如下所示：
以下是所提到的方法的解释和示例：
  1. 初始化 TreeNode root = new TreeNode(0);
这行代码创建一个新的二叉树节点，并将其值设置为0。这个节点会成为树的根节点。
  1. 为根节点添加左子节点 root.left = new TreeNode(1);
这行代码创建一个新的二叉树节点，其值为1，并将其设置为当前根节点的左子节点。
  1. 为根节点添加右子节点 root.right = new TreeNode(2);
这行代码创建一个新的二叉树节点，其值为2，并将其设置为当前根节点的右子节点。
这样，我们就创建了一个具有根节点和两个子节点（左子节点值为1，右子节点值为2）的简单二叉树。在实际应用中，二叉树通常具有更复杂的结构，需要使用递归或迭代方法进行遍历、查找、插入和删除操作。
 

Trie 前缀树或字典树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。
 
字典树的性质
  1. 根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符；
  1. 从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串；
  1. 任意节点的所有子节点所包含的字符都不相同；
 

Stack 栈

仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
 
 

Queue 队列

Queue First In First Out (FIFO)
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); //推荐
queue.offer(2);
queue.poll();    //return 1
queue.poll();    //return 2
时间复杂度均为O(1)
注意区分这里的LinkedList class, 和之前的数据结构Linked List（中间有空格）
常用来实现BFS 宽度优先搜索的遍历
notion image

Deque  双端队列

ava集合提供了接口Deque来实现一个双端队列，它的功能是
既可以添加到队尾，也可以添加到队首；
既可以从队首获取，又可以从队尾获取。

PriorityQueue(Heap) 堆(最大堆，最小堆)

堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。
在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。 Java PriorityQueue默认最小堆
考察点一般为pq应用和array手动实现heap
 

© LI Donghao 2023 - 2026