C++之list的自我实现

代码语言：javascriptAI代码解释{ }// 指向前驱节点// 指向后继节点T _val;// 存储的数据值核心作用：作为链表的基本单元，封装节点数据和指针关系代码语言：javascriptAI代码解释// 封装的节点指针模板参数解析T：节点数据类型Ref：引用类型（T&或const T&）Ptr：指针类型（T或const T代码语言：javascriptAI代码解释// 元素计数器//

a***1314

129人浏览 · 2026-01-16 03:42:11

a***1314 · 2026-01-16 03:42:11 发布

一、节点类：ListNode

1.1 类定义与作用

代码语言：javascript

AI代码解释

template<class T>
struct ListNode {
    ListNode(const T& val = T())
        :_pPre(nullptr), _pNext(nullptr), _val(val) 
    { }
    
    ListNode<T>* _pPre;  // 指向前驱节点
    ListNode<T>* _pNext; // 指向后继节点
    T _val;              // 存储的数据值
};

核心作用：作为链表的基本单元，封装节点数据和指针关系

1.2 关键特性

双向指针：_pPre和_pNext实现双向链接
默认构造函数：支持无参创建空节点
值初始化：通过T()提供默认值初始化
模板化设计：支持任意数据类型存储

二、迭代器类：ListIterator

2.1 类定义与模板参数

代码语言：javascript

AI代码解释

template<class T, class Ref, class Ptr>
struct ListIterator {
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
    
    PNode _pNode; // 封装的节点指针
};

模板参数解析：

T：节点数据类型
Ref：引用类型（T&或const T&）
Ptr：指针类型（T或const T）

2.2 核心功能函数

2.2.1 访问操作符

代码语言：javascript

AI代码解释

Ref operator*() { return _pNode->_val; }   // 解引用获取值
Ptr operator->() { return &_pNode->_val; } // 访问成员指针

2.2.2 迭代器移动

代码语言：javascript

AI代码解释

// 前置++
Self& operator++() {
    _pNode = _pNode->_pNext;
    return *this;
}

// 后置++
Self operator++(int) {
    Self tmp(_pNode);
    _pNode = _pNode->_pNext;
    return tmp;
}

// 前置--
Self& operator--() {
    _pNode = _pNode->_pPre;
    return *this;
}

2.2.3 比较操作符

代码语言：javascript

AI代码解释

bool operator!=(const Self& s) { 
    return _pNode != s._pNode; 
}

bool operator==(const Self& s) { 
    return _pNode == s._pNode; 
}

2.3 设计要点

行为模拟：通过运算符重载模拟指针行为
泛型支持：同一模板支持普通/常量迭代器
位置封装：隐藏节点指针实现细节

三、链表类：list

3.1 核心成员与类型定义

代码语言：javascript

AI代码解释

template<class T>
class list {
    typedef ListNode<T> Node;
    typedef Node* PNode;
    
    size_t _size;    // 元素计数器
    PNode _pHead;    // 哨兵头节点
};

3.2 构造与析构函数

3.2.1 头节点创建

代码语言：javascript

AI代码解释

void CreateHead() {
    _pHead = new Node; // 创建头节点
    _pHead->_pNext = _pHead; // 自环结构
    _pHead->_pPre = _pHead;
    _size = 0;
}

哨兵节点作用：统一空/非空链表操作，简化边界处理

3.2.2 构造函数组

代码语言：javascript

AI代码解释

list() { CreateHead(); } // 默认构造

// 填充构造
list(int n, const T& value = T()) {
    CreateHead();
    for(int i=0; i<n; ++i) 
        push_back(value);
}

// 拷贝构造
list(const list<T>& lt) {
    CreateHead();
    for(auto e : lt) push_back(e);
}

3.2.3 赋值与析构

代码语言：javascript

AI代码解释

// 拷贝交换赋值
list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

// 析构函数
~list() {
    clear();        // 清空元素
    delete _pHead;  // 释放头节点
    _pHead = nullptr;
}

3.3 迭代器访问接口

代码语言：javascript

AI代码解释

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

iterator begin() { return _pHead->_pNext; } // 首元素
iterator end() { return _pHead; }           // 尾后位置

const_iterator begin() const { 
    return const_iterator(_pHead->_pNext); 
}

3.4 容量操作

代码语言：javascript

AI代码解释

size_t size() const { return _size; }  // 元素计数
bool empty() const { return 0 == _size; } // 判空

3.5 关键操作函数

3.5.1 元素插入

代码语言：javascript

AI代码解释

void insert(iterator pos, const T& val) {
    PNode cur = pos._pNode;
    PNode prev = cur->_pPre;
    
    PNode newNode = new Node(val); // 创建新节点
    
    // 调整四向指针
    newNode->_pNext = cur;
    newNode->_pPre = prev;
    prev->_pNext = newNode;
    cur->_pPre = newNode;
    
    _size++; // 更新计数
}

3.5.2 元素删除

代码语言：javascript

AI代码解释

iterator erase(iterator pos) {
    PNode cur = pos._pNode;
    PNode prev = cur->_pPre;
    PNode next = cur->_pNext;
    
    // 跳过当前节点
    prev->_pNext = next;
    next->_pPre = prev;
    
    delete cur;  // 释放节点
    _size--;     // 更新计数
    
    return iterator(next); // 返回下一位置
}

3.5.3 清空操作

代码语言：javascript

AI代码解释

void clear() {
    iterator it = begin();
    while(it != end()) {
        it = erase(it); // 迭代删除
    }
}

3.6 复合操作接口

代码语言：javascript

AI代码解释

// 尾端操作
void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }

// 首端操作
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { erase(begin()); }

// 高效交换
void swap(list<T>& lt) {
    std::swap(_pHead, lt._pHead);
    std::swap(_size, lt._size);
}