常见八大数据结构

数据结构指的是组织和存储数据的方式，它可以帮助我们有效地管理和操作数据。常见的数据结构有以下八种

数据结构简介
数组（Array）线性数据结构，将相同类型的元素按照一定顺序排列。
链表（Linked List）线性数据结构，由一系列节点组成，每个节点都包含一个数据元素和一个指向下一个节点的指针。
栈（Stock）特殊的线性数据结构，遵循先进后出（LIFO）原则，仅一端能够进出，先进的元素进入栈底，取元素的时先从栈顶获取。
队列（Queue）线性数据结构，遵循先进先出（FIFO）的原则。一端只能进，一端只能出，只能在队尾插入元素，在队头删除元素。
树（Tree）非线性数据结构，由一系列节点以层次关系组成，每个节点可以有多个子节点。
图（Graph）非线性数据结构，由一组节点和节点之间的边组成。
哈希表（Hash Table）也叫散列表， 是一种使用哈希函数将键映射到存储桶的数据结构。
堆（Heap）特殊的树结构，可以被看成一个树的数组对象，分为最大堆和最小堆。

算法复杂度

算法复杂度是什么？

算法复杂度（Algorithm Complexity）是衡量算法执行效率的一种度量标准。指解决问题时，算法所需要的计算资源（如时间和空间）随着问题规模的增加而变化的趋势。通常算法复杂度可以分为时间复杂度和空间复杂度两个方面。

  • 时间复杂度（Time Complexity）：用于衡量算法运行所需的时间资源。它表示了算法执行时间随着输入规模增大而增加的趋势，通常用大O符号表示。时间复杂度通常通过统计算法执行基本操作（例如循环、条件判断、递归等）的次数来分析。常用的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)、O(n^2)等。
  • 空间复杂度（Space Complexity）：用于衡量算法在执行过程中所需的额外空间资源。它表示了算法执行期间所占用的内存空间大小与输入规模的关系，也用大O符号表示。空间复杂度通常通过统计算法执行中使用的数据结构、临时变量、递归调用等占用的内存空间来分析。常用的空间复杂度有O(1)、O(n)、O(n^2)等。

时间复杂度

时间复杂度简介

时间复杂度用于评估算法执行所需的时间资源，通常用大O符号表示，时间复杂度有O(1)、O(log n)、O(n)、O(n * log n)、O(n^2)、O(n^3)、O(n^k)、O(2^n)、O(n !)、O(n^n)等。常见的空间复杂度有O(1)、O(log n)、O(n)、O(n * log n)、O(n^2)，其他的在实际应用中较少见。

时间复杂度描述举例
O(1)常数时间复杂度，无论输入规模大小，算法的执行时间都是恒定的。最优的时间复杂度。访问数组中的某个元素
O(log n)对数时间复杂度，算法的执行时间与输入规模n成对数关系。二分查找算法
O(n)线性时间复杂度，算法的执行时间与输入规模n成线性关系。遍历数组、线性搜索
O(n * log n)线性对数时间复杂度，算法的执行时间与n乘以log n成比例关系。快速排序算法
O(n^2)平方时间复杂度，算法的执行时间与输入规模n的平方成比例关系。冒泡排序算法、选择排序算法
O(n^3)立方时间复杂度，算法的执行时间与输入规模n的立方成比例关系。三重嵌套循环
O(n^k)多项式时间复杂度，算法的执行时间与输入规模n的k次方成比例关系。多重嵌套循环（其中 k 为常数）
O(2^n)指数时间复杂度，算法的执行时间随着输入规模n呈指数级增长。效率较低。递归求解组合问题
O(n!)阶乘时间复杂度，算法的执行时间与输入规模n的阶乘成比例关系。效率非常低。全排列算法

时间复杂度效率对比

一般来说，时间复杂度越小，算法的性能越高，执行时间越短。而时间复杂度越大，算法的性能越低，执行时间越长。比较如下：

O(1) < O(log n) < O(n) < O(n * log n) < O(n^2) < O(n^3) < O(n^k) < O(2^n) < O(n!)

时间复杂度与数据规模趋势图

假如使用X轴表示数据规模，使用Y轴表示算法执行时间，随着X轴数据规模的增加，不同的时间复杂度会呈现出不同的走势。

  • **O(1)**：常数时间复杂度，算法的执行时间保持不变，即Y轴上的值不随X的增加而改变，形成水平线。
  • **O(log n)**：对数时间复杂度，算法的执行时间以对数方式增长，但增长速度较慢，形成逐渐上升的曲线。
  • **O(n)**：线性时间复杂度，算法的执行时间与数据规模成线性关系，即沿着X轴以相等的速度增长，形成斜线。
  • **O(n * log n)**：线性对数时间复杂度，算法的执行时间以较快的速度增长，形成斜率较大的曲线。
  • **O(n^2)**：平方时间复杂度，算法的执行时间与数据规模的平方成正比，即沿着Y轴迅速上升，形成急速上升的曲线。
  • **O(n^3)**：立方时间复杂度，算法的执行时间与数据规模的立方成正比，形成更陡的曲线。
  • **O(n^k)**：多项式时间复杂度，算法的执行时间与数据规模的指数幂成正比，曲线的斜率和增长速度随k值（k为常数）增加而变大。
  • **O(2^n)**：指数时间复杂度，算法的执行时间以指数方式增长，形成非常陡峭的曲线。
  • **O(n!)**：阶乘时间复杂度，算法的执行时间与数据规模的阶乘成正比，曲线呈现非常陡峭的上升趋势。

