C/C++ 数据结构（一）基础概念、线性表链表
本篇核心知识：数据结构四大逻辑结构、两种物理存储、算法三大评价指标（时间 / 空间复杂度、排序稳定性）、线性表分类、单链表概念、名词释义、节点结构、链表分类、单链表增删改查逻辑 + 代码
一、数据结构概述
概念
数据结构用来描述数据元素之间的相互逻辑关系 + 内存存储方式，从「逻辑关系」「物理存放」两个维度划分体系，是各类算法实现的底层载体。
特性
逻辑结构：只管数据抽象关系，和内存怎么存无关；
物理结构：只管数据在内存实际排布，同一逻辑结构可选用不同物理实现；
学习路线：逐个吃透每种结构→实现增删改查→结合对应排序算法。
二、四大逻辑结构
概念
1.集合结构：所有数据同属一个集合范围，元素之间无任何关联关系。
2.线性结构：元素之间一对一前后相邻，排成一条逻辑链。
3.树形结构：元素一对多的层级从属关系。
4.图形结构：元素多对多互相连通，任意节点可双向建立联系。
特性
1.集合结构：仅归属同一个整体，不存在前驱、后继、从属关系。
2.线性结构：除首元素无前驱、尾元素无后继，其余元素各有唯一前驱、唯一后继。
3.树形结构：一个父节点可以拥有多个子节点，子节点仅有一个直接父节点；存在唯一根节点，逐层向下延伸。
4.图形结构：无固定头尾，节点间连接自由。
拓展
1.集合结构：C++ 可用数组、容器 set 实现集合存储。
2.线性结构：典型实现：顺序表、链表、栈、队列。
3.树形结构：典型实现：二叉树。
三、两种物理（存储）结构
概念
1.顺序存储：数据在内存占用连续整块空间，数组是原生实现。
2.链式存储：数据分散在内存零散地址，依靠指针保存相邻元素地址维系逻辑关系。
特性
1.顺序存储：通过下标随机访问，访问效率(O(1))；中间插入 / 删除需要批量挪动元素，效率低。
2.链式存储：插入删除仅修改指针指向，无需挪动数据；不能随机下标访问，只能从头依次遍历。
代码示例
// 顺序存储 int arr[6] = {1,2,3,4,5,6}; cout << arr[3]; // 下标随机访问 // 链式存储 struct Node{ int data; Node* next; };相似概念比较
顺序存：连续内存、随机访问快、增删慢；
链式存：离散内存、随机访问慢、增删快。
四、算法三大评判标准
（1）时间复杂度
概念
使用大 O 记法，衡量代码执行步数随数据量n的增长趋势，忽略常数、低次项。
特性（由优→劣排序）
(O(1))常数 < (O(logn))对数 < (O(n))线性 < (O(nlogn))线性对数 < (O(n^2))平方 < (O(2^n))指数
1.(O(1))：固定代码行，无循环；
2.(O(logn))：循环变量成倍增减（i *= 2）；
3.(O(n))：单层循环；
4.(O(n^2))：双层嵌套循环。
代码示例
// O(1) int a = 10; // O(n) for(int i=0;i<n;i++); // O(logn) int i=1; while(i<n) i *=2; // O(n²) for(int i=0;i<n;i++) for(int j=0;j<n;j++);（2）空间复杂度
概念
大 O 记法，统计算法运行临时开辟的内存开销，原始输入内存不计入。
特性
(O(1))：临时变量固定，不随 n 变化；
(O(n))：动态开辟数组，空间随 n 线性增长。
代码示例
// O(1) int tmp; // O(n) int* p = new int[n];（3）排序稳定性
概念
原序列中值相等元素，排序后相对先后位置不变 = 稳定；位置颠倒 = 不稳定。
特性
稳定排序：冒泡、直接插入；
不稳定排序：选择排序。
举例
原序列：[6 (红),6 (绿),5]，稳定排序后仍红在前、绿在后。
五、线性表
概念
由同类型数据按一对一逻辑关系构成的线性结构，整体元素数量称为线性表长度；分为顺序表、链表两类。
特性
顺序表：逻辑线性、物理内存连续（数组实现），支持下标随机访问；中间插入 / 删除需要批量挪动数据，效率偏低。
链表：逻辑线性、物理地址零散不连续，依靠指针维系前后关系；无法随机下标访问，插入删除仅修改指针，效率高。
相似对比
| 类型 | 访问 | 增删 | 存储 |
|---|---|---|---|
| 顺序表 | 随机 O (1) | 中间低效 | 连续内存 |
| 链表 | 只能遍历 O (n) | 任意位置高效 | 离散内存 |
六、链表基础名词
概念
链式存储实现的线性表，由多个节点串联组成，依托指针保存相邻节点地址。
特性
节点构成：数据域（存有效数据）+ 指针域（存其他节点地址）。
前驱 / 后继：前面 / 后面的所有节点
直接前驱：紧贴当前的上一个节点；
直接后继：紧贴当前的下一个节点。
头指针：存储链表首节点地址，用来找到整条链表。
头结点：链表最前端附加节点，不存储有效业务数据，仅存指针；
优势：链表为空、首节点增删时不用特殊处理头指针，统一代码逻辑。
尾节点：链表最后一个节点，后继指针置
nullptr。
代码示例（单链表节点）
struct Node { int data; // 数据域 Node* next; // 指针域 // 构造函数快速初始化 Node(int val) : data(val), next(nullptr) {} };七、链表四大分类
概念
根据指针数量与首尾连接形式区分
特性
单链表：仅存后继指针，只能从头向后单向遍历（本节课重点）。
双向链表：同时存前驱 + 后继指针，可前后双向遍历。
循环链表：尾节点指针指向头，首尾相连成环形。
相交链表：两条链表部分节点地址重合，共享尾部子链。
八、单链表常用操作逻辑（创建、增、删、改、查、遍历打印）
1. 尾插法创建链表
概念
从链表尾部逐个新增节点，用尾指针记录末尾，优化遍历开销。
特性
空链表：头结点与尾指针同时指向第一个新节点；
非空：新节点接在尾节点后，再更新尾指针。
代码示例
// 参数：创建节点个数，返回链表头结点 Node* createList(int n) { Node* head = new Node(0); // 头结点无有效数据 Node* tail = head; for(int i=1;i<=n;i++){ Node* newNode = new Node(i); tail->next = newNode; tail = newNode; } return head; }2. 遍历打印
概念
从头结点后继开始循环遍历，依次输出数据，指针为空结束。
特性
遍历不修改原链表，形参用头指针即可。
void print(Node* head) { Node* p = head->next; while(p != nullptr){ cout << p->data << " "; p = p->next; } cout << endl; }3. 指定位置插入
概念
在指定下标前插入新节点
特性
先让新节点指向后继，再修改前驱指向新节点（防止断链）
void insert(Node* head, int pos, int val) { Node* p = head; // 走到插入位置前一个节点 for(int i=0; i<pos && p->next; i++) p = p->next; Node* newNode = new Node(val); newNode->next = p->next; // 新节点先接后面 p->next = newNode; // 前驱再接新节点 }4. 按值删除
概念
查找目标值节点，断开链接并释放内存
特性
先保存待删节点地址，修改前驱指针后delete释放，避免内存泄漏
void delByVal(Node* head, int val) { Node* p = head; // 找到待删节点的前驱 while(p->next && p->next->data != val) p = p->next; if(p->next == nullptr) return; // 无目标 Node* temp = p->next; p->next = temp->next; delete temp; }5. 修改 & 查找
修改
遍历匹配数值，直接改写数据域；
查找
找到返回节点指针，找不到返回空。
//查找 Node* find(Node* head,int key){ Node* p=head->next; while(p&&p->data!=key) p=p->next; return p; } //修改 void modify(Node* head,int old,int newVal){ Node* p=find(head,old); if(p) p->data = newVal; }九、拓展
插入顺序不可逆：新节点先接后继，再改前驱，颠倒会丢失整条后续链表；
删除必须释放
delete，长期遗漏造成内存泄漏；头结点设计：规避首节点增删时头指针特殊判断。
同一逻辑结构可以选用不同物理实现（如线性→数组 / 链表），是数据结构灵活设计的核心。