单链表

数据结构基础

数据定义

• 数据(data)：客观事物的符号表示，可被计算机程序处理的所有符号
• 数据元素(data element)：数据的基本单位，由若干数据项组成

  struct student {
      std::string name;  // 数据项
      int age;           // 数据项
      float score;       // 数据项
  };

• 数据对象(data object)：性质相同的数据元素集合

  struct student class[20];  // class数组是数据对象

数据结构分类

结构类型	描述	特点
集合结构	元素间无特定关系	仅同属一个集合
线性结构	元素间一对一关系	顺序排列（如线性表）
树状结构	元素间一对多关系	层次关系
网状结构	元素间多对多关系	图状关系

数据结构形式定义

• 二元组表示：Data_Structure = (D, S)
  • D：数据元素有限集
  • S：D上关系的有限集（逻辑结构）
• 物理结构：数据元素在计算机中的存储表示（存储结构）

线性结构（线性表）

基本特性

• 示例：26个英文字母、学号序列、日期序列
• 核心性质：
  1. 存在唯一的"第一个"数据元素
  2. 存在唯一的"最后一个"数据元素
  3. 除首元素外，每个元素有且仅有一个前驱结点
  4. 除尾元素外，每个元素有且仅有一个后继结点

物理结构实现

存储方式	特点	实现形式
顺序存储	地址连续的存储单元	数组、动态内存分配
链式存储	地址不一定连续的存储单元	链表（单/双/静态链表）

单链表（无头结点）

基本概念

• 链表定义：由包含指针成员的结构体（结点）通过指针链接形成的链式数据结构
• 结点结构：

  struct Node {
      int data;        // 数据域（存储数据）
      Node* next;     // 指针域（存储指向下一个结点的地址）
  };

关键结点

结点类型	特点	指针状态
首结点	唯一无前驱、只有后继	指向后继结点
尾结点	唯一无后继、只有前驱	指向nullptr
中间结点	既有前驱也有后继	指向后继结点

链表创建

从无到有过程

1. 初始状态：链表指针指向nullptr

   List_ptr → nullptr

2. 创建首结点：

   List_ptr → [data|next] → nullptr

增加结点方法

方法	操作描述	特点
尾插法	新结点插入原尾结点后，成为新尾结点	保持原始顺序
头插法	新结点插入原首结点前，成为新首结点	逆序排列
中间插入法	通过数据比对确定位置插入，保持链表有序	需头尾插法配合

链表操作

遍历链表

Node* current = list_ptr;
while(current != nullptr) {
    std::cout << current->data << " ";
    current = current->next;
}

删除结点

// 查找待删除结点
Node* prev = nullptr;
Node* current = list_ptr;

while(current != nullptr && current->data != target) {
    prev = current;
    current = current->next;
}

if(current == nullptr) return; // 未找到

// 分类处理删除操作
if(prev == nullptr) { 
    // 情况1：删除首结点
    list_ptr = current->next;
} else if(current->next == nullptr) { 
    // 情况2：删除尾结点
    prev->next = nullptr;
} else { 
    // 情况3：删除中间结点
    prev->next = current->next;
}

delete current; // 释放结点空间

数组与链表对比

特性	数组	链表
内存布局	连续地址空间	非连续地址空间
访问效率	O(1)随机访问	O(n)顺序访问
插入删除	O(n)元素移动	O(1)指针修改
空间利用	可能浪费/不足	按需分配无浪费
内存碎片	较少	较多
适用场景	频繁访问、固定大小数据	频繁增删、动态大小数据

作业

实现中间插入法创建有序链表：

void insertSorted(Node*& head, int value) {
    Node* newNode = new Node{value, nullptr};
    
    // 情况1：空链表或新值小于首结点
    if(head == nullptr || value < head->data) {
        newNode->next = head;
        head = newNode;
        return;
    }
    
    // 查找插入位置
    Node* current = head;
    while(current->next != nullptr && current->next->data < value) {
        current = current->next;
    }
    
    // 插入新结点
    newNode->next = current->next;
    current->next = newNode;
}