下面是使用ECharts绘制时间复杂度与数据规模趋势图的示例代码，可以复制到HTML运行查看效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>时间复杂度与数据规模趋势图</title>
    <script src="https://cdn.jsdelivr.net/npm/echarts@5.3.0/dist/echarts.min.js"></script>
</head>

<body>
    <div id="chart" style="width: 100%; height: 800px;"></div>
    <script>
        var chart = echarts.init(document.getElementById('chart'));

        // 定义时间复杂度和对应描述
        var complexityData = [
            { complexity: "O(1)", description: "常数时间复杂度" },
            { complexity: "O(log n)", description: "对数时间复杂度" },
            { complexity: "O(n)", description: "线性时间复杂度" },
            { complexity: "O(n * log n)", description: "线性对数时间复杂度" },
            { complexity: "O(n^2)", description: "平方时间复杂度" },
            { complexity: "O(n^3)", description: "立方时间复杂度" },
            { complexity: "O(n^k)", description: "多项式时间复杂度" },
            { complexity: "O(2^n)", description: "指数时间复杂度" },
            { complexity: "O(n!)", description: "阶乘时间复杂度" }
        ];

        // 定义数据规模n的范围
        var dataSize = [];
        for (var i = 1; i <= 10; i++) {
            dataSize.push(i);
        }

        // 生成时间复杂度与数据规模的对应关系
        var seriesData = [];
        for (var i = 0; i < complexityData.length; i++) {
            var complexity = complexityData[i].complexity;
            var description = complexityData[i].description;
            var timeData = [];

            // 根据不同的时间复杂度生成对应的执行时间数据
            switch (complexity) {
                case "O(1)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(1);
                    }
                    break;
                case "O(log n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(Math.log(dataSize[j]));
                    }
                    break;
                case "O(n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(dataSize[j]);
                    }
                    break;
                case "O(n * log n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(dataSize[j] * Math.log(dataSize[j]));
                    }
                    break;
                case "O(n^2)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(Math.pow(dataSize[j], 2));
                    }
                    break;
                case "O(n^3)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(Math.pow(dataSize[j], 3));
                    }
                    break;
                case "O(n^k)":
                    var k = 3.1; // 设置多项式空间复杂度的指数 k，可以根据需要进行调整
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(Math.pow(dataSize[j], k));
                    }
                    break;
                case "O(2^n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(Math.pow(2, dataSize[j]));
                    }
                    break;
                case "O(n!)":
                    for (var j = 0; j < dataSize.length; j++) {
                        timeData.push(factorial(dataSize[j]));
                    }
                    break;
            }

            seriesData.push({
                name: complexity,
                type: 'line',
                data: timeData,
                tooltip: {  // 鼠标停留时显示信息
                    formatter: function (params) {
                        return complexity + '<br/>' + description + '<br/>' + '数据规模：' + params.name + '<br/>' + '执行时间：' + params.value;
                    }
                }
            });
        }

        // 绘制图表
        chart.setOption({
            toolbox: {
                feature: {
                    restore: {}, // 重置图表，还原图表
                    magicType: {
                        type: ['bar', 'line']  // 将图表在不同类型之间切换（需要数据的支持）
                    }
                }
            },

            title: {
                text: '时间复杂度与数据规模趋势图'
            },
            tooltip: {
                trigger: 'axis',
                axisPointer: {
                    type: 'cross'
                }
            },
            legend: {
                data: complexityData.map(function (item) {
                    return item.complexity;
                })
            },
            xAxis: {
                type: 'category',
                name: '数据规模n',
                data: dataSize
            },
            yAxis: {
                type: 'value',
                name: '执行时间'
            },
            series: seriesData
        });

        // 计算阶乘
        function factorial(n) {
            if (n <= 1) {
                return 1;
            }
            return n * factorial(n - 1);
        }
    </script>
</body>

</html>

空间复杂度

空间复杂度简介

空间复杂度用于评估算法所需的额外内存空间，通常用大O符号来表示，空间复杂度有O(1)、O(log n)、O(n)、O(n * log n)、O(n^2)、O(n^3)、O(n^k)、O(2^n)、O(n !)、O(n^n)。常见的空间复杂度只有O(1)、O(n)、O(n ^2)，其他的几乎用不到。

空间复杂度描述举例
O(1)常数空间复杂度，无论输入规模大小，算法的空间使用量都是恒定的。最优的空间复杂度。两个变量的存储空间
O(log n)对数空间复杂度，算法的空间使用量与输入规模n的对数成比例关系。二分查找算法
O(n)线性空间复杂度，算法的空间使用量与输入规模n成线性关系。数组、链表
O(n * log n)线性对数空间复杂度，算法的空间使用量与n乘以log n成比例关系。快速排序算法的递归调用栈空间
O(n^2)平方空间复杂度，算法的空间使用量与输入规模n的平方成比例关系。二维数组、矩阵
O(n^3)立方空间复杂度，算法的空间使用量与输入规模n的立方成比例关系。三维数组、立方体
O(n^k)多项式空间复杂度，算法的空间使用量与输入规模n的k次方成比例关系。k维数组、多重嵌套循环的变量
O(2^n)指数空间复杂度，算法的空间使用量随着输入规模n呈指数级增长。效率较低。递归调用的栈空间
O(n!)阶乘空间复杂度，算法的空间使用量与输入规模n的阶乘成比例关系。效率非常低。全排列算法的临时存储空间

空间复杂度效率对比

一般来说，空间复杂度越小，算法所需的额外空间越少，节省内存资源。空间复杂度越大，算法所需的额外空间越多。比较如下：

