C++ 顺序表与链表：原理、实现与对比

1. 引言在 C 数据结构的学习中顺序表动态数组和链表是最基础也最重要的两种线性表存储结构。它们都用于存储一组具有线性关系的数据元素但在内存布局、插入删除效率、访问方式等方面存在显著差异。本文将从原理出发结合 C 代码实现系统对比两者的特点与适用场景。2. 顺序表动态数组2.1 基本原理顺序表使用一段连续的存储单元依次存放数据元素逻辑上相邻的元素在物理地址上也相邻。C 标准库中的std::vector就是典型的动态顺序表实现它会在容量不足时自动扩容。顺序表的核心特点随机访问通过下标可在 O(1) 时间内访问任意元素。插入删除慢在中间位置插入或删除元素需要移动大量后续元素平均时间复杂度为 O(n)。空间连续对 CPU 缓存友好遍历效率高。2.2 C 实现示例下面给出一个基于动态数组的简单顺序表实现支持插入、删除和按位置访问。#include iostream #include stdexcept template typename T class SeqList { private: T* data; // 存储数据的数组 int capacity; // 当前容量 int size; // 当前元素个数 void resize() { capacity capacity 0 ? 4 : capacity * 2; T* newData new T[capacity]; for (int i 0; i size; i) { newData[i] data[i]; } delete[] data; data newData; } public: SeqList() : data(nullptr), capacity(0), size(0) {} ~SeqList() { delete[] data; } void pushBack(const T value) { if (size capacity) { resize(); } data[size] value; } void insert(int index, const T value) { if (index 0 || index size) { throw std::out_of_range(index out of range); } if (size capacity) { resize(); } for (int i size; i index; --i) { data[i] data[i - 1]; } data[index] value; size; } void remove(int index) { if (index 0 || index size) { throw std::out_of_range(index out of range); } for (int i index; i size - 1; i) { data[i] data[i 1]; } --size; } T operator[](int index) { if (index 0 || index size) { throw std::out_of_range(index out of range); } return data[index]; } int getSize() const { return size; } int getCapacity() const { return capacity; } };3. 链表3.1 基本原理链表通过节点Node存储数据每个节点包含数据域和指向下一个节点的指针域节点在内存中不必连续。C 标准库中的std::list是双向链表实现。链表的核心特点插入删除快只要找到目标位置插入和删除操作只需修改指针时间复杂度为 O(1)。不支持随机访问访问第 k 个元素需要从头遍历时间复杂度为 O(n)。空间不连续节点分散存储对缓存不友好且每个节点需要额外存储指针空间开销更大。3.2 C 实现示例下面给出一个单链表的简单实现支持头插、尾插、删除和遍历。#include iostream template typename T class LinkedList { private: struct Node { T data; Node* next; Node(const T value) : data(value), next(nullptr) {} }; Node* head; int size; public: LinkedList() : head(nullptr), size(0) {} ~LinkedList() { Node* cur head; while (cur ! nullptr) { Node* next cur-next; delete cur; cur next; } } void pushFront(const T value) { Node* newNode new Node(value); newNode-next head; head newNode; size; } void pushBack(const T value) { Node* newNode new Node(value); if (head nullptr) { head newNode; } else { Node* cur head; while (cur-next ! nullptr) { cur cur-next; } cur-next newNode; } size; } void remove(const T value) { Node* cur head; Node* prev nullptr; while (cur ! nullptr) { if (cur-data value) { if (prev nullptr) { head cur-next; } else { prev-next cur-next; } delete cur; --size; return; } prev cur; cur cur-next; } } void print() const { Node* cur head; while (cur ! nullptr) { std::cout cur-data ; cur cur-next; } std::cout std::endl; } int getSize() const { return size; } };4. 顺序表与链表的对比下表从多个维度对比顺序表和链表的核心差异帮助你在实际开发中做出选择。对比维度顺序表vector链表list内存布局连续存储离散存储节点间通过指针连接随机访问O(1)支持下标访问O(n)需从头遍历头部插入O(n)需移动所有元素O(1)只需修改指针尾部插入均摊 O(1)可能触发扩容O(1)双向链表维护尾指针中间插入/删除O(n)需移动元素O(1)已知位置时空间开销较小仅数据本身较大每个节点额外存储指针缓存友好性高连续内存利于预取低节点分散导致缓存命中率低扩容机制容量不足时自动扩容倍增无需扩容按需分配节点从时间复杂度来看顺序表和链表在插入、删除、查找三类核心操作上各有侧重。顺序表凭借连续内存支持 O(1) 的随机访问但中间插入和删除需要移动大量元素代价为 O(n)链表则相反只要已知目标位置插入和删除只需修改指针可在 O(1) 内完成但查找第 k 个元素必须从头遍历代价为 O(n)。在实际工程中应根据操作频率来权衡如果程序以随机访问和遍历为主插入删除较少顺序表是更优选择如果程序频繁在头部或中间插入删除且对随机访问需求不高链表更合适。此外还需考虑缓存效应——顺序表的连续内存对 CPU 缓存友好在数据量较大时遍历性能往往明显优于链表因此即使部分场景涉及插入删除std::vector也常常比std::list更快。建议优先使用标准库容器并结合真实业务的操作分布做基准测试再决定最终选型。5. 如何选择在实际开发中选择顺序表还是链表应结合具体场景频繁随机访问优先选择顺序表O(1) 的下标访问优势明显。频繁在头部或中间插入删除优先选择链表避免大量元素移动。数据量小且遍历为主顺序表更合适缓存友好且空间开销小。元素数量动态变化大链表按需分配节点避免扩容带来的拷贝开销但顺序表的均摊扩容成本通常也可接受。需要特别说明的是现代 CPU 的缓存机制使得顺序表在大多数场景下表现优于链表即使涉及插入删除std::vector也常常比std::list更快。因此除非有明确的频繁中间插入删除需求否则优先考虑顺序表。6. 总结顺序表和链表是线性表的两种基本存储方式各有优劣。顺序表擅长随机访问和缓存友好遍历链表擅长频繁插入删除。理解两者的底层原理和复杂度差异是写出高效 C 代码的重要基础。在实际工程中建议优先使用标准库的std::vector和std::list仅在特殊需求下才自行实现。