C++数据结构——单链表

版本一(之前写的，用了头、尾两个指针，不常规)：

#include 
using namespace std;


template
struct Node
{
    T data;
    Node* next;

    Node()
    {
        next = nullptr;
    }
    explicit Node(T item, Node* ptr = nullptr)
    {
        data = item;
        next = ptr;
    }
};


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

protected:
    int count;
    Node* head;
    Node* back;
    Node* set_position(int position)const;
};


template
LinkList::LinkList()  //构造函数
{
    count = 0;
    head = back = nullptr;
}


template
LinkList::~LinkList()  //析构函数
{
    Node* p = head;
    while (p != nullptr)
    {
        head = head->next;
        delete p;
        p = head;
    }
    back = nullptr;
    count = 0;
}


template
void LinkList::clear() {
    Node* p = head;
    while (p != nullptr)
    {
        head = head->next;
        delete p;
        p = head;
    }
    back = nullptr;
    count = 0;
}


template 
LinkList::LinkList(const LinkList& item)  //拷贝构造函数
{
    Node* original_node = item.head;
    if (original_node == nullptr)
    {
        head = nullptr;
    }
    else
    {
        head = back = new Node(original_node->data);
        while (original_node->next != nullptr)
        {
            original_node = original_node->next;
            back->next = new Node(original_node->data);
            back = back->next;
        }
    }
    count = item.count;
}


template 
LinkList& LinkList::operator=(const LinkList& item)  //重载赋值运算符
{
    this->clear();
    if (nullptr == item.front) {
        head = back = nullptr;
        count = 0;
    }
    else {
        Node* original_front = item.front;
        head = back = new Node(original_front->entry);
        while (original_front->next != nullptr) {
            original_front = original_front->next;
            back->next = new Node(original_front->entry);
            back = back->next;
        }
        count = item.count;
    }
    return *this;
}



template
int LinkList::size()const
{
    return count;
}


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


template
Node* LinkList::set_position(int position)const  //找到指定位置的元素
{
    Node* target = head;
    for(int i = 0; i < position; ++i){
        target = target ->next;
    }
    return target;
}


template
void LinkList::insert(int position, const T& temp)  //在指定位置插入元素
{

    auto following = new Node;
    auto previous = new Node;
    if (position < 0 || position > count)
    {
        throw"Range Error";
    }
    if (position > 0)
    {
        previous = set_position(position - 1);
        following = previous->next;
    }
    else  //position = 0
    {
        following = head;
    }
    auto new_node = new Node(temp, following);
    if (new_node == nullptr)
    {
        throw"Overflow";
    }
    if (position == 0)
    {
        head = new_node;
        count++;
    }
    else
    {
        previous->next = new_node;
        count++;
    }
}


template
void LinkList::remove(int position)  //删除指定位置的元素
{
    if (empty())
    {
        throw"Overflow";
    }
    if (position < 0 || position > count - 1)
    {
        throw"Range Error";
    }
    if (position > 0)
    {
        Node* previous = set_position(position - 1);
        Node* temp = previous->next;
        previous->next = temp->next;
        temp = nullptr;
        delete temp;
        count--;
    }
    else  //position = 0
    {
        if (count == 1){
            Node* temp = head;
            head = back = nullptr;
            temp = nullptr;
            delete temp;
        }
        else{
            Node* temp = head;
            head = head->next;
            temp = nullptr;
            delete temp;
        }
        count--;
    }
}


template
void LinkList::replace(int position, const T& temp)  //替换指定位置的元素
{
    if (empty())
    {
        throw"Overflow";
    }
    if (position < 0 || position > count - 1)
    {
        throw"Range Error";
    }
    else
    {
        Node* item = set_position(position);
        item->data = temp;
    }
}


