今天的作业中有链表相关的题目，所以就顺手写了一个双向链表。在这里记录一下我写的链表吧。

(没什么好说的直接上代码吧)

代码实现

#include <iostream>

struct Node
{
    int value;

    Node* previous;
    Node* next;

    Node() :value(0), previous(nullptr), next(nullptr) {    }
};

class MyList
{
private:
    size_t SIZE;
    Node* head;
    Node* tail;

public:
    /*构造、析构*/
    MyList();
    ~MyList();

    /*插入、删除*/
    void insert(Node* node, int data);//在结点node后插入数据data
    void insert_prev(Node* node, int data);//在结点node前插入数据data
    void push_back(int data);//在最后加入节点
    Node* erase(Node* node);//删除node结点
    void pop_back();//删除最后一个节点

    /*查找*/
    Node* find(int data);//查找链表中数据为data的结点
    Node* search(int ith);//查找链表中第ith个结点

    /*链表信息*/
    int size() { return SIZE; }
    bool empty() { return SIZE == 0; }
    Node* begin() { return head; }
    Node* end() { return tail; }

    /*其他*/
    void display();
    void clear();
};

/*****************************************************************
Function:MyList
Description：构造函数，主要是初始化size、实例化头结点、初始化
             头指针head和尾指针tail。
*****************************************************************/

inline MyList::MyList()
{
    SIZE = 0;
    head = new Node();
    tail = head;
}

/*****************************************************************
Function:~MyList
Description：析构函数，主要是释放链表的空间。
*****************************************************************/

inline MyList::~MyList()
{
    while (SIZE > 0)
        erase(tail);
    
    delete head;
}

/*****************************************************************
Function:insert
Description：在node节点后插入值data。
*****************************************************************/

inline void MyList::insert(Node* node, int data)
{
    if (node == nullptr)
        return;

    Node* tmp = new Node();
    tmp->value = data;

    if (node->next != nullptr)
    {//如果node不为末节点就修改node后一个节点
        tmp->next = node->next;
        node->next->previous = tmp;
    }

    //处理node和tmp的关系
    node->next = tmp;
    tmp->previous = node;

    //如果node是末节点，则将tail修改为tmp
    if (node == tail)
        tail = tmp;

    SIZE++;

    return;
}

/*****************************************************************
Function:insert_prev
Description：在node节点前插入值data。
*****************************************************************/

inline void MyList::insert_prev(Node* node, int data)
{
    if (node == nullptr || node == head)
        return;

    Node* tmp = new Node();
    tmp->value = data;

    if (node->previous != nullptr)
    {//如果node不为头节点就修改node前一个节点
        tmp->previous = node->previous;
        node->previous->next = tmp;
    }

    //处理node和tmp的关系
    node->previous = tmp;
    tmp->next = node;

    SIZE++;

    return;
}

/*****************************************************************
Function:push_back
Description：在链表最后面插入一个节点。
*****************************************************************/

inline void MyList::push_back(int data)
{
    insert(tail, data);

    return;
}

/*****************************************************************
Function:erase
Description：从链表中删除node节点，返回下一节点的指针。
*****************************************************************/

inline Node* MyList::erase(Node* node)
{
    if (node == nullptr)
        return tail;

    Node* tmp = node->next;

    //分三种情况，node为head，node为tail，以及node在中间
    if (node == tail)
    {
        node->previous->next = nullptr;
        tail = node->previous;
    }
    else
    {
        node->previous->next = node->next;
        node->next->previous = node->previous;
    }

    //调整完node前后节点的关系即可删除node节点
    delete node;

    SIZE--;

    return tmp;
}

/*****************************************************************
Function:puop_back
Description：删除链表最后一个节点。
*****************************************************************/

inline void MyList::pop_back()
{
    if (SIZE == 0)
        return;

    erase(tail);

    return;
}

/*****************************************************************
Function:find
Description：遍历查找值为data的节点。
*****************************************************************/

inline Node* MyList::find(int data)
{
    Node* tmp = head->next;

    while (tmp != nullptr)
    {
        if (tmp->value == data)
            return tmp;

        tmp = tmp->next;
    }

    return nullptr;
}

/*****************************************************************
Function:search
Description：遍历查找第ith个节点。
*****************************************************************/

inline Node* MyList::search(int ith)
{
    if (ith > SIZE || ith < 1)
        return nullptr;

    Node* tmp = head;

    for (int i = 0; i < ith; i++)
        tmp = tmp->next;

    return tmp;
}

/*****************************************************************
Function:display
Description：遍历输出链表。
*****************************************************************/

inline void MyList::display()
{
    Node* tmp = head->next;

    while (tmp != nullptr)
    {
        std::cout << tmp->value << " ";
        tmp = tmp->next;
    }

    return;
}

/*****************************************************************
Function:clear
Description：清空链表。
*****************************************************************/

inline void MyList::clear()
{
    while (SIZE > 0)
        erase(tail);

    return;
}

我简单地测试了一下似乎没什么问题。单向链表后面再补吧。

随便写写

在写双向链表的时候我遇到了一个error LNK2005，我把所有的函数都加上 inline 修饰词后就没事了。猜测可能是我写在两个cpp文件导致的。具体原因找到在写下来吧。(之前写模板类好像没出过这个问题)

这个错误似乎是重复定义了一些变量。我把函数声明和定义放在 .h 文件里面就不会了。