Java——》线性数据结构
推荐链接：
总结——》【Java】
总结——》【Mysql】
总结——》【Redis】
总结——》【Kafka】
总结——》【Spring】
总结——》【SpringBoot】
总结——》【MyBatis、MyBatis-Plus】
总结——》【Linux】
总结——》【MongoDB】
总结——》【Elasticsearch】
Java——》线性数据结构
线性表就是数据排成像一条线的结构。
每个线性表上的数据最多只有前和后两个方向。
线性表结构：数组、链表、队列、栈
一、数组Array
数组是一种线性表数据结构。用一组连续的内存空间，来存储一组具有固定大小的相同类型的数据。在数组中，数据元素按照有序的方式进行排列，可以通过索引访问数组中的任意位置的元素。
1、特点
顺序存储：按照顺序存储在连续的内存空间中类型相同：数组中的所有元素必须是相同的数据类型索引访问：每个元素都有一个唯一的索引，可以通过索引快速访问大小固定：一旦定义了数组的大小，就不能改变。如果需要更大的存储空间，需要重新定义一个新的数组。
2、优点
访问速度快：由于数组是顺序存储的，可以通过索引直接访问数组中的元素，时间复杂度为O(1)。易于实现：数组是一种简单的数据结构，容易实现和操作。
3、缺点
大小固定：数组的大小是固定的，不能动态扩展。如果需要更多的存储空间，需要重新定义一个新的数组，这会增加额外的开销。空间利用率低：由于数组是连续的内存空间，即使某些位置没有被使用，也不能被其他数据结构使用，导致空间利用率较低。
4、示例
// 动态初始化：初始化时由程序员只指定数组长度，由系统为数组元素分配初始值
char c1[] = new char[5];
// 静态初始化： 初始化时由程序员显示置顶每个数组的初始值，由系统决定数组长度
char c2[] = new char[]{'E','D','U','Y','U'};
char c3[] = {'E','D','U','Y','U'};
二、链表
数组是一种线性表数据结构。
通过指针将一组零散的内存块串联在一起。链表中的每个内存块被称为节点，每个节点除了存储数据之外，还需要记录链上的下一个节点的地址。
1、特点
- 不需要连续的内存空间
- 有指针引用
- 插入、删除数据效率高，时间复杂度为O(1)级别（只需更改指针指向即可）；但是，随机访问效率低，时间复杂度O(n)级别（需要从链头至链尾进行遍历）。
- 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。
2、分类
分类 | 特点 |
|---|---|
单向链表 | 节点只有一个后继指针next指向后面的节点 |
双向链表 | 节点除了有一个后继指针next指向后面的节点外，还有一个前驱指针prev指向前面的节点 |
循环链表 | 循环链表与单向链表的唯一区别是尾节点的指针指向头节点，形成一个环 |
2.1 单向链表
单向链表由节点组成，每个节点都包含下一个节点的指针，表头为空，表头的后继节点是"结点10"(数据为10的结点)，“节点10"的后继结点是"节点20”(数据为20的结点)
（1）删除节点
（2）添加节点
2.2 双向链表
双链表由节点组成，每个结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
static final class Node {
// 前一个节点
volatile Node prev;
// 后一个节点
volatile Node next;
// 链表节点存储的具体数据
volatile Thread thread;
}
（1）删除节点
（2）添加节点
2.3 循环链表
三、队列queue
队列是一种线性表数据结构。先进先出FIFO，后进后出。
只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
允许插入的一端称为队尾，允许删除的一端称为队头。
1、特点
先进先出：队列中的元素遵循先进先出的原则，即最早进入队列的元素最先被删除。插入和删除操作发生在同端：队列中的插入操作发生在队尾，删除操作发生在队头。无界队列：队列的长度可以是任意的整数，只要内存空间足够。
2、数据结构演示
参考链接：数据结构演示地址
3、示例
package com.xiaoxian.demo;
import java.util.LinkedList;
import java.util.Queue;
public class QueueTest {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(3);//尾插
queue.offer(6);
queue.offer(9);
queue.offer(12);
System.out.println(queue);
System.out.println(queue.peek());//访问队列头元素
System.out.println(queue);
System.out.println(queue.poll());//删除队列头元素
System.out.println(queue);
}
}
四、栈stack
栈是一种线性表数据结构。
只能在表尾进行插入或者删除，后进先出。
表尾端称为栈顶（top），表头端称为栈底（bottom）。
不含元素的空表称为空栈。
1、特点
- 后进先出
- 只能在
表尾进行插入或者删除
2、主要操作
- 入栈（push）：在栈顶添加一个元素。
- 出栈（pop）：删除栈顶的元素并返回其值。
- 判断栈空（is_empty）：检查栈是否为空。
- 获取栈顶元素（top）：返回栈顶的元素值，但不删除它。