template
void LinkList::traverse()  //遍历链表
{
    Node* ptr = head;
    while (ptr != nullptr)
    {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
    cout << endl;
}


template
T LinkList::get(int position) {
    if (position < 0 || position > count - 1){
        throw"Range Error";
    }
    else{
        Node* temp = set_position(position);
        return temp->data;
    }
}


int main()
{
    LinkListtemp;
    for (int i = 0; i < 10; i++)
    {
        temp.insert(0, i);
    }
    cout << temp.size() << endl;
    temp.traverse();
    temp.remove(1);
    cout << temp.size() << endl;
    temp.replace(1, 100);
    temp.traverse();


    system("pause");
    return 0;
}

版本二（常规）：

#include
#include
using namespace std;


template
struct Node{
    T data;
    Node* next;

    Node(){
        this->next = nullptr;
    }

    explicit Node(T content, Node* nd = nullptr){
        this->data = content;
        this->next = nd;
    }
};


template
class LinkedList{
    Node* top;
    int count;

public:
    LinkedList();   //  构造函数
    LinkedList(const LinkedList& item);  //  拷贝构造函数
    ~LinkedList();  //  析构函数
    void Insert(T temp, int pos);   //  插入
    void Delete(int pos);   //  删除
    void Update(T temp, int pos);   //  更新
    T getEle(int pos);  //  获取链表指定位置的内容
    int getPos(T temp); //  获取指定内容在链表的下标索引
    void clear();   //  清空链表
    bool isEmpty()const;    //  判空
    int size()const;    //  返回链表长度
    void print();   //  输出链表内容
};


template
LinkedList::LinkedList(){
    top = nullptr;
    count = 0;
}


template
LinkedList::LinkedList(const LinkedList& item){
    Node* original_node = item.top;
    Node* copy_node;
    if (original_node == nullptr){
        this->top = nullptr;
    }
    else {
        this->top = copy_node = new Node(original_node->data);
        while (original_node->next){
            original_node = original_node->next;
            copy_node->next = new Node(original_node->data);
            copy_node = copy_node->next;
        }
    }
    this->count = item.count;
}

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

template
void LinkedList::Insert(T temp, int pos) {
    //  从1号位置开始插入
    if (pos > 0 && pos <= this->count){
        Node* p = this->top;
        for (int i = 0; i < pos - 1; ++i) {
            p = p->next;
        }
        Node* append = new Node(temp);
        append->next = p->next;
        p->next = append;
        this->count++;
    }
    //  插在链表头部
    else if(pos == 0){
        Node* append = new Node(temp, this->top);
        this->top = append;
        this->count++;
    }
    //  非法
    else{
        cout << "插入位置不合法" << endl;
    }
}


template
void LinkedList::Delete(int pos) {
    if (pos > 0 && pos < this->count){
        Node* p = this->top;
        for (int i = 0; i < pos - 1; ++i) {
            p = p->next;
        }
        Node* toDelete = p->next;
        p->next = toDelete->next;
        delete toDelete;
        this->count--;
    }
    else if (pos == 0){
        Node* p = this->top;
        this->top = this->top->next;
        delete p;
        this->count--;
    }
    else{
        cout << "删除位置不合法" << endl;
    }
}


template
void LinkedList::Update(T temp, int pos) {
    if (pos >= 0 && pos < this->count){
        Node* p = this->top;
        for (int i = 0; i < pos; ++i) {
            p = p->next;
        }
        p->data = temp;
    }
    else{
        cout << "修改位置不合法" << endl;
    }
}


template
T LinkedList::getEle(int pos) {
    if (pos >= 0 && pos < this->count){
        Node* p = this->top;
        for (int i = 0; i < pos; ++i) {
            p = p->next;
        }
        return p->data;
    }
    else{
        cout << "查找位置不合法" << endl;
    }
}


template
int LinkedList::getPos(T temp) {
    Node* p = this->top;
    for (int i = 0; i < this->count; ++i) {
        if (p->data == temp){
            return i;
        }
        p = p->next;
    }
    return -1;  //  表明未找到目标值
}


template
void LinkedList::clear() {
    if (count == 0){
        cout << "链表已空" << endl;
    }
    else {
        int flag = this->count;
        for (int i = 0; i < flag; ++i) {
            Node* p = this->top;
            this->top = this->top->next;
            delete p;
            count--;
        }
    }
}


template
bool LinkedList::isEmpty()const {
    return count == 0;
}


template
void LinkedList::print() {
    Node* p = this->top;
    for (int i = 0; i < this->count; ++i) {
        cout << p->data << "t";
        p = p->next;
    }
}


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


int main() {
    LinkedList linklist;
    for (int i = 0; i < 10; ++i) {
        linklist.Insert(pow(i, 2), i);
    }
    linklist.print();
    cout << endl;

    linklist.Delete(7);
    linklist.print();
    cout << endl;

    linklist.Update(100, 1);
    linklist.print();
    cout << endl;

    int target = linklist.getEle(5);
    cout << "5号位置的元素为：" << target << endl;

    int pos = linklist.getPos(100);
    cout << "100在链表中的下标索引为：" << pos << endl;

    linklist.clear();
    cout << "链表的长度为：" << linklist.size() << endl;


    return 0;

}