链表是一种非连续存储的线性数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针域，相比数组具有动态扩容、插入删除效率高的特点，是C++数据结构学习的核心内容之一。
链表的基础结构定义
实现链表首先需要定义节点结构体，节点需要存储数据和下一个节点的地址，我们以存储整型数据的单向链表为例，节点定义如下：
// 定义链表节点结构体
struct ListNode {
int val; // 数据域，存储节点值
ListNode* next; // 指针域，指向下一个节点
// 构造函数，初始化节点值和指针
ListNode(int x) : val(x), next(nullptr) {}
};
链表类的整体设计
我们可以封装一个链表类，包含头节点指针和常用的操作方法，整体类框架如下：
class MyLinkedList {
private:
ListNode* head; // 链表头节点
int size; // 链表长度
public:
// 构造函数，初始化空链表
MyLinkedList();
// 获取链表中第index个节点的值，索引从0开始
int get(int index);
// 在链表头部插入节点
void addAtHead(int val);
// 在链表尾部插入节点
void addAtTail(int val);
// 在第index个节点前插入值为val的节点
void addAtIndex(int index, int val);
// 删除第index个节点
void deleteAtIndex(int index);
// 释放链表内存
~MyLinkedList();
};
核心方法实现
构造函数与析构函数
构造函数初始化空链表，头节点设为空，长度为0；析构函数需要遍历释放所有节点的内存，避免内存泄漏：
MyLinkedList::MyLinkedList() {
head = nullptr;
size = 0;
}
MyLinkedList::~MyLinkedList() {
ListNode* curr = head;
while (curr != nullptr) {
ListNode* temp = curr;
curr = curr->next;
delete temp;
}
}
获取节点值方法
get方法需要先判断索引是否合法，再遍历到对应位置返回节点值：
int MyLinkedList::get(int index) {
// 索引不合法返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode* curr = head;
// 遍历到索引位置
for (int i = 0; i < index; i++) {
curr = curr->next;
}
return curr->val;
}
头部插入节点
头部插入只需要创建新节点，让新节点的next指向原来的头节点，再更新头节点即可：
void MyLinkedList::addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
head = newNode;
size++;
}
尾部插入节点
尾部插入需要遍历到最后一个节点，让最后一个节点的next指向新节点：
void MyLinkedList::addAtTail(int val) {
ListNode* newNode = new ListNode(val);
// 如果链表为空，直接更新头节点
if (head == nullptr) {
head = newNode;
} else {
ListNode* curr = head;
// 遍历到最后一个节点
while (curr->next != nullptr) {
curr = curr->next;
}
curr->next = newNode;
}
size++;
}
指定位置插入节点
指定位置插入需要处理索引为0（头部插入）、索引等于size（尾部插入）和中间插入三种情况：
void MyLinkedList::addAtIndex(int index, int val) {
// 索引大于长度不插入，索引小于0插入到头部
if (index > size) return;
if (index <= 0) {
addAtHead(val);
return;
}
if (index == size) {
addAtTail(val);
return;
}
ListNode* newNode = new ListNode(val);
ListNode* curr = head;
// 遍历到插入位置的前一个节点
for (int i = 0; i < index - 1; i++) {
curr = curr->next;
}
newNode->next = curr->next;
curr->next = newNode;
size++;
}
删除指定位置节点
删除节点需要先判断索引合法性，再找到待删除节点的前一个节点，修改指针指向后释放内存：
void MyLinkedList::deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
ListNode* temp;
// 删除头节点的情况
if (index == 0) {
temp = head;
head = head->next;
} else {
ListNode* curr = head;
// 遍历到待删除节点的前一个节点
for (int i = 0; i < index - 1; i++) {
curr = curr->next;
}
temp = curr->next;
curr->next = temp->next;
}
delete temp;
size--;
}
完整测试示例
我们可以编写测试代码验证链表的功能是否正常：
#include <iostream>
using namespace std;
// 这里放入前面定义的ListNode结构体和MyLinkedList类的所有代码
int main() {
MyLinkedList* linkedList = new MyLinkedList();
linkedList->addAtHead(1);
linkedList->addAtTail(3);
linkedList->addAtIndex(1, 2); // 链表变为1->2->3
cout << linkedList->get(1) << endl; // 输出2
linkedList->deleteAtIndex(1); // 链表变为1->3
cout << linkedList->get(1) << endl; // 输出3
delete linkedList;
return 0;
}
实现注意事项
- 操作指针时要注意空指针判断，避免访问空指针导致程序崩溃
- 动态分配的内存需要在析构函数中释放，防止内存泄漏
- 插入删除操作时要正确处理指针的指向关系，避免链表断裂
- 索引相关的操作要先校验合法性，避免越界访问