C++数据结构——双端链表

主页有其他数据结构内容（持续更新中）

#include 
using namespace std;


template
struct Node
{
    T data;
    Node* next;  //  后继结点
    Node* prior; //  前驱结点

    Node()
    {
        next = nullptr;
        prior = nullptr;
    }
    explicit Node(T temp, Node* link_prior = nullptr, Node* link_next = nullptr)
    {
        data = temp;
        next = link_next;
        prior = link_prior;
    }
};


template
class DoubleLinkedList
{
    Node* head;
    int count;

public:
    DoubleLinkedList();
    ~DoubleLinkedList();
    int size()const;
    bool empty()const;  //判表空
    void traverse();  //遍历表
    void clear();  //清空表
    DoubleLinkedList(const DoubleLinkedList& item);  //拷贝构造函数
    DoubleLinkedList& operator=(const DoubleLinkedList& item);  //赋值运算符重载
    void insert(int position, const T& temp);  //在指定位置插入元素
    void remove(int position);  //删除指定位置的元素
    void update(int position, const T& temp);  //替换指定位置的元素
};


template
DoubleLinkedList::DoubleLinkedList() {
    this->head = nullptr;
    this->count = 0;
}


template
DoubleLinkedList::~DoubleLinkedList() {
    clear();
}


template
int DoubleLinkedList::size() const {
    return this->count;
}


template
bool DoubleLinkedList::empty() const {
    return count == 0;
}


template
void DoubleLinkedList::traverse() {
    Node* p = this->head;
    while (p){
        cout << p->data << "t";
        p = p->next;
    }
}


template
void DoubleLinkedList::clear() {
    while (this->head){
        Node* toDelete = this->head;
        this->head = this->head->next;
        delete toDelete;
    }
    this->count = 0;
}


template
DoubleLinkedList::DoubleLinkedList(const DoubleLinkedList &item) {
    Node* original_node = item.head;
    Node* copy_node;
    if (item.head == nullptr){
        this->head = nullptr;
        this->count = 0;
    }
    else{
        copy_node = this->head = new Node(item.head->data);
        while (original_node->next){
            original_node = original_node->next;
            Node* temp = new Node(original_node->data, copy_node, nullptr);
            copy_node->next = temp;
            copy_node = temp;
        }
        this->count = item.count;
    }
}


template
DoubleLinkedList &DoubleLinkedList::operator=(const DoubleLinkedList &item) {
    clear();
    Node* original_node = item.head;
    Node* copy_node;
    if (item.head == nullptr){
        this->head = nullptr;
        this->count = 0;
    }
    else{
        copy_node = this->head = new Node(item.head->data);
        while (original_node->next){
            original_node = original_node->next;
            Node temp = new Node(original_node->data, copy_node, nullptr);
            copy_node->next = temp;
            copy_node = copy_node->next;
        }
        this->count = item.count;
    }
    return *this;
}


template
void DoubleLinkedList::insert(int position, const T &temp) {
    if (position < 0 || position > this->count){
        cout << "插入位置非法" << endl;
    }
    else{
        if (!position){ //  插在头部(0号位置)
            if (!this->head){
                this->head = new Node(temp);
            }
            else{
                Node* toInsert = new Node(temp, nullptr, this->head);
                this->head->prior = toInsert;
                this->head = toInsert;
            }
        }
        else{
            Node* p = this->head;
            for (int i = 0; i < position - 1; ++i) {
                p = p->next;
            }
            Node* toInsert = new Node(temp, p, p->next);
            if (p->next){   //  不是插在尾部
                p->next->prior = toInsert;
            }
            p->next = toInsert;
        }
        this->count++;
    }
}


template
void DoubleLinkedList::remove(int position) {
    if (this->empty()){
        cout << "当前链表已空，无法继续删除" << endl;
    }
    else{
        if (position < 0 || position > this->count - 1){
            cout << "删除位置非法" << endl;
        }
        else{
            if (!position){
                Node* toDelete = this->head;
                this->head = this->head->next;
                delete toDelete;
            }
            else {
                Node* p = this->head;
                for (int i = 0; i < position - 1; ++i) {
                    p = p->next;
                }
                Node* toDelete = p->next;
                p->next = toDelete->next;
                if (position != this->count - 1){
                    toDelete->next->prior = p;
                }
                delete toDelete;
            }
        }
        this->count--;
    }
}


template
void DoubleLinkedList::update(int position, const T &temp) {
    if (position < 0 || position > this->count - 1){
        cout << "修改位置非法" << endl;
    }
    else{
        Node* p = this->head;
        for (int i = 0; i < position; ++i) {
            p = p->next;
        }
        p->data = temp;
    }
}


int main(){
    DoubleLinkedList dll;
    for (int i = 0; i < 10; ++i) {
        dll.insert(i, i * i);
    }
    dll.traverse();
    cout << endl;

    dll.remove(0);
    dll.remove(8);
    dll.traverse();
    cout << endl;

    dll.update(0, 100);
    dll.update(7, 200);
    dll.traverse();
    cout << endl;

    DoubleLinkedList copy_1 = dll; //  测试赋值运算符
    cout << "copy_1的内容为：";
    copy_1.traverse();
    cout << endl;
    DoubleLinkedList copy_2 = DoubleLinkedList(dll);  //  测试拷贝构造函数
    cout << "copy_2的内容为：";
    copy_2.traverse();
    cout << endl;

    cout << "双端链表的长度为：" << dll.size() << endl;
    dll.clear();
    cout << "清除后，双端链表的长度为：" << dll.size() << endl;


    return 0;
}