C++链表类的封装详情介绍

C++中的链表是一种数据结构，它由一组节点组成，每个节点包含两个部分：一个存储数据的部分和一个指向下一个节点的指针。链表可以按照插入的顺序存储数据，因此它没有大小限制，也可以随时添加、删除和查询数据。在本文中，我们将介绍如何在C++中使用链表类来封装一个链表数据结构。

相关定义

节点类定义

为了构建链表，我们首先需要定义一个节点类，该类有两个成员变量：一个用于存储数据的数据成员，以及一个指向下一个节点的指针成员变量。同时，该类也应该提供公共的访问和更新成员函数来处理这些成员变量。

template<typename T>
class Node {
public:
    T data_;        //定义节点数据成员
    Node<T>* next_; //定义指向下一个节点的指针成员
public:
    Node() {} //默认构造函数
    Node(T d, Node<T>* n = nullptr) : data_(d), next_(n) {} //带参构造函数
    ~Node() {} //析构函数
};

链表类定义

首先，链表类需要一个定义节点的指针和一个记录链表大小的成员变量。此外，我们还需要提供一些基本操作，例如查找、插入和删除等成员函数。为了提高效率，在链表类的实现中使用头指针和尾指针来记录列表的开头和结尾部分。

在链表类定义中，我们需要注意以下几点：

链表类需要定义一个指向节点的指针作为列表的头指针；
定义一个指向节点的指针作为列表的尾指针；
定义一个整型变量保存列表的长度；
定义公共成员函数操作，如查找、插入和删除等。

template<typename T>
class LinkList {
private:
    Node<T>* head_; //指向节点的指针作为列表的头指针
    Node<T>* tail_; //指向节点的指针作为列表的尾指针
    int length_; //指向整型变量保存列表的长度
public:
    LinkList() : head_(nullptr), tail_(nullptr), length_(0) {}; //链表对象的构造函数
    ~LinkList(); //链表对象的析构函数
    bool empty(); //判断是否为空链表
    void clear(); //清空链表
    int length(); //链表长度
    bool get_element(int i, T& e); //获取指定索引位置的节点值
    int locate(const T& e); //查找值为e的节点
    bool insert(int i, const T& e); //在指定位置前插入值为e的节点
    bool remove(int i, T& e); //删除指定位置的节点
    void display(); //遍历输出链表
};

成员函数实现

析构函数

当链表对象被销毁时，需要逐个删除存储在链表中的所有节点。

template<typename T>
LinkList<T>::~LinkList() {
    clear();
}

判断链表是否为空

判断链表是否为空需要查看链表的长度，如果长度为0，则表示链表为空。

template<typename T>
bool LinkList<T>::empty() {
    return length_ == 0; //length_记录链表长度，为0则代表为空链表
}

清空链表

为了避免内存泄漏，链表在使用完后要及时清空。而清空链表就是从头至尾逐个删除链表中的节点。

template<typename T>
void LinkList<T>::clear() {
    Node<T>* p = head_;
    while (p) {
        head_ = p->next_;
        delete p;
        p = head_;
    }
    head_ = tail_ = nullptr;
    length_ = 0; //清空链表，length_为0
}

获取链表长度

由于每次添加或删除节点时，我们都会根据需要更新链表长度，所以可以直接返回长度值即可。

template<typename T>
int LinkList<T>::length() {
    return length_;
}

获取指定节点值

在链表中查找指定位置的节点并将值返回。如果索引超出链表长度，则返回false。

template<typename T>
bool LinkList<T>::get_element(int i, T& e) {
    if (i < 0 || i >= length_) {
        return false;
    }
    Node<T>* p = head_;
    int j = 0;
    while (p && j < i) {
        p = p->next_;
        ++j;
    }
    e = p->data_;
    return true;
}

查找指定值节点

在链表中查找指定值的节点。如果找到该节点，则返回它的位置，否则返回0。

template<typename T>
int LinkList<T>::locate(const T& e) {
    Node<T>* p = head_;
    int j = 0;
    while (p && p->data_ != e) {
        p = p->next_;
        j++;
    }
    if (!p) return 0;
    return j;
}

插入节点

在链表的任意位置插入一个新节点。如果索引超出链表长度，则返回false。

template<typename T>
bool LinkList<T>::insert(int i, const T& e) {
    if (i < 0 || i > length_) {
        return false;
    }
    Node<T>* new_node = new Node<T>(e);
    if (!new_node) {
        return false;
    }
    if (i == 0) {
        new_node->next_ = head_;
        head_ = new_node;
        if (!tail_) {
            tail_ = head_;
        }       
    } else {
        Node<T>* p = head_;
        int j = 0;
        while (p && j < i - 1) {
            p = p->next_;
            ++j;
        }
        new_node->next_ = p->next_;
        p->next_ = new_node;
        if (!new_node->next_) {
            tail_ = new_node;
        }
    }
    length_++;
    return true;
}

删除节点

在链表的任意位置删除一个节点。如果索引超出链表长度，则返回false。

template<typename T>
bool LinkList<T>::remove(int i, T& e) {
    if (i < 0 || i >= length_) {
        return false;
    }
    Node<T>* p = head_;
    if (i == 0) {
        e = head_->data_;
        head_ = head_->next_;
        if (!head_) {
            tail_ = nullptr;
        }       
    } else {
        int j = 0;
        while (p->next_ && j < i - 1) {
            p = p->next_;
            ++j;
        }
        e = p->next_->data_;
        p->next_ = p->next_->next_;
        if (!p->next_) {
            tail_ = p;
        }
    }
    length_--;
    return true;
}

遍历链表

遍历链表是指输出链表的所有节点，以便于查看链表内的元素数据。

template<typename T>
void LinkList<T>::display(){
    if(head_ == nullptr){
        std::cout<<"链表为空"<<std::endl;
    }else{
        Node<T>* p = head_;
        while(p!=nullptr){
            std::cout<<p->data_<<" ";
            p = p->next_;
        }
        std::cout << "\n";
    }
}

示例

示例1：插入、删除以及获取操作

下面的示例显示如何使用链表类封装一次插入、删除以及获取数据的操作。

#include<iostream>
#include"linklist.hpp"

int main(){
    LinkList<int> linklist;
    linklist.insert(0,1);
    std::cout<<"isEmpty: "<<linklist.empty()<<std::endl; //输出0
    linklist.insert(1,2);
    linklist.insert(2,3);
    linklist.display();
    int e = 0;
    linklist.remove(2,e);
    std::cout<<"remove element: "<<e<<std::endl; //输出3
    linklist.display();
    linklist.get_element(1,e);
    std::cout<<"get element: "<<e<<std::endl; //输出2
    linklist.display();

    return 0;
}

执行结果：

isEmpty: 0
1 2 3 
remove element: 3
1 2 
get element: 2
1 2

示例2：查找、长度以及清空操作

下面的示例显示如何使用链表类封装一次查找、长度以及清空的操作。

#include<iostream>
#include"linklist.hpp"

int main(){
    LinkList<int> linklist;
    linklist.insert(0,1);
    linklist.insert(1,2);
    linklist.insert(2,3);
    linklist.display();
    std::cout<<"length: "<<linklist.length()<<std::endl; //输出3
    int e = 0;
    int len = linklist.locate(2);
    std::cout<<"locate: "<<len<<std::endl; //输出2
    linklist.clear();
    std::cout<<"isEmpty: "<<linklist.empty()<<std::endl; //输出1

    return 0;
}