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

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

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

/node definition

template <typename T>

class Node {

public:

    T value;

    Node<T>* next;

    Node() {}

    Node(const T& value) {

        this->value = value;

        next = nullptr;

    }

    Node(const T& value, const Node<T>& next) {

        this->value = value;

        this->next = next;

    }

};

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

//linklist definition

template <typename T>

class LinkList {

public:

    Node<T>* headnode;

    LinkList();

    LinkList(const T* arr, int len);  //array initial

    LinkList(const LinkList<T>& link);

    ~LinkList();

    LinkList<T>& push_back(T n);

    LinkList<T>& push_front(T n);

    LinkList<T>& insert(int pos, int n, T* arr);

    LinkList<T>& pop_front();

    LinkList<T>& pop_back();

    LinkList<T>& remove(int pos, int num);

    LinkList<T>& reverse();

    T& operator[](int n);

    T& at(int n);

    LinkList<T>& replace(int pos, int n, T* arr);

    int getLen() {return len;}

    void clear() {this->~LinkList();}

    void display();

private:

    int len = 0;

    Node<T>* getNode(int n);

};

各个函数解释：

LinkList(); 默认构造函数

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

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

~LinkList(); 析构函数

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

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

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

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

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

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

LinkList<T>& reverse(); 反转链表

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

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

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

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

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

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

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

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

#include <iostream>

using namespace std;

//node definition

template <typename T>

class Node {

public:

    T value;

    Node<T>* next;

    Node() {}

    Node(const T& value) {

        this->value = value;

        next = nullptr;

    }

    Node(const T& value, const Node<T>& next) {

        this->value = value;

        this->next = next;

    }

};

//linklist definition

template <typename T>

class LinkList {

public:

    Node<T>* headnode;

    LinkList();

    LinkList(const T* arr, int len);  //array initial

    LinkList(const LinkList<T>& link);

    ~LinkList();

    LinkList<T>& push_back(T n);

    LinkList<T>& push_front(T n);

    LinkList<T>& insert(int pos, int n, T* arr);

    LinkList<T>& pop_front();

    LinkList<T>& pop_back();

    LinkList<T>& remove(int pos, int num);

    LinkList<T>& reverse();

    T& operator[](int n);

    T& at(int n);

    LinkList<T>& replace(int pos, int n, T* arr);

    int getLen() {return len;}

    void clear() {this->~LinkList();}

    void display();

private:

    int len = 0;

    Node<T>* getNode(int n);

};

//default constructor

template <typename T>

LinkList<T>::LinkList() {

    headnode = nullptr;

    len = 0;

}

//normal constructor

template <typename T>

LinkList<T>::LinkList(const T* arr, int len) {

    Node<T>* temp = nullptr;

    Node<T>* 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<T>(i);

        node->value = *(arr+i);

        node->next = temp;

        temp = node;

        node = nullptr;

    }

    headnode = temp;

    this->len = len;

}

//copy constructor

template <typename T>

LinkList<T>::LinkList(const LinkList<T>& link) {

    this->len = link.getLen();

    this->headnode = link.headnode;

    link.headnode = nullptr;

}

//deconstructor

template <typename T>

LinkList<T>::~LinkList() {

    this->len = 0;

    Node<T>* temp = headnode;

    while ( headnode ) {

        temp = headnode;

        headnode = headnode->next;

        delete temp;

        temp = nullptr;

    }

}

//display all elements in Linklist<T>

template <typename T>

void LinkList<T>::display() {

    if ( len == 0 ) {

        cout << "[warning]: can not disply empty linkedlist" << endl;

        return;

    }

    Node<T> *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<T>& LinkList<T>::push_back(T n) {

    Node<T> *node = this->getNode(len-1);

    if ( node->next == nullptr ) {

        Node<T> *temp = new Node<T>(n);

        node->next = temp;

        this->len++;

    }

    return *this;

}

//add one node at the first position

template <typename T>

LinkList<T>& LinkList<T>::push_front(T n) {

    Node<T>* node_new = new Node<T>(n);

    node_new->next = headnode;

    headnode = node_new;

    this->len++;

    return *this;

}

//insert elements to LinkList

template <typename T>

LinkList<T>& LinkList<T>::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<T>* node_N = getNode(pos-1);  //前半部分

    Node<T>* temp = node_N->next;    //后半部分

    Node<T>* node_new = nullptr;     //新增加的

    for ( int i = 0; i < n; i++ ) {

        node_new = new Node<T> (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<T>& LinkList<T>::pop_front() {

    if ( this->len == 0 ) {

        cout << "[error]: LinkList don't has any element" << endl;

        exit(0);

    }

    Node<T>* temp = headnode;

    headnode = getNode(1);

    delete temp;

    this->len--;

    return *this;

}

//delete the last element

template <typename T>

LinkList<T>& LinkList<T>::pop_back() {

    if ( this->len == 0 ) {

        cout << "[error]: LinkList don't has any element" << endl;

        exit(0);

    }

    Node<T>* temp = getNode(len-2);

    delete temp->next;

    temp->next = nullptr;

    this->len--;

    return *this;

}

//get the last node pointer

template <typename T>

Node<T>* LinkList<T>::getNode(int n) {

    if ( n > len-1 || n < 0) {

        cout << "[error]: index out of range" <<endl;

    }

    Node<T> *node = headnode;

    for( int i = 0; i < n; i++ ) {

        node = node->next;

    }

    return node;

}

//remove n elements

template <typename T>

LinkList<T>& LinkList<T>::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<T>* node_N = getNode(pos-1);

    Node<T>* node_N_num = getNode(pos+num);

    Node<T>* temp = getNode(pos);

    while ( 1 ) {

        Node<T>* 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<T>& LinkList<T>::reverse() {

    Node<T>* front = nullptr;

    Node<T>* mid   = headnode;

    Node<T>* 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<T>::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<T>& LinkList<T>::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<T>* 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: " <<endl;

    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();

}

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

C++ 单向链表手动实现（课后 作业版）的相关教程结束。

相关推荐

一种flink 作业提交失败的情况描述与原因排查

【算法训练营day4】LeetCode24. 两两交换链表中的结点 LeetCode19. 删除链表的倒数第N个结点 LeetCode面试题 02.07. 链表相交 LeetCode142. 环形链表II

使用C语言实现简单的通用的链表

OO第一次博客作业总结反思

2021-09-17：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？

《DL/T 976-2017 带电作业用工具、装置和设备预防性试验规程》中的样品名称及试验项目

2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。

LeeCode链表问题（一）