O(1) < O(log n) < O(n) < O(n * log n) < O(n^2) < O(n^3) < O(n^k) < O(2^n) < O(n!)

空间复杂度与数据规模趋势图

假如使用X轴表示数据规模，使用Y轴表示算法空间使用量，随着X轴数据规模的增加，不同的空间复杂度会呈现出不同的走势。

  • **O(1)**：常数空间复杂度，算法的空间使用量保持不变，即Y轴上的值不随X的增加而改变，形成水平线。
  • **O(log n)**：对数空间复杂度，算法的空间使用量以对数方式增长，但增长速度较慢，形成逐渐上升的曲线。
  • **O(n)**：线性空间复杂度，算法的空间使用量与数据规模成线性关系，即沿着X轴以相等的速度增长，形成斜线。
  • **O(n * log n)**：线性对数空间复杂度，算法的空间使用量以较快的速度增长，形成斜率较大的曲线。
  • **O(n^2)**：平方空间复杂度，算法的空间使用量与数据规模的平方成正比，即沿着Y轴迅速上升，形成急速上升的曲线。
  • **O(n^3)**：立方空间复杂度，算法的空间使用量与数据规模的立方成正比，形成更陡的曲线。
  • **O(n^k)**：多项式空间复杂度，算法的空间使用量与数据规模的指数幂成正比，曲线的斜率和增长速度随k值（k为常数）增加而变大。
  • **O(2^n)**：指数空间复杂度，算法的空间使用量以指数方式增长，形成非常陡峭的曲线。
  • **O(n!)**：阶乘空间复杂度，算法的空间使用量与数据规模的阶乘成正比，曲线呈现非常陡峭的上升趋势。

下面是使用ECharts绘制的空间复杂度与数据规模趋势图的示例代码，可以复制到HTML运行查看效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>空间复杂度与数据规模趋势图</title>
    <script src="https://cdn.jsdelivr.net/npm/echarts@5.3.0/dist/echarts.min.js"></script>
</head>

<body>
    <div id="chart" style="width: 100%; height: 800px;"></div>
    <script>
        var chart = echarts.init(document.getElementById('chart'));

        // 定义空间复杂度和对应描述
        var spaceComplexityData = [
            { complexity: "O(1)", description: "常数空间复杂度" },
            { complexity: "O(log n)", description: "对数空间复杂度" },
            { complexity: "O(n)", description: "线性空间复杂度" },
            { complexity: "O(n * log n)", description: "线性对数空间复杂度" },
            { complexity: "O(n^2)", description: "平方空间复杂度" },
            { complexity: "O(n^3)", description: "立方空间复杂度" },
            { complexity: "O(n^k)", description: "多项式空间复杂度" },
            { complexity: "O(2^n)", description: "指数空间复杂度" },
            { complexity: "O(n!)", description: "阶乘空间复杂度" }
        ];

        // 定义数据规模n的范围
        var dataSize = [];
        for (var i = 1; i <= 10; i++) {
            dataSize.push(i);
        }

        // 生成空间复杂度与数据规模的对应关系
        var seriesData = [];
        for (var i = 0; i < spaceComplexityData.length; i++) {
            var complexity = spaceComplexityData[i].complexity;
            var description = spaceComplexityData[i].description;
            var spaceData = [];

            // 根据不同的空间复杂度生成对应的空间使用量数据
            switch (complexity) {
                case "O(1)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(1);
                    }
                    break;
                case "O(log n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(Math.log(dataSize[j]));
                    }
                    break;
                case "O(n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(dataSize[j]);
                    }
                    break;
                case "O(n * log n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(dataSize[j] * Math.log(dataSize[j]));
                    }
                    break;
                case "O(n^2)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(Math.pow(dataSize[j], 2));
                    }
                    break;
                case "O(n^3)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(Math.pow(dataSize[j], 3));
                    }
                    break;
                case "O(n^k)":
                    var k = 3.1; // 设置多项式空间复杂度的指数 k，可以根据需要进行调整
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(Math.pow(dataSize[j], k));
                    }
                    break;
                case "O(2^n)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(Math.pow(2, dataSize[j]));
                    }
                    break;
                case "O(n!)":
                    for (var j = 0; j < dataSize.length; j++) {
                        spaceData.push(factorial(dataSize[j]));
                    }
                    break;
            }

            seriesData.push({
                name: complexity,
                type: 'line',
                data: spaceData,
                tooltip: {
                    formatter: function (params) {
                        return complexity + '<br/>' + description + '<br/>' + '数据规模：' + params.name + '<br/>' + '空间使用量：' + params.value;
                    }
                }
            });
        }

        // 阶乘函数
        function factorial(n) {
            if (n <= 1) {
                return 1;
            } else {
                return n * factorial(n - 1);
            }
        }

        // 绘制图表
        chart.setOption({
            toolbox: {
                feature: {
                    restore: {},
                    magicType: {
                        type: ['bar', 'line']
                    }
                }
            },

            title: {
                text: '空间复杂度与数据规模趋势图'
            },
            tooltip: {
                trigger: 'axis',
                axisPointer: {
                    type: 'cross'
                }
            },
            legend: {
                data: spaceComplexityData.map(function (item) {
                    return item.complexity;
                })
            },
            xAxis: {
                type: 'category',
                name: '数据规模n',
                data: dataSize
            },
            yAxis: {
                type: 'value',
                name: '空间使用量'
            },
            series: seriesData
        });
    </script>
</body>

</html>

常见数据结构操作的复杂度

可以参考：https://www.bigocheatsheet.com/

