单链表的实现（cpp版本）

链表节点的定义

template <class T>
struct LinkNode //节点类
{
    T Data;         //节点的数据
    LinkNode *Next; //指向该节点的下一个节点的指针
    LinkNode() : Next(NULL)
    {
        cout << "please enter data: ";
        cin >> Data;
    }
    LinkNode(const T &d, LinkNode *p = NULL) : Data(d), Next(p) {}
    ~LinkNode() {}
};

链表实例化

template <class T>
SingleLinkedList<T>::SingleLinkedList(int len)
{
    LinkNode<T> *Cur;
    for (size_t i = 0; i < len; i++)
    {
        Cur = new LinkNode<T>();
        if (i == 0)
        {
            Head = Cur;
            Tail = Cur;
        }
        else
        {
            Tail->Next = Cur;
            Tail = Tail->Next;
        }
        ListSize++;
    }
}

删除链表的某一节点

template <class T>
void SingleLinkedList<T>::Delete(const T &Data)
{
    LinkNode<T> *Prev = this->Head;
    LinkNode<T> *Temp = nullptr;
    if (this->Head->Data == Data)
    {
        this->Head = Prev->Next;
        Prev->Next = nullptr;
        free(Prev);
        ListSize--;
    }

    while (Prev->Next != nullptr && Prev->Next->Data != Data)
    {
        Prev = Prev->Next;
    }
    if (Prev->Next != nullptr && Prev->Next != this->Tail)
    {
        Temp = Prev;
        Temp->Next = Prev->Next->Next;
        free(Prev->Next);
        ListSize--;
    }
    else
    {
        this->Tail = Prev;
        this->Tail->Next = nullptr;
        free(Prev->Next);
        ListSize--;
    }
}

删除整个链表

template <class T>
void SingleLinkedList<T>::DeleteList()
{
    LinkNode<T> *Temp, *DeleteTemp;
    DeleteTemp = this->Head;
    while (DeleteTemp != nullptr)
    {
        Temp = DeleteTemp->Next;
        free(DeleteTemp);
        DeleteTemp = Temp;
        ListSize--;
    }
    Head = nullptr;
    Tail = nullptr;
}

插入头节点

template <class T>
void SingleLinkedList<T>::InsertHead(const T &data)
{
    LinkNode<T> *temp = new LinkNode<T>(data);
    if (Head == nullptr)
    {
        Head = temp;
        Tail = temp;
    }
    else
    {
        temp->Next = Head;
        Head = temp;
    }
    // 局部变量不需要free，除非使用malloc申请时
    ListSize++;
}

插入到尾节点

template <class T>
void SingleLinkedList<T>::InsertTail(const T &data)
{
    LinkNode<T> *temp = new LinkNode<T>(data);
    if (Head == nullptr)
    {
        Head = temp;
        Tail = temp;
    }
    else
    {
        Tail->Next = temp;
        Tail = Tail->Next;
    }
    ListSize++;
}

SingleLinkedList.h

#pragma once
#include <iostream>
using namespace std;

template <class T>
struct LinkNode //节点类
{
    T Data;         //节点的数据
    LinkNode *Next; //指向该节点的下一个节点的指针
    LinkNode() : Next(NULL)
    {
        cout << "please enter data: ";
        cin >> Data;
    }
    LinkNode(const T &d, LinkNode *p = NULL) : Data(d), Next(p) {}
    ~LinkNode() {}
};
template <class T>
class SingleLinkedList
{
    LinkNode<T> *Head = nullptr; //首尾指针
    LinkNode<T> *Tail = nullptr;
    int ListSize = 0; //链表长度
public:
    SingleLinkedList(int Len = 0); //构造函数(顺序插入)
    ~SingleLinkedList()            //析构函数
    {
        DeleteList(); //释放new出来的节点
    }
    void DeleteList();
    void Delete(const T &Data); //可以使用&也可以不用，删除指定的一个元素
    bool IsEmpty() const
    {
        return ListSize == 0;
    }
    bool IsLast(LinkNode<T> *Node)
    {
        return Node == Tail;
    }
    int GetLength() const //返回链表长度
    {
        return ListSize;
    }
    int Find(const T &Data) const;                       //寻找链表中是否存在该值，存在返回其位置，不存在则返回-1，如果有重复则返回第一个找到的元素
    LinkNode<T> *FindPosition(const int position) const; //查看positio位置链表的值，若该位置不在链表中，则返回nullptr(position从0开始计数)
    void InsertHead(const T &Data);
    void InsertTail(const T &Data);
    void Reverse();         //反转链表
    void PrintList() const; //打印链表数据
};

#include "SingleLinkedList.cpp" //模板实现文件，包含编译模型

SingleLinkedList.cpp

template <class T>
SingleLinkedList<T>::SingleLinkedList(int len)
{
    LinkNode<T> *Cur;
    for (size_t i = 0; i < len; i++)
    {
        Cur = new LinkNode<T>();
        if (i == 0)
        {
            Head = Cur;
            Tail = Cur;
        }
        else
        {
            Tail->Next = Cur;
            Tail = Tail->Next;
        }
        ListSize++;
    }
}

