C++ 单向链表手动实现（课后作业版）

单向链表，并实现增删查改等功能

首先定义节点类，类成员包含当前节点的值和下一个节点的地址

/node definition
template <typename T>
class Node {
public:
    T value;
    Node* next;
 
    Node() {}
    Node(const T& value) {
        this->value = value;
        next = nullptr;
    }
    Node(const T& value, const Node& next) {
        this->value = value;
        this->next = next;
    }
};

然后是链表类的定义，主要包含了增删查改等功能

//linklist definition
template <typename T>
class LinkList {
public:
    Node* headnode;
 
    LinkList();
    LinkList(const T* arr, int len);  //array initial
    LinkList(const LinkList& link);
    ~LinkList();
    LinkList& push_back(T n);
    LinkList& push_front(T n);
    LinkList& insert(int pos, int n, T* arr);
    LinkList& pop_front();
    LinkList& pop_back();
    LinkList& remove(int pos, int num);
    LinkList& reverse();
    T& operator[](int n);
    T& at(int n);
    LinkList& replace(int pos, int n, T* arr);
    int getLen() {return len;}
    void clear() {this->~LinkList();}
    void display();
private:
    int len = 0;
    Node* getNode(int n);
 
};

各个函数解释：

LinkList();      默认构造函数

LinkList(const T* arr, int len);      一般构造函数

LinkList(const LinkList& link)           拷贝构造函数

~LinkList();     析构函数

LinkList& push_back(T n);    在尾部添加一个元素

LinkList& push_front(T n);     在头部添加一个元素

LinkList& insert(int pos, int n, T* arr);   在pos处插入n个元素

LinkList& pop_front();    删除第一个节点

LinkList& pop_back();    删除最后一个节点

LinkList& remove(int pos, int num);     删除pos开始的num个元素

LinkList& reverse();     反转链表

T& operator[](int n);     重载[ ]运算符，返回第n个节点的值

T& at(int n);                 与[ ]一样，只不过会检查索引是否越界

LinkList& replace(int pos, int n, T* arr);    替换n个节点

int getLen() {return len;}     返回长度，因为len是private

void clear() {this->~LinkList();}    清除链表

void display();    显示链表所有元素

Node* getNode(int n);     返回第n个节点的指针，是private函数，在其他函数中经常用到

最后是各个成员函数的定义：

#include 
using namespace std;
 
//node definition
template <typename T>
class Node {
public:
    T value;
    Node* next;
 
    Node() {}
    Node(const T& value) {
        this->value = value;
        next = nullptr;
    }
    Node(const T& value, const Node& next) {
        this->value = value;
        this->next = next;
    }
};
 
//linklist definition
template <typename T>
class LinkList {
public:
    Node* headnode;
 
    LinkList();
    LinkList(const T* arr, int len);  //array initial
    LinkList(const LinkList& link);
    ~LinkList();
    LinkList& push_back(T n);
    LinkList& push_front(T n);
    LinkList& insert(int pos, int n, T* arr);
    LinkList& pop_front();
    LinkList& pop_back();
    LinkList& remove(int pos, int num);
    LinkList& reverse();
    T& operator[](int n);
    T& at(int n);
    LinkList& replace(int pos, int n, T* arr);
    int getLen() {return len;}
    void clear() {this->~LinkList();}
    void display();
private:
    int len = 0;
    Node* getNode(int n);
 
};
 
//default constructor
template <typename T>
LinkList::LinkList() {
    headnode = nullptr;
    len = 0;
}
 
//normal constructor
template <typename T>
LinkList::LinkList(const T* arr, int len) {
    Node* temp = nullptr;
    Node* node = nullptr;
    if ( len < 0 ) {
        cout << "[error]: illegal length of LinkList" << endl;
        exit(0);
    }
    for ( int i = len-1; i >= 0; i-- ) {
        node = new Node(i);
        node->value = *(arr+i);
        node->next = temp;
        temp = node;
        node = nullptr;
    }
    headnode = temp;
    this->len = len;
}
 
//copy constructor
template <typename T>
LinkList::LinkList(const LinkList& link) {
    this->len = link.getLen();
    this->headnode = link.headnode;
    link.headnode = nullptr;
}
 
//deconstructor
template <typename T>
LinkList::~LinkList() {
    this->len = 0;
    Node* temp = headnode;
    while ( headnode ) {
        temp = headnode;
        headnode = headnode->next;
        delete temp;
        temp = nullptr;
    }
}
 
//display all elements in Linklist
template <typename T>
void LinkList::display() {
    if ( len == 0 ) {
        cout << "[warning]: can not disply empty linkedlist" << endl;
        return;
    }
    Node *node = headnode;
    for ( int i = 0; i < len; i++ ) {
        cout << node->value << " ";
        node = node->next;
    }
    cout << endl;
}
 
//add one node at the last position
template <typename T>
LinkList& LinkList::push_back(T n) {
    Node *node = this->getNode(len-1);
 
    if ( node->next == nullptr ) {
        Node *temp = new Node(n);
        node->next = temp;
        this->len++;
    }
    return *this;
}
 
