在《初识STL库中的list容器》我们就曾明确谈到list容器是双向链表,每一个节点由两个指针和数据组成,两个指针分别指向前一个节点和后一个节点。长这样:

链表属于相对简单的数据结构,我们也可以手搓一个简单链表:
首先先创建一个结构体,包括数据域和指针域:
struct node
{
int n;//数据域
/*创建node指针初始值为空*/
node* next=nullptr;//指向后一个节点
node* pre = nullptr;//指向前一个节点
}那就简单创建一个链表类并实现简单的增删查改。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3F3F3F3F;//如果没有该元素 反馈个int最大值
/*结构体创建*/
struct Node {
int data;
Node* pre;
Node* next;
Node(const int& val) : data(val), pre(nullptr), next(nullptr) {}
};
class myList {
public:
/*变量设计*/
Node* head;
Node* tail; //维护一个尾指针,直接通过访问尾指针进行添加而无需从前往后遍历
size_t m_size; //统计容器内元素总和,改名为m_size避免与size()函数冲突
myList() : head(nullptr), tail(nullptr), m_size(0) {} //构造函数
~myList() {//析构函数
clear();
}
// 尾部添加元素
void push_back(const int& val) {
Node* new_node = new Node(val);//在堆区创建一个新node
if (tail == nullptr) { // 空链表,直接更新首尾指针
head = tail = new_node;
} else {//非空直接在尾部更新指针
tail->next = new_node;
new_node->pre = tail;
tail = new_node;
}
m_size++; //动态记录容器内元素总和
}
// 尾部删除元素
void pop_back() {
if (tail == nullptr) {return;}//无则return
Node* temp = tail;//创建node*中间变量暂时存储尾部节点地址
if (head == tail) { // 只有一个元素 需要更新头指针
head = tail = nullptr;
} else {
tail = tail->pre;
tail->next = nullptr;
}
delete temp;//通过临时指针释放堆区内存
m_size--;//动态记录容器内元素总和
}
// 访问元素 基于0-based
int at(size_t index) {
if (index >= m_size){return INF;}//没有该下标,直接returnINF ;
/*根据下标移动指针*/
Node* current = head;
for (size_t i = 0; i < index; ++i) {
current = current->next;
}
return current->data;
}
// 获取大小
size_t size() const {
return m_size;
}
// 检查是否为空
bool empty() const {
return m_size == 0;
}
//全部清空
void clear() {
while (!empty()) {
pop_back();
}
}
};
void test()
{
myList ml;
for(int i=0;i<5;++i)
{
ml.push_back(i+1);
}
cout << "遍历mylist容器{1,2,3,4,5}分别是:" ;
for(int i=0;i<5;++i)
{
cout << ml.at(i) << " ";
}
cout << '\n';
cout << "通过pop_back()删除尾部元素后,遍历容器:";
ml.pop_back();
for(int i=0;i<ml.size();++i) // 应该用ml.size()而不是固定5
{
cout << ml.at(i) << " ";
}
cout << '\n';
cout << "清除容器所有元素:" << '\n';
ml.clear();
cout << "此时容器内一共" << ml.size() << "个元素\n";
}
int main() {
test();
return 0;
}编译结果:

我们成功实现一个简单的int型的双向链表,从节点创建到指针移动,从增删改查到最后的析构函数,都属于list容器最基础的知识,希望通过这个例子,读者能够掌握到list内的底层原理。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程