深度剖析list底层结构

在《初识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内的底层原理。