数据结构插入删除查找遍历
数组 (Array)O(n)O(n)O(n)O(n)
链表 (Linked List)O(1)O(1)O(n)O(n)
栈 (Stack)O(1)O(1)O(n)O(n)
队列 (Queue)O(1)O(1)O(n)O(n)
哈希表 (Hash Table)O(1)O(1)O(1)O(n)
二叉树 (Binary Tree)O(log n)O(log n)O(log n)O(n)
堆 (Heap)O(log n)O(log n)O(n)O(n)
图 (Graph)O(1)O(1)O(V+E)O(V+E)

常见数组排序算法的复杂度

可以参考：https://www.bigocheatsheet.com/

排序算法最优时间复杂度平均时间复杂度最坏时间复杂度
冒泡排序 (Bubble Sort)O(n)O(n^2)O(n^2)
选择排序 (Selection Sort)O(n^2)O(n^2)O(n^2)
插入排序 (Insertion Sort)O(n)O(n^2)O(n^2)
希尔排序 (Shell Sort)O(n log n)O(n log^2 n)O(n log^2 n)
归并排序 (Merge Sort)O(n log n)O(n log n)O(n log n)
快速排序 (Quick Sort)O(n log n)O(n log n)O(n^2)
堆排序 (Heap Sort)O(n log n)O(n log n)O(n log n)
计数排序 (Counting Sort)O(n + k)O(n + k)O(n + k)
桶排序 (Bucket Sort)O(n + k)O(n + k)O(n^2)
基数排序 (Radix Sort)O(n * k)O(n * k)O(n * k)

数组（Array）

数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组的特点

  1. 内存连续分配：数组是线性数据结构，数组中的元素在内存中是连续存储的，每个元素占用相同大小的内存空间。
  2. 索引访问：数组使用整数索引来访问元素，索引从0开始，每个元素都有一个唯一对应的索引值。通过索引，可以直接计算出元素在内存中的地址。
  3. 长度固定：数组在创建时需要指定长度，且长度固定不可变。这意味着数组的容量是固定的，无法动态扩展或缩小。
  4. 单一类型存储：数组通常只能存储同一种数据类型的元素。在创建数组时需要明确指定元素的数据类型，不能在同一个数组中存储不同类型的元素。
  5. 查询效率高：由于数组通过索引定位元素，因此随机访问非常高效，时间复杂度为O(1)。
  6. 插入和删除效率低：由于数组的长度固定，当需要在中间位置插入或删除元素时，需要将后续的元素进行移动，需要将后续的元素依次向后或向前移动，以腾出空间或填补空缺，这导致插入和删除操作的时间复杂度为O(n)。
  7. 内存空间浪费：由于数组的长度固定，如果实际存储的元素个数小于数组的长度，会导致内存空间的浪费，因为多余的空间没有被利用起来。
  8. 多维数组：除了一维数组，数组还可以是多维的，例如二维数组、三维数组等。多维数组在概念上是一个表格或矩阵，可以使用多个索引来访问和操作其中的元素。

数组的创建

在Java中，可以使用以下方式创建一个整数数组

1
int[] array = {22, 33, 88, 66, 55, 25}; // 定义一个整数数组，并初始化元素

创建的整数数组结构图如下

创建的整数数组在内存的表示如下

数组的访问

寻址公式

由于数组的元素是按照连续的方式存储的，所以数组的访问操作可以通过索引直接定位到对应的元素。当计算机要随机访问数组中的某个元素时，会通过寻址公式计算出对应元素的内存地址，从而通过内存地址访问数据。这个计算过程不会随着数组大小的增加而改变，所以无论数组有多大，访问任意位置的元素所需的时间都是相同的，因此数组的随机访问操作非常高效，时间复杂度为O(1)。寻址公式语法如下：

  • address：要访问的元素的内存地址，是一个指针或引用，指向了数组中特定元素的内存位置。

  • baseAddress ：数组的起始内存地址，即数组中第一个元素所在的内存地址。

  • index ：要访问的元素索引，表示想要访问数组中的哪个元素。

  • elementSize ：每个元素所占的内存空间大小，以字节为单位，不同的数据类型有不同的大小。

1
2
// 要访问的元素的内存地址 = 数组的起始内存地址 + 要访问的元素索引 * 元素大小
address = baseAddress + index * elementSize

已知索引访问元素的过程

（1）假设有下面的数组

1
int[] array = {22, 33, 88, 66, 55, 25}; // 定义一个整数数组，并初始化元素

（2）需要访问索引为1的元素，可以使用下面的语法

1
int arr = array[1];

（3）假设数组的起始内存地址为100，即索引为0的元素的内存地址为100。由于数组元素类型为整数（int），所以每个元素的大小是4个字节，根据寻址公式，可以计算出索引为1的元素的内存地址为104，通过内存地址104，可以获取到arr对应的元素值为33。代码的执行次数并不会随着数组的数据规模大小变化而变化，是常数级的，所以查询数据操作的时间复杂度是O(1)。

1
address = 100 + 1 * 4

未知索引访问元素的过程

数组无序：假如数组无序并且不知道索引，查找数组内的元素时需要遍历查找，例如查找55号数据，遍历数组时间复杂度为O(n)。

数组有序：假如数组有序并且不知道索引，查找数组内的元素时可以使用二分查找算法查找，例如查找55号数据时间复杂度为O(log n)。

为什么数组下标从0开始?

假设数组下标从n开始（n>0），那么计算机的寻址公式就会变成为如下

1
address = baseAddress + (index-n) * elementSize

从n开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU来说，就是多了一次减法指令，性能就会变低

数组的插入

插入操作对于数据的不同的场景和不同的插入位置，时间复杂度都略有不同，最好情况下是O(1)，最坏情况下是O(n)，平均情况下的时间复杂度是O(n)。

