Java——》线性数据结构

推荐链接:
    总结——》【Java】
    总结——》【Mysql】
    总结——》【Redis】
    总结——》【Kafka】
    总结——》【Spring】
    总结——》【SpringBoot】
    总结——》【MyBatis、MyBatis-Plus】
    总结——》【Linux】
    总结——》【MongoDB】
    总结——》【Elasticsearch】

线性表就是数据排成像一条线的结构。
每个线性表上的数据最多只有前和后两个方向。
线性表结构:数组、链表、队列、栈

一、数组Array

数组是一种线性表数据结构。用一组连续的内存空间,来存储一组具有固定大小的相同类型的数据。在数组中,数据元素按照有序的方式进行排列,可以通过索引访问数组中的任意位置的元素。

1、特点

  1. 顺序存储:按照顺序存储在连续的内存空间中
  2. 类型相同:数组中的所有元素必须是相同的数据类型
  3. 索引访问:每个元素都有一个唯一的索引,可以通过索引快速访问
  4. 大小固定:一旦定义了数组的大小,就不能改变。如果需要更大的存储空间,需要重新定义一个新的数组。

2、优点

  1. 访问速度快:由于数组是顺序存储的,可以通过索引直接访问数组中的元素,时间复杂度为O(1)。
  2. 易于实现:数组是一种简单的数据结构,容易实现和操作。

3、缺点

  1. 大小固定:数组的大小是固定的,不能动态扩展。如果需要更多的存储空间,需要重新定义一个新的数组,这会增加额外的开销。
  2. 空间利用率低:由于数组是连续的内存空间,即使某些位置没有被使用,也不能被其他数据结构使用,导致空间利用率较低。

4、示例

// 动态初始化:初始化时由程序员只指定数组长度,由系统为数组元素分配初始值
char c1[] = new char[5];

// 静态初始化: 初始化时由程序员显示置顶每个数组的初始值,由系统决定数组长度
char c2[] = new char[]{'E','D','U','Y','U'};
char c3[] = {'E','D','U','Y','U'};

二、链表

数组是一种线性表数据结构。
通过指针将一组零散的内存块串联在一起。链表中的每个内存块被称为节点,每个节点除了存储数据之外,还需要记录链上的下一个节点的地址。

1、特点

  1. 不需要连续的内存空间
  2. 有指针引用
  3. 插入、删除数据效率高,时间复杂度为O(1)级别(只需更改指针指向即可);但是,随机访问效率低,时间复杂度O(n)级别(需要从链头至链尾进行遍历)。
  4. 和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

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、特点

  1. 先进先出:队列中的元素遵循先进先出的原则,即最早进入队列的元素最先被删除。
  2. 插入和删除操作发生在同端:队列中的插入操作发生在队尾,删除操作发生在队头。
  3. 无界队列:队列的长度可以是任意的整数,只要内存空间足够。

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);
    }
}

image.png

四、栈stack

是一种线性表数据结构。
只能在表尾进行插入或者删除后进先出
表尾端称为栈顶(top),表头端称为栈底(bottom)。
不含元素的空表称为空栈。

1、特点

  1. 后进先出
  2. 只能在表尾进行插入或者删除

2、主要操作

  1. 入栈(push):在栈顶添加一个元素。
  2. 出栈(pop):删除栈顶的元素并返回其值。
  3. 判断栈空(is_empty):检查栈是否为空。
  4. 获取栈顶元素(top):返回栈顶的元素值,但不删除它。