数据结构一-迪斯科星球

数据结构一

数据结构是计算机领域的核心基础，在求职面试、考研、保研等场景中均为重点考察内容。本文系统梳理数据结构的核心意义、时间复杂度评判标准，以及数组、链表、哈希表、二叉树等经典结构的原理与特性，建立完整的入门知识框架。

一、为什么要学习数据结构

数据结构的核心价值，是对大规模数据进行合理的存储规划，从而提升查找、插入、删除等操作的执行效率。

我们可以用图书馆藏书做类比：

家中只有几十本书时，随意摆放也能快速找到，效率差异可以忽略
图书馆有百万级藏书，如果杂乱堆放，每次借阅都需要全量翻找，效率会极低
通过分门别类（文学、理工、计算机等层级分类）存放，前期需要付出整理成本，但后续查找能直接缩小范围，效率大幅提升

计算机中的海量数据同理：磁盘、服务器中存储着TB级甚至更多数据，如果毫无规律地存储，每次查找都要遍历全部内容，耗时无法接受。数据结构就是通过设计不同的组织存储方式，针对性地优化特定操作的性能。

关键前提：数据结构的优劣只在大规模数据下才能体现。只有十几个数据时，任何结构的执行时间差异都微乎其微，只有数据量达到一定量级，结构的性能差异才会凸显。

二、算法效率的评判标准：时间复杂度

1. 为什么不用真实运行时间？

直观来看，程序运行时间越短效率越高，但真实运行时间受太多外部因素干扰，无法作为客观标准：

硬件性能差异：高端CPU和低端CPU的运算速度天差地别
系统调度影响：CPU何时分配时间片给当前程序存在随机性
长周期算法：需要运行数天的模型，不可能通过实测时间评判优劣

因此行业统一使用**「基础操作的执行次数」**作为评判依据：计算机单次基础操作的耗时是固定的，完成同一件事，需要的操作次数越少，算法效率越高。

2. 大O表示法

时间复杂度用大O符号描述，核心是刻画「操作次数随数据量增长的变化趋势」，遵循抓主要矛盾、忽略低影响项的原则：

忽略常数项与常数系数：如y = ax + b简化为O(n)
只保留最高次项：如y = ax² + bx + c简化为O(n²)
数据规模越大，低次项的影响越可以忽略

3. 常见时间复杂度与增长趋势

从优到劣，最核心的四类时间复杂度：

O(1) 常数级：无论数据量多大，操作次数固定，是最优的时间复杂度
O(logn) 对数级：数据量翻倍，操作次数仅增加1次，效率极高
O(n) 线性级：操作次数与数据量成正比
O(n²) 平方级：操作次数随数据量呈平方增长，效率较低

增长速度对比：O(1) < O(logn) < O(n) < O(n²)

计算机中绝大多数操作都依赖查找，因此数据结构优化的核心目标，就是尽量将查找效率从O(n)降低到O(logn)甚至O(1)。

4. 经典场景的时间复杂度推导

（1）无序数组遍历查找：O(n)

在长度为n的无序数组中，从头到尾逐个比对目标值。

最优情况：第一个元素就是目标，仅1次操作
最坏情况：最后一个元素才是目标，需要n次操作
平均情况：约遍历一半数据，即 n/2 次
忽略常数系数后，时间复杂度为O(n)。

（2）等差数列公式求和：O(1)

对1到n的等差数列求和，两种思路效率天差地别：

思路1：循环遍历累加，每个数相加一次，共n次操作，时间复杂度O(n)
思路2：直接套用求和公式sum = n*(n+1)/2，仅需1次运算

第二种思路无论n多大，操作次数固定，时间复杂度为O(1)。这也说明：同一件事，算法思路不同，效率差距可以非常大。

（3）冒泡排序：O(n²)

冒泡排序的核心逻辑：相邻元素两两比较，小数前移、大数后移，每一轮都会让当前最大的数“冒泡”到末尾的正确位置。

第1轮：遍历全部n个数据，比较n-1次，1个数据归位
第2轮：遍历前n-1个数据，比较n-2次，第2个数据归位
…
最后1轮：仅比较1次，最后2个数据同时归位

总操作次数为等差数列求和：1+2+...+(n-1) = n*(n-1)/2，最高次项为n²，因此时间复杂度为O(n²)。

冒泡排序可做优化：如果某一轮遍历中没有发生任何交换，说明数组已经完全有序，可以提前终止。但最坏场景下，时间复杂度仍为O(n²)。

（4）二分查找：O(logn)

二分查找必须基于有序数组，核心逻辑：每次和中间值比较，直接丢弃一半不可能的区间。

初始查找范围：n个数据
第1次比较：丢弃一半，剩余 n/2 个数据
第2次比较：再丢弃一半，剩余 n/4 个数据
…
直到范围缩小到1个数据，比较后结束

设共比较k次，则满足n / 2^k = 1，推导得k = log₂n。忽略底数常数，时间复杂度为O(logn)。

5. 快速判断时间复杂度的技巧

从头到尾全量遍历数据：O(n)
循环中数据量持续折半：O(logn)
k层和数据量n相关的嵌套循环：O(n^k)（两层嵌套即为O(n²)）