尾部插入元素

在数组的末尾插入元素，不需要搬移数据，直接将元素放入到数组的末尾即可，时间复杂度为O(1)

开头或中间插入元素（数组中的元素有序）

如果数组的数据是有序（从小到大或从大到小），在第k位置插入一个新的元素时，就必须把k之后的数据往后移动一位，此时最坏时间复杂度是O(n)。

开头或中间插入元素（数组中的元素无序）

如果数组的数据没有任何规律，那么在第k位置插入一个新的元素时，先将旧的第k位置的数据搬移到数据末尾，再把新的元素数据直接放入到第k位置。那么在这种特定场景下，在第k个位置插入一个元素的时间复杂度为O(1)。

数组的删除

尾部删除元素

如果删除数组末尾的数据，不需要搬移数据，直接将末尾元素删除即可，时间复杂度为O(1)；

开头或中间删除元素

如果删除开头的数据，因需把k位置之后的数据往前搬移一位，那么时间复杂度就为O(n)。

数组的分类

一维数组

数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

1
int[] array = {1, 2, 3};

二维数组（多维数组）

多维数组可以看成是数组的数组，比如二维数组就是一个特殊的一维数组，其每一个元素都是一个一维数组

1
int[][] array = {{1, 2, 3}, {4, 5, 6}};

链表（Linked List）

链表的特点

  1. 非连续存储：链表中的元素在内存中可以是不连续存储的，每个元素（节点）都包含一个指向下一个节点的指针（引用），通过这种方式将节点串联在一起。
  2. 动态长度：链表的长度可以根据需要动态增长或缩小，不需要事先指定长度，相比于数组，节省了内存空间。
  3. 多种类型存储：链表节点可以存储不同类型的元素，每个节点可以包含任意类型的数据。
  4. 查询效率低：由于链表中的节点不是连续存储的，要查找某个元素需要从头节点开始顺序遍历链表，才能访问特定位置的节点，无法像数组那样通过索引直接访问元素，因此访问操作的时间复杂度为O(n)。
  5. 插入和删除效率高：由于链表中的每个节点都有指针指向下一个节点，因此插入和删除节点的操作相对简单和高效，只需要改变节点之间的指针链接即可，不需要移动其他节点，时间复杂度为O(1)。
  6. 内存空间消耗较大：相比于数组，链表在存储上需要额外的指针来维护节点之间的关系，导致内存空间消耗较大。
  7. 多种类型的链表：除了单链表（每个节点只含一个指向下一个节点的指针），还有双向链表（每个节点既有指向下一个节点的指针，也有指向前一个节点的指针）和循环链表（尾节点指向头节点）等。

链表的分类

单向链表

单向链表是一种线性数据结构，由一系列节点（Node）组成，每个节点（Node）包含一个数据元素（Data）和一个指向下一个节点的指针（Next）。链表的第一个节点称为头节点（Hand）。最后一个节点的指针指向null，表示链表的结束。

  • 头结点（Hand）：链表的入口，用于记录链表的起始位置，指向第一个节点

  • 数据域（Data）：用于存储节点中的数据。

  • 指针域（Next）：用于指向下一个节点的引用。

单向环形链表

单向环形链表是一种特殊类型的链表，其最后一个节点的指针指向链表的头节点，形成一个闭环。单向环形链表可以通过任意一个节点开始遍历整个链表。

双向链表

双向链表是一种每个节点同时包含指向前一个节点和后一个节点的指针的链表。相比于单向链表，双向链表可以实现双向的遍历和操作。双向链表的节点结构包含三个部分：

  • 前驱指针（Prev）：指向前一个节点的指针。
  • 数据域（Data）：用于存储节点中的数据。
  • 后继指针（Next）：指向后一个节点的指针。

双向环形链表

双向环形链表是一种特殊类型的链表，形成一个闭环，并且每个节点都同时具有指向前一个节点和后一个节点的指针。双向环形链表可以通过任意一个节点开始遍历整个链表。

链表的访问

无序链表遍历查找

如果链表是无序的，需要从链表的头节点开始，逐个节点进行比较，直到找到目标节点或者到达链表末尾。这种方式时间复杂度为O(n)，其中n是链表的节点数。

有序链表二分法查找

如果链表是有序的，可以使用二分查找的方法加快查找速度。这种方式可以将查找时间复杂度降低到O(log n)，其中n是链表的节点数。具体步骤如下：

  1. 使用二分查找法，从链表的中间节点开始比较
  2. 如果目标值小于中间节点的值，则在链表的前半部分继续二分查找；
  3. 如果目标值大于中间节点的值，则在链表的后半部分继续二分查找；
  4. 如果目标值等于中间节点的值，则找到了目标节点。

链表的插入

头部插入

将新节点插入到链表的头部，只需要修改头节点的指针即可。这种插入方式的时间复杂度为O(1)。

中间插入

将新节点插入到链表的中间位置，即两个节点之间，需要先找到插入位置。这种插入方式的时间复杂度为O(n)。

尾部插入

将新节点插入到链表的尾部，需要遍历整个链表找到尾节点。这种插入方式的时间复杂度为O(n)。

链表的删除

头部删除

删除链表的头节点，只需修改头节点的指针即可。这种删除方式的时间复杂度为O(1)。

尾部删除

删除链表的尾节点，需要遍历链表找到尾节点并更新前驱节点的指针。这种删除方式的时间复杂度为O(n)。

中间删除

删除链表中的某个中间节点，需要先找到要删除的节点，然后更新前驱节点的指针。这种删除方式的时间复杂度为O(n)。

