链表基础

在开始之前，我们先了解一下什么是链表：

• 链表是一种物理存储单元上非连续、非顺序的存储结构

• 双向链表的每个节点都包含指向前一个节点和后一个节点的指针

• 与数组相比，链表在插入和删除操作上更加高效

实现步骤

1. 节点结构

首先，我们需要定义链表的节点结构：

template<class T>
struct list_node {
    T _data;              // 存储的数据
    list_node<T>* _prev;  // 指向前一个节点
    list_node<T>* _next;  // 指向后一个节点

    list_node(const T& value = T())
        :_data(value),
        _prev(nullptr),
        _next(nullptr) 
    {}
};

这个节点结构包含三个成员：

• _data：存储的实际数据

• _prev：指向前一个节点的指针

• _next：指向后一个节点的指针

构造函数使用默认参数，可以创建带有默认值的节点。

2. 迭代器实现

迭代器是遍历容器的工具，对于链表来说尤为重要：

template<class T, class Ref, class Ptr>
struct list_iterator {
    typedef list_node<T> Node;
    typedef struct list_iterator < T, Ref, Ptr > Self;
    Node* _node;
    
    list_iterator(Node* node)
        :_node(node)
    {}
    
    // 解引用操作符，获取节点数据
    Ref operator*() {
        return _node->_data;
    }
    
    // 箭头操作符，获取节点数据的指针
    Ptr operator->() {
        return &_node->_data;
    }
    
    // 前置++
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }
    
    // 后置++
    Self operator++(int) {
        Self tmp = *this;
        _node = _node->_next;
        return tmp;
    }
    
    // 前置--
    Self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    
    // 后置--
    Self operator--(int) {
        Self tmp = *this;
        _node = _node->_prev;
        return tmp;
    }
    
    // 比较操作符
    bool operator!=(const Self& it) const {
        return _node != it._node;
    }
    
    bool operator==(const Self& it) const {
        return _node == it._node;
    }
};

这里使用了模板参数 Ref 和 Ptr 来区分普通迭代器和常量迭代器。

3. 链表主体

现在让我们来看链表的主要实现：

template<class T>
class list {
    typedef list_node<T> Node;
public:
    // 定义迭代器类型
    typedef list_iterator<T, T&, T*> iterator;
    typedef list_iterator < T, const T&, const T* > const_iterator;

private:
    Node* _head;   // 头节点指针
    size_t _size;  // 链表大小
};

迭代器相关方法

// 返回指向第一个元素的迭代器
iterator begin() {
    return iterator(_head->_next);
}

// 返回指向末尾（头节点）的迭代器
iterator end() {
    return iterator(_head);
}

// 常量版本
const_iterator begin() const {
    return const_iterator(_head->_next);
}

const_iterator end() const {
    return const_iterator(_head);
}

初始化方法

// 空初始化
void empty_init() {
    _head = new Node;
    _head->_prev = _head;
    _head->_next = _head;
    _size = 0;
}

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

这里创建了一个哨兵节点（头节点），它指向自己，形成一个空的循环链表。

拷贝构造和赋值

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

// 赋值操作符
list<T>& operator=(list<T> l) {
    swap(l);
    return *this;
}

void swap(list<T>& l) {
    std::swap(_head, l._head);
    std::swap(_size, l._size);
}

这里使用了"拷贝并交换"技术，这是一种安全且高效的实现方式。

析构函数

~list() {
    clear();
    delete _head;
}

// 清除所有元素
void clear() {
    iterator it = begin();
    while (it != end()) {
        it = erase(it);
    }
}

常用操作

头插和头删：

// 头插
void push_front(const T& x) {
    Node* newnode = new Node(x);
    Node* tmp = _head->_next;
    _head->_next = newnode;
    tmp->_prev = newnode;
    newnode->_prev = _head;
    newnode->_next = tmp;
    _size++;
}

// 头删
void pop_front() {
    assert(_size > 0);
    erase(begin());
}

尾插和尾删：

// 尾插
void push_back(const T& x) {
    Node* newnode = new Node(x);
    Node* tail = _head->_prev;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
    tail->_next = newnode;
    _size++;
}

// 尾删
void pop_back() {
    assert(_size > 0);
    erase(--end());
}

插入和删除：

// 在指定位置插入元素
iterator insert(iterator pos, const T& x) {
    Node* newnode = new Node(x);
    Node* tmp = pos._node->_prev;
    newnode->_prev = tmp;
    newnode->_next = pos._node;
    pos._node->_prev = newnode;
    tmp->_next = newnode;
    _size++;
    return iterator(newnode);
}

// 删除指定位置的元素
iterator erase(iterator pos) {
    assert(pos != end());
    Node* next = pos._node->_next;
    pos._node->_prev->_next = next;
    next->_prev = pos._node->_prev;
    delete pos._node;
    _size--;
    return iterator(next);
}

获取大小：

// 返回链表元素个数
size_t size() const {
    return _size;
}

使用示例

让我们看看如何使用这个 list 容器：

#include "My_list.h"
#include <iostream>

int main() {
    yzq::list<int> myList;
    
    // 添加元素
    myList.push_back(1);
    myList.push_back(2);
    myList.push_back(3);
    myList.push_front(0);
    
    // 遍历输出
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环
    for (const auto& val : myList) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    
    // 删除元素
    myList.pop_back();
    myList.pop_front();
    
    std::cout << "Size: " << myList.size() << std::endl;
    
    return 0;
}