template <class T>
void SingleLinkedList<T>::DeleteList()
{
    LinkNode<T> *Temp, *DeleteTemp;
    DeleteTemp = this->Head;
    while (DeleteTemp != nullptr)
    {
        Temp = DeleteTemp->Next;
        free(DeleteTemp);
        DeleteTemp = Temp;
        ListSize--;
    }
    Head = nullptr;
    Tail = nullptr;
}
template <class T>
void SingleLinkedList<T>::Delete(const T &Data)
{
    LinkNode<T> *Prev = this->Head;
    LinkNode<T> *Temp = nullptr;
    if (this->Head->Data == Data)
    {
        this->Head = Prev->Next;
        Prev->Next = nullptr;
        free(Prev);
        ListSize--;
    }

    while (Prev->Next != nullptr && Prev->Next->Data != Data)
    {
        Prev = Prev->Next;
    }
    if (Prev->Next != nullptr && Prev->Next != this->Tail)
    {
        Temp = Prev;
        Temp->Next = Prev->Next->Next;
        free(Prev->Next);
        ListSize--;
    }
    else
    {
        this->Tail = Prev;
        this->Tail->Next = nullptr;
        free(Prev->Next);
        ListSize--;
    }
}
template <class T>
int SingleLinkedList<T>::Find(const T &Data) const
{
    LinkNode<T> *Temp = this->Head;
    int position = 0;
    while (Temp != nullptr && Temp->Data != Data)
    {
        Temp = Temp->Next;
        position++;
    }
    if (Temp == nullptr)
        return -1;
    else
        return position;
}
template <class T>
LinkNode<T> *SingleLinkedList<T>::FindPosition(const int position) const
{
    if (position > ListSize)
        return nullptr;
    LinkNode<T> *Temp = this->Head;
    for (int i = 0; i < position; i++)
    {
        Temp = Temp->Next;
    }
    return Temp;
}
template <class T>
void SingleLinkedList<T>::InsertHead(const T &data)
{
    LinkNode<T> *temp = new LinkNode<T>(data);
    if (Head == nullptr)
    {
        Head = temp;
        Tail = temp;
    }
    else
    {
        temp->Next = Head;
        Head = temp;
    }
    // 局部变量不需要free，除非使用malloc申请时
    ListSize++;
}
template <class T>
void SingleLinkedList<T>::InsertTail(const T &data)
{
    LinkNode<T> *temp = new LinkNode<T>(data);
    if (Head == nullptr)
    {
        Head = temp;
        Tail = temp;
    }
    else
    {
        Tail->Next = temp;
        Tail = Tail->Next;
    }
    ListSize++;
}
template <class T>
void SingleLinkedList<T>::Reverse()
{
    if (this->Head == this->Tail)
        return;
    this->Tail = this->Head;
    LinkNode<T> *Prev = this->Head;
    LinkNode<T> *Cur = Prev->Next;
    while (Cur != nullptr)
    {
        LinkNode<T> *Temp = Cur->Next;
        Cur->Next = Prev;
        Prev = Cur;
        Cur = Temp;
    }
    this->Head = Prev;
    this->Tail->Next = nullptr;
}
template <class T>
void SingleLinkedList<T>::PrintList() const
{
    int n = 0;
    LinkNode<T> *temp = this->Head;
    while (temp != nullptr)
    {
        cout << "第" << n++ << "个:" << temp->Data << endl;
        temp = temp->Next;
    }
}

test.cpp

#include "SingleLinkedList.h"
#include <iostream>
#include <string>

int main()
{
    system("chcp 65001");
    SingleLinkedList<int> intList(3);
    intList.PrintList();
    cout << "链表的长度是：" << intList.GetLength() << endl;
    intList.InsertHead(3);
    intList.PrintList();
    cout << "链表的长度是：" << intList.GetLength() << endl;
    intList.InsertTail(300);
    intList.PrintList();
    cout << "链表的长度是：" << intList.GetLength() << endl;
    cout << "元素2在位置" << intList.Find(2) << endl;
    cout << "第3个位置是元素" << intList.FindPosition(3)->Data << endl;
    intList.Delete(300);
    intList.PrintList();
    intList.DeleteList();
    intList.PrintList();
    cout << "链表的长度是：" << intList.GetLength() << endl;
    SingleLinkedList<string> stringList(2);
    stringList.PrintList();
    cout << "链表的长度是：" << stringList.GetLength() << endl;
    cout << "元素abc在位置" << stringList.Find("abc") << endl;
    cout << "第1个位置是元素" << stringList.FindPosition(1)->Data << endl; //-1代表不存在该元素
    stringList.InsertHead("a");
    stringList.PrintList();
    cout << "链表的长度是：" << stringList.GetLength() << endl;
    stringList.InsertTail("abc");
    stringList.PrintList();
    cout << "元素abc在位置" << stringList.Find("abc") << endl;
    stringList.Reverse();
    stringList.PrintList();
    cout << "链表的长度是：" << stringList.GetLength() << endl;
    return 0;
}

测试后

参考：
https://michael.blog.csdn.net/article/details/88370698
https://blog.csdn.net/weixin_42136837/article/details/113411695
https://zhuanlan.zhihu.com/p/51855842