栈（Stock）

栈的特点

  1. 后进先出（LIFO）：栈是一种具有后进先出的特性的数据结构，最后入栈的元素将首先被访问和弹出。
  2. 限定操作：栈的操作限定为两种基本操作，即入栈（Push）和出栈（Pop）。入栈将元素放入栈顶，出栈将栈顶元素移除并返回。
  3. 单一访问点：栈只能通过栈顶进行访问，无法直接访问栈中的其他元素。需要通过连续的出栈操作将栈顶元素弹出，才能访问到栈中更底层的元素。
  4. 顺序存储：栈可以使用数组或链表来实现，但通常使用数组来实现。数组提供了连续的内存空间，可以快速访问栈顶元素。
  5. 内存管理简单：栈的内存管理由编译器或解释器自动管理，不需要手动分配和释放内存。
  6. 有限容量：栈的容量是有限的，取决于底层实现的数组或链表的大小。当栈满时，继续进行入栈操作会引发溢出的异常。

入栈

入栈表示将元素放入栈顶，不需要遍历整个栈，时间复杂度为O(1)。

出栈

出栈表示从栈顶移除一个元素，不需要遍历整个栈，时间复杂度为O(1)。

队列（Queue）

队列的特点

  1. 先进先出（FIFO）：队列是一种具有先进先出特性的数据结构，最先入队的元素将首先被访问和移出队列。
  2. 限定操作：队列的操作限定为两种基本操作，即入队（Enqueue）和出队（Dequeue）。入队将元素放入队尾，出队将队头元素移出并返回。
  3. 单一插入点和单一删除点：队列只能通过队尾进行插入操作，通过队头进行删除操作，不支持在其他位置插入或删除元素。
  4. 顺序存储：队列可以使用数组或链表来实现，但通常使用数组或循环数组来实现。数组提供了连续的内存空间，可以快速访问队头和队尾元素。
  5. 内存管理简单：队列的内存管理由编译器或解释器自动管理，不需要手动分配和释放内存。
  6. 有限容量：队列的容量是有限的，取决于底层实现的数组或链表的大小。当队列满时，继续进行入队操作会引发溢出的异常。
  7. 阻塞队列和循环队列：除了普通队列，还有阻塞队列和循环队列等变种。阻塞队列在插入和删除操作时具有阻塞特性，当队满时阻塞插入，当队空时阻塞删除。循环队列是通过循环利用数组的空间来实现的，可以提高队列的效率。

队列的入队与出队

队列是一种具有先进先出特性的数据结构，最先入队的元素将首先被访问和移出队列。

树（Tree）

树的特点

  1. 入队列列列列，由节点和边组成。每个节点可以有零个或多个子节点，除了根节点外，每个节点都有一个父节点。
  2. 根节点：树的根节点是顶层节点，它没有父节点，是整个树的起始点。
  3. 子节点和父节点：每个节点可以有零个或多个子节点，子节点是其父节点的直接下级节点，而父节点是其子节点的直接上级节点。
  4. 叶节点：也称为终端节点或叶子节点，是没有子节点的节点，位于树的最底层。
  5. 路径：树中两个节点之间的路径是由连接这两个节点的边组成的序列。
  6. 深度和高度：节点的深度指的是从根节点到该节点的唯一路径上的边数。树的高度指的是树中所有节点的最大深度。
  7. 分支因子：分支因子是指树中每个节点的子节点个数。二叉树是一种特殊的树，其分支因子为2，即每个节点最多有两个子节点。
  8. 无环性：树是一种无环的数据结构，不存在回路或循环。
  9. 有向和无向树：树可以是有向的，其中每条边都有一个方向；也可以是无向的，其中边没有方向限制。

二叉树

二叉搜索树（BST）

二叉搜索树是一种有序的二叉树，每个节点都满足左子树的键值小于根节点的键值，右子树的键值大于根节点的键值。如果二叉搜索树是平衡的，那么时间复杂度为 O(log n)，其中 n 是树中节点的数量。

二叉搜索树可以任意地构造，同样的数字，也可以按照下图的方式来构造

二叉搜索树如果是顺序插入的，可能会导致失去平衡，退化为链表，这样效率就变低了，时间复杂度将退化为 O(n)。

平衡二叉树（AVL Tree）

为了避免二叉搜索树失去平衡退化为链表，可以使用平衡二叉搜索树。平衡二叉树（AVL Tree）是一种自平衡的二叉搜索树，引入了平衡因子的概念，当插入或删除一个节点后，如果导致某个节点的平衡因子的绝对值（左子树高度减右子树高度）大于1，就表示该节点失去了平衡，会采用旋转操作（左旋、右旋、左右旋和右左旋）来进行平衡调整。一般导致失衡的常见情况有四种：LL（左左）、RR（右右）、LR（左右）、RL（右左）

  • LL失衡情况：左子树的左子树发生了插入或删除操作，导致失去平衡，需要进行右旋操作，进行平衡调整。
  • RR失衡情况：右子树的右子树发生了插入或删除操作，导致失去平衡，需要进行左旋操作，进行平衡调整。
  • LR失衡情况：左子树的右子树发生了插入或删除操作，导致失去平衡，需要先进行左旋操作，再进行右旋操作，进行平衡调整。
  • RL失衡情况：右子树的左子树发生了插入或删除操作，导致失去平衡，需要先进行右旋操作，再进行左旋操作，进行平衡调整。

红黑树（Red-Black Tree）