三、经典数据结构详解

1. 数组

数组是最基础的线性结构，底层是一块连续的内存空间，每个元素对应唯一的下标索引。

核心优势：通过下标随机访问元素，时间复杂度O(1)，速度极快
劣势：
- 无序数组查找效率低，为O(n)
- 有序数组可通过二分查找达到O(logn)，但将无序数据转为有序需要排序，本身有时间成本（如快速排序O(nlogn)、冒泡排序O(n²)）
- 插入、删除元素需要移动后续所有元素，效率较低

2. 链表

链表是另一种线性结构，内存空间不连续，由一个个独立的节点串联而成。

节点结构：每个节点包含两部分——数据域（存储本身的数值）+指针域（存储下一个节点的内存地址）
常见分类：
- 单链表：每个节点只记录下一个节点的地址，只能从头向后单向遍历
- 双向链表：每个节点同时记录上一个和下一个节点的地址，支持双向遍历

链表的核心特性

优势：插入、删除节点只需要修改相邻节点的指针，不需要移动批量数据，操作本身为O(1)（前提是已定位到目标位置）
劣势：
- 无法随机访问，查找必须从头节点开始逐个遍历，时间复杂度O(n)
- 即使链表有序，也无法使用二分查找——无法直接定位中间节点，必须遍历才能到达
- 每个节点需要额外存储指针，空间开销大于数组

3. 哈希表（散列表）

哈希表结合了数组和链表的优势，目标是让查找效率接近O(1)，是工业界最常用的快速查找结构。

核心原理

底层主体是一个数组
通过哈希函数（常见如「数值对数组长度取余」）计算数据应该存储的数组下标
存数据时按计算出的下标存入，查数据时按同样的公式计算下标，直接定位，理想情况时间复杂度O(1)

哈希冲突（哈希碰撞）

两个不同的数值，通过哈希函数计算出了同一个下标，这就是哈希冲突。如果直接覆盖写入，会导致原有数据丢失。

经典解决方案：链地址法

数组的每个位置不直接存单个数据，而是挂载一条链表：算出同一下标的所有数据，都挂到对应位置的链表上。

查找流程：先算下标定位到链表，再遍历链表查找目标
链表较短时，遍历开销可忽略，整体仍可视为O(1)
性能优化：当链表长度超过阈值时，将链表转换为红黑树，查找效率提升为O(logn)，避免链表过长导致性能退化

4. 二叉树

基础概念

树是一种层级结构，类似倒置的自然树：

最顶端的节点叫根节点
没有子节点的节点叫叶子节点
每个节点向下分出的分支叫子树，分为左子树、右子树
二叉树：每个节点最多有两个子节点

有序二叉树（二叉搜索树）

有序二叉树是专门用于查找的基础二叉树，核心规则：任意节点的左子树所有节点值 < 当前节点值 < 右子树所有节点值。

构建逻辑

逐个插入数据，从根节点开始匹配：

第一个数据作为根节点
后续数据从根节点开始比较：比当前节点小走左子树，比当前节点大走右子树
走到空位置时完成插入

查找效率

查找过程和二分查找逻辑一致：从根节点开始，每次比较后丢弃一整侧分支，比较次数等于树的层数。

理想平衡状态：每层节点数翻倍，n个数据的树高约为log₂n，查找时间复杂度为O(logn)
极端退化场景：如果按有序顺序插入数据（如1、2、3、4、5），树会退化成一条链表，高度为n，查找时间复杂度退化为O(n)，效率骤降

平衡二叉树与红黑树

为了解决有序二叉树容易退化的问题，出现了可以自动维持平衡的树结构：

平衡二叉树：严格维持左右子树高度差不超过1，保证树高始终为logn，查找效率稳定O(logn)，但插入删除时调整平衡的成本较高
红黑树：一种近似平衡的二叉树，通过红黑节点规则维持大致平衡，插入、删除、查找效率均稳定在O(logn)，是工业界最主流的平衡树实现

5. 多叉树（B树、B+树）

二叉树在数据量极大时，树高依然会很高。如果数据存储在磁盘上，每访问一层树就需要一次磁盘IO，而磁盘IO速度远慢于内存，树高越高，IO次数越多，查找越慢。

B树、B+树属于多叉树，每个节点可以存储多个数据、分出多个分支，相同数据量下树高远低于二叉树，能大幅减少磁盘IO次数，因此广泛应用于数据库索引、文件系统设计中。

四、总结

不存在绝对最优的数据结构，每种结构都有自己的优缺点和适用场景：

追求随机访问、数据长度固定：优先选择数组
频繁增删节点、很少随机查找：优先选择链表
追求单点快速查找、无强有序需求：优先选择哈希表
需要有序范围查询、追求稳定性能：优先选择红黑树、B+树

数据结构的本质是权衡——根据业务的操作特点，用空间换时间，或者用灵活性换效率。这些底层原理是所有编程语言通用的基本功，底层逻辑吃透后，学习任何语言的对应实现都能快速上手。

企业官网建设流程全解析