//add one node at the first position
template <typename T>
LinkList& LinkList::push_front(T n) {
    Node* node_new = new Node(n);
    node_new->next = headnode;
    headnode = node_new;
    this->len++;
    return *this;
}
 
//insert elements to LinkList
template <typename T>
LinkList& LinkList::insert(int pos, int n, T* arr) {
    if ( pos > len-1 || len < 0 ) {
        cout << "[error]: illegal insert position, please check again" << endl;
        exit(0);
    }
    if ( pos == 0 ) {
        for ( int i = 0; i < n; i++ )
            this->push_front(arr[n-1-i]);
        return *this;
    }
    Node* node_N = getNode(pos-1);  //前半部分
    Node* temp = node_N->next;    //后半部分
    Node* node_new = nullptr;     //新增加的
    for ( int i = 0; i < n; i++ ) {
        node_new = new Node (arr[n-1-i]);
        node_new->next = temp;
        temp = node_new;
        node_new = nullptr;
    }
    node_N->next = temp;
    this->len += n;
    return *this;
}
 
//delete the first element
template <typename T>
LinkList& LinkList::pop_front() {
    if ( this->len == 0 ) {
        cout << "[error]: LinkList don't has any element" << endl;
        exit(0);
    }
    Node* temp = headnode;
    headnode = getNode(1);
    delete temp;
    this->len--;
    return *this;
}
 
//delete the last element
template <typename T>
LinkList& LinkList::pop_back() {
    if ( this->len == 0 ) {
        cout << "[error]: LinkList don't has any element" << endl;
        exit(0);
    }
    Node* temp = getNode(len-2);
    delete temp->next;
    temp->next = nullptr;
    this->len--;
    return *this;
}
 
//get the last node pointer
template <typename T>
Node* LinkList::getNode(int n) {
    if ( n > len-1 || n < 0) {
        cout << "[error]: index out of range" <
    }
    Node *node = headnode;
    for( int i = 0; i < n; i++ ) {
        node = node->next;
    }
    return node;
}
 
//remove n elements
template <typename T>
LinkList& LinkList::remove(int pos, int num) {
    if ( pos > len-1 || len < 0 ) {
        cout << "[error]: illegal remove position, please check again" << endl;
        exit(0);
    } else if ( pos + num > len) {
        cout << "[error]: remove index out of range" << endl;
        exit(0);
    }
    if ( pos == 0 ) {
        for ( int i = 0; i < num; i++ )
            this->pop_front();
        return *this;
    }
    Node* node_N = getNode(pos-1);
    Node* node_N_num = getNode(pos+num);
    Node* temp = getNode(pos);
    while ( 1 ) {
        Node* node = temp;
        temp = temp->next;
        delete node;
        if ( temp == node_N_num ) {
            break;
        }
    }
    node_N->next = node_N_num;
    this->len -= num;
    return *this;
}
 
//reverse linklist
template <typename T>
LinkList& LinkList::reverse() {
    Node* front = nullptr;
    Node* mid   = headnode;
    Node* back  = headnode->next;
    while ( back ) {
        mid->next = front;
        front = mid;
        mid = back;
        back = back->next;
    }
    mid->next = front;
    front = nullptr;
    headnode = mid;
 
    return *this;
}
 
template <typename T>
T& LinkList::operator[](int n) {
    if ( n > len-1 || n < 0 ) {
        cout << "[error]: index out of range" << endl;
        exit(0);
    }
    return this->getNode(n)->value;
}
 
template <typename T>
LinkList& LinkList::replace(int pos, int n, T* arr) {
    if ( pos > len-1 || len < 0 ) {
        cout << "[error]: illegal remove position, please check again" << endl;
        exit(0);
    } else if ( pos + n > len) {
        cout << "[error]: remove index out of range" << endl;
        exit(0);
    }
    Node* temp = nullptr;
    if ( pos == 0 )
        temp = headnode;
    else
        temp = this->getNode(pos-1);
    for ( int i = 0; i < n; i++ ) {
        temp->value = arr[i];
        temp = temp->next;
    }
    return *this;
}
 
int main(){
    int arr[]{1,2,4,5,0};
    LinkList<int> link(arr, sizeof(arr)/sizeof(int));
    cout << "LinkLint init with arr: " <
    link.display();
    cout << "push_back:" << endl;
    link.push_back(34);
    link.display();
    cout << "push_front:" << endl;
    link.push_front(10);
    link.display();
    cout << "insert:" << endl;
    link.insert(0,4,arr);
    link.display();
    cout << "pop_front:" << endl;
    link.pop_front();
    link.display();
    cout << "pop_back:" << endl;
    link.pop_back();
    link.display();
    cout << "remove:" << endl;
    link.remove(2,3);
    link.display();
    cout << "[] operator:" << endl;
    cout << link[2] << endl;
    cout << "replace:" << endl;
    int a[] = {6,5,2};
    link.replace(2, sizeof(a)/sizeof(int), a);
    link.display();
    cout << "linklist reserve:" << endl;
    link.reverse();
    link.display();
    cout << "clear:" << endl;
    link.clear();
    cout << "len=" << link.getLen() << endl;
    link.display();
}