如果插入和删除操作比查询操作频繁且持续进行，平衡二叉树（AVL Tree）为了平衡树，可能需要进行大量的旋转操作，会导致性能下降。针对这种情况，可以考虑使用红黑树。红黑树在插入和删除操作时，会对节点重新染色（红色或黑色）和旋转操作（左旋、右旋、左右旋和右左旋）来保持树的平衡，无需像AVL树那样要求严格的平衡，因此旋转操作较少，性能更好。红黑树需要满足以下规则：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点必须是黑色。
  3. 每个叶子节点（NIL 或空节点）是黑色。
  4. 如果一个节点是红色，那么它的两个子节点都是黑色。
  5. 对于每个节点，从该节点到其子孙节点的所有路径上包含相同数量的黑色节点。

多叉树

B 树（B Tree）

B树是一种自平衡多叉搜索树，所有节点既存放键（key）也存放数据（data）

B + 树（B + Tree）

B + Tree是B 树的变种，在 B 树基础上为叶子节点增加了单向指针，形成有序链表，并且只有叶子节点存放键（key）和数据（data），非叶子节点只存放键（key）

MySQL中的 B + 树（B + Tree）

MySQL索引数据结构对经典的B+Tree进行了优化，将B+ 树中叶子节点之间的单向指针改为双向指针，形成双向链表，可以从两个方向依次遍历叶子节点，可以更快速地定位范围内的数据块，提高查询效率

B-Tree 与 B + Tree 的区别

存储方式的区别

  • B-树：所有节点既存放键（key）也存放数据（data）
  • B+树：只有叶子节点存放键（key）和数据（data），非叶子节点只存放键（key）

叶子节点的区别

  • B-树：叶子节点都是独立的
  • B+树：叶子节点之间通过指针进行连接，形成一个有序链表，顺序查询性能更高

范围查询的区别

  • B-树：需要从头到尾遍历整个索引树，并跳过不符合条件的子树
  • B+树：只需要先定位到符合条件的起始叶子节点，然后沿着叶子节点链表遍历符合条件的数据记录即可

时间复杂度的区别

  • B-树：查询时间复杂度不固定，取决于需要查询的数据（data）在树中的位置，最好情况下为O(1)
  • B+树：查询时间复杂度固定为 log n，因为所有数据（data）存储在叶子节点

图（Graph）

图的特点

  1. 顶点和边：图由一组顶点（节点）和连接这些顶点的边组成。顶点表示实体或对象，边表示顶点之间的关系或连接。
  2. 有向性：图可以是有向的或无向的。有向图中的边具有方向性，表示顶点之间的单向关系；无向图中的边没有方向，表示顶点之间的双向关系。
  3. 权重：边可以带有权重，表示顶点之间的距离、代价或其他度量。权重可以用来表示路径的长度或优先级。
  4. 路径：图中的路径是由顶点和边按一定顺序组成的序列。路径可以是简单路径（不重复经过顶点的路径）或循环路径（起点和终点相同的路径）。
  5. 连通性：图中的顶点之间可能存在连通或非连通的关系。如果在无向图中，每两个顶点之间都存在路径，则称为强连通图；如果在有向图中，每两个顶点之间都存在双向路径，则称为强连通图。
  6. 度：顶点的度是指与该顶点相连的边的数量。在无向图中，度表示与该顶点相邻的其他顶点的数量；在有向图中，度分为入度（指向该顶点的边的数量）和出度（从该顶点出发的边的数量）。
  7. 稀疏性和稠密性：图具有稀疏性或稠密性的概念，取决于边的数量相对于顶点数量的比例。稀疏图表示边相对较少，而稠密图表示边相对较多。

哈希表（Hash Table）

哈希表的特点

  1. 快速的查找和插入：哈希表通过哈希函数将关键字映射到对应的存储位置，使得在哈希表中查找和插入元素的操作具有较快的速度。哈希表的平均时间复杂度为O(1)。
  2. 使用关键字进行存储和检索：哈希表是一种键值对存储结构，每个元素由关键字（Key）和对应的值（Value）组成。通过关键字能够快速定位到对应的值。
  3. 哈希函数的使用：哈希表使用哈希函数将关键字映射到数组的索引位置，以便快速定位到对应的存储位置。哈希函数应该具有良好的分布性，即使输入的关键字稍有变化，哈希函数也能生成不同的哈希值。
  4. 空间效率高：哈希表使用紧凑的数组结构来存储数据，不需要额外的指针和链接信息，因此比一些其他数据结构更节省空间。
  5. 不适用于有序操作：哈希表是基于哈希函数的散列结构，因此其中的元素没有固定的顺序。如果需要对元素进行有序操作，例如对元素进行排序或范围查询，哈希表并不是最合适的选择。
  6. 哈希冲突处理：由于哈希函数的输出范围可能小于关键字的取值范围，不同的关键字可能映射到相同的索引位置，造成冲突。哈希表使用冲突处理技术来解决这个问题，常见的方法包括链表法、开放寻址法等。
  7. 哈希碰撞的影响：由于哈希函数的映射是有限的，存在不同的关键字映射到同一个索引位置的情况。当发生大量的哈希碰撞时，哈希表的性能可能会下降，导致查找和插入的时间复杂度增加。

关键概念

哈希函数

