Skip to main content

基础线性结构

· 5 min read
Zeffon Wu

线性结构是一个有序数据元素的集合。线性结构--数组、栈、队列、链表介绍

前言​

线性结构是一个有序数据元素的集合。线性结构--数组、栈、队列、链表介绍

正文​

Array 数组​

Array 是一种线性结构，把数据码成一排进行存放，只能存放同一种类型多个元素。

  1. Java Array 属于静态数组
  2. Array 最大的优点：快速查询。例如：arr[1]
  3. Array 最好应用与索引有语意的场景。
  4. 但并非所有有语意的索引都适应于 Array。有些索引如（身份证号）长度太长了导致空间被浪费。
  5. 相关操作添加操作删除操作修改操作查找操作
    复杂度O(n)O(n)已知索引 O(1);未知索引 O(n)已知索引 O(1);未知索引 O(n)

Stack 栈​

Satck 是一种先进后出的线性结构。

  1. 相比数组，栈对应的操作是数组的子集，只能从一端添加元素，也只能从这一端取出元素。这一端称为栈顶。
  2. 栈只能在栈顶操作数据: 在表尾进行插入和删除操作。
  3. 栈的使用场景: 我们经常使用的Undo(撤销操作)、程序调用的系统栈、括号匹配。
  4. 相关操作入栈出栈查看栈顶查看元素数量判断是否为空
    复杂度O(1)均摊O(1)均摊O(1)O(1)O(1)

Queue 队列​

Queue 是一种先进先出的线性结构。

  1. 相比数组，队列对应的操作是数组的子集。只能从一端队尾添加元素，只能从另一端队首取出元素。

  2. 队列的分类: 数组队列、循环队列

  3. 循环队列必定是要浪费掉一个空间不能存储数据的

  4. 循环队列队列为空队列满 (c 表示队列的容量)
    条件front == tail(tail + 1) % c == front
  5. 相关操作入队出队查看队首查看元素数量判断是否为空
    复杂度O(1)均摊O(n)O(1)O(1)O(1)
  • 注意   数组队列出列的时间复杂度为O(n),而循环队列均摊下来的复杂度为O(1).

LinkedList 链表​

最简单、真正的动态数据结构，数据存储在节点Node中。

  1. 节点: 把数据存储在一种单独数据结构中，一部分是数据，一部分是下一个节点，最后一个节点是NULL。
  2. 链表在添加和删除中，对数据操作的顺序很重要。在中间添加时，先将该元素的前一个节点找出来。
  3. 优点: 真正的动态数据，不需要像 Array、Stack、Queue 处理固定容量的问题
  4. 缺点: 不适合用于索引有语意的情况，因为它丧失了随机访问数据的能力

Recursion 递归​

递归 : 本质上，将原来的问题，转化为更小的同一问题

  • 递归基本原则: 所有递归问题基本上都可以分为以下两部分
  1. 求解最基本问题（这个最基本问题是不能自动求解的，需要编写逻辑求解的）
  2. 把原问题转化成更小的问题（核心部分）
  • 举例 : 数组求和
Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])   <-  更小的同一问题(少了一个元素)
Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])   <-  更小的同一问题(少了一个元素)
                            . . . . . .
Sum(arr[n-1...n-1]) = arr[n-1] + Sum([])   <-  最基本的问题
  • 代码
    public static int sum(int[] arr){
        return sum(arr, 0);
    }

    // 计算arr[l...n)这个区间内所有数字的和
    private static int sum(int[] arr, int l){
        if(l == arr.length)
            return 0;                        <-  最基本的问题
        return arr[l] + sum(arr, l + 1);     <-  更小的同一问题
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8};
        System.out.println(sum(nums));
    }