哈希函数（Hash Function）是指能将任意大小的输入（Key）映射到固定大小的哈希值（Hash Value）的函数。哈希函数应该具备以下特点：

  • 一致性：对于相同的输入，哈希函数应始终返回相同的哈希值。这是为了确保同一个关键字始终能够映射到相同的桶中。
  • 均匀性：哈希函数应该将不同的输入均匀地映射到不同的哈希值，以减少哈希冲突的发生。
  • 高效性：哈希函数的计算速度应尽可能快，以减少访问哈希表的时间开销。
  • 雪崩效应：对原始输入进行微小修改，会导致哈希值发生很大的变化，以保证数据的健壮性。
  • 不可逆性：哈希函数应该是单向的，即从哈希值无法推导出原始输入。这是为了保护敏感信息的安全性。
  • 抗碰撞性：哈希函数应尽可能地避免产生哈希冲突，即对于不同的输入，哈希函数返回相同的输出的概率应该很小。
  • 输出固定长度：哈希函数的输出应该是一个固定长度的哈希值。不同大小的输入都应该映射到相同长度的哈希值。

哈希冲突

在理想的情况下，每一个关键字（key）通过哈希函数计算出来的地址都是不一样的。但在实际情况中，可能会碰到两个键不相同（key1≠key2），但是经过哈希函数计算出来的地址出现相同，这种现象称为哈希冲突。

解决哈希冲突的常见方法

  1. 开放地址法（Open Addressing）：当发生哈希冲突时，通过在哈希表中寻找一个新的空闲位置来存储冲突的元素。具体的探测方式包括线性探测、二次探测和双重哈希等。开放地址法的优点是不需要额外的存储空间来处理冲突，但可能会导致聚集现象，即连续发生冲突的元素被放置在相邻的槽位上。
  2. 再哈希法（Rehashing）：使用多个不同的哈希函数来构造哈希表。当发生哈希冲突时，依次尝试其他哈希函数，直到找到一个空闲的槽位。再哈希法的优点是解决了聚集现象的问题，但会增加计算时间，因为需要计算多个哈希函数。
  3. 链地址法（Chaining）：将哈希表的每个槽位上维护一个链表或其他数据结构，所有哈希地址相同的记录都链接在同一链表中。当发生哈希冲突时，将冲突的元素添加到对应槽位的链表中。链地址法的优点是简单且易于实现，但可能会占用更多的内存空间来管理链表。
  4. 建立公共溢出区（Establishing a Public Overflow Area）：将哈希表分为基本表和溢出表，当发生哈希冲突时，将冲突的元素存放在溢出表中。建立公共溢出区的优点是可以避免聚集现象，但需要额外的存储空间，并且在处理溢出表时需要特殊的处理逻辑。

哈希表的组成

哈希表（Hash table），也称为散列表，是一种根据关键字（Key）直接访问数据的数据结构。哈希表（Hash table）通常由哈希函数、数组以及对于解决哈希冲突的方法组成。其中数组被称为哈希桶（bucket），每个哈希桶（bucket）中存储一个链表（或其他数据结构）的元素。

哈希表的工作原理

哈希表的工作原理是通过将关键字（Key）输入哈希函数，得到一个对应的哈希值，再将哈希值映射为数组的索引位置，以便能够快速查找、插入和删除元素。

  1. 输入关键字（Key）：将要存储的元素的关键字输入到哈希函数中。
  2. 哈希函数计算哈希值：哈希函数根据关键字（Key）计算出一个对应的哈希值。
  3. 映射为索引位置：通过对哈希值进行适当的转换映射，将哈希值映射为数组中的索引位置。
  4. 存储和处理冲突：如果多个关键字产生了相同的哈希值，这就是哈希冲突。在哈希表中，通常有多种方法来处理冲突，例如链地址法、开放地址法等。
  5. 插入、查找、删除元素：一旦元素的哈希值被映射为数组的索引位置，我们可以直接在该位置上执行插入、查找和删除操作。

注意细节：通过哈希函数计算出的哈希值的范围是-2147483648 到 2147483647，也就是说大概有 40 亿的映射空间。如果直接将 40 亿的哈希值都映射为数组中的索引，只要映射得比较均匀松散，一般很难出现碰撞（哈希冲突）。但可惜的是内存不能加载 40 亿长度的数组，所以哈希值不能直接进行映射，因此需要将哈希值范围限制在合适的数组索引范围内。一般是通过对哈希值进行取模运算来限制范围，取模运算的除数通常是数组的长度，得到的余数作为最终的索引位置。

堆（Heap）

堆特点

  1. 特殊的树形数据结构：堆是一个完全二叉树或者近似完全二叉树，即除了最后一层外，其他层都是满的，并且最后一层的节点尽可能地靠左排列。
  2. 堆顶元素：堆中的元素按照一定的规则进行排序，其中位于根节点的元素被称为堆顶元素（或称为最大堆的情况下的最大元素、最小堆的情况下的最小元素）。
  3. 堆序性：堆满足堆序性质，即对于最大堆来说，父节点的值大于等于其子节点的值；对于最小堆来说，父节点的值小于等于其子节点的值。因此，堆顶元素是整个堆中的最大或最小元素。
  4. 快速插入和删除：在堆中插入和删除元素的时间复杂度都是O(log n)，其中n是堆中元素的数量。这是因为堆中的排序规则允许在树的顶部进行快速调整。
  5. 优先级队列：堆常常用于实现优先级队列。在优先级队列中，每个元素都有一个关联的优先级，堆的堆序性质保证了具有最高（或最低）优先级的元素位于堆的顶部，可以快速地找到并删除该元素。

大根堆与小根堆

堆（Heap）拥有树状结构，能够保证父节点比子节点大（或小）。当根节点保存堆中最大值时，称为大根堆；反之则称为小根堆。

  • 大根堆（Max Heap）：堆中的最大元素位于根节点，每个父节点的值都大于或等于其子节点的值
  • 小根堆（Min Heap）：一堆中的最小元素位于根节点，每个父节点的值都小于或等于其子节点的值。