C++ 链表实现 - 创建、插入、删除、查询节点

#include using namespace std;

template//定义链表节点类 class Node { public: T data; //节点的数据 Node *next; //指向下一个节点的指针 Node(T value)//构造函数 { data = value; next = NULL; //初始时下一个节点为空 } };

template//定义链表类 class LinkedList { private: Node *head; //链表头指针 public: LinkedList() //构造函数 { head = NULL; //初始化链表为空 }

~LinkedList()//析构函数
{
    Node<T> *current = head;//释放链表内存
    while (current != NULL)
    {
        Node<T> *temp = current;
        current = current->next;
        delete temp;
    }
}

void create()//创建链表
{
    int n;
    cout << '请输入链表的长度：';
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        T val;
        cout << '请输入第' << i + 1 << '个节点的值：';
        cin >> val;
        Node<T> *newNode = new Node<T>(val);// 创建新节点
        if (head == NULL)//如果链表为空，将新节点设为头节点
        {
            head = newNode;
        }
        else//如果链表不为空，将新节点插入到链表末尾
        {
            Node<T> *current = head;
            while (current->next != NULL)
            {
                current = current->next;
            }
            current->next = newNode;
        }
    }
}

void insert()//插入节点
{
    T val;
    cout << '请输入要插入的节点值：';
    cin >> val;
    Node<T> *newNode = new Node<T>(val);
    int position;
    cout << '请输入要插入的位置（从1开始）：';
    cin >> position;
    if (position <= 0)//插入节点到指定位置
    {
        cout << '插入位置无效！' << endl;
    }
    else if (position == 1)  //插入位置是头节点之前
    {

        newNode->next = head;
        head = newNode;
    }
    else  //插入位置是中间或末尾节点
    {
        Node<T> *current = head;
        int count = 1;
        while (current != NULL && count < position - 1)
        {
            current = current->next;
            count++;
        }
        if (current == NULL)
        {
            cout << '插入位置无效！' << endl;
        }
        else
        {
            newNode->next = current->next;
            current->next = newNode;
        }
    }
}

void remove()//删除节点
{
    T val;
    cout << '请输入要删除的节点值：';
    cin >> val;
    //判断要删除的节点是否为头节点
    if (head != NULL && head->data == val)
    {
        Node<T> *temp = head;
        head = head->next;
        delete temp;
        return;
    }
    //查找要删除的节点并删除
    Node<T> *current = head;
    while (current != NULL && current->next != NULL)
    {
        if (current->next->data == val)
        {
            Node<T> *temp = current->next;
            current->next = current->next->next;
            delete temp;
            return;
        }
        current = current->next;
    }
    cout << '要删除的节点不存在！' << endl;
}

void print()//链表遍历输出
{
    Node<T> *current = head;
    while (current != NULL)
    {
        cout << current->data << ' ';
        current = current->next;
    }
    cout << endl;
}

void search()//结点的查询
{
    T val;
    cout << '请输入要查询的节点值：';
    cin >> val;
    Node<T> *current = head;
    int position = 1;
    while (current != NULL)
    {
        if (current->data == val)
        {
            cout << '节点' << val << '在链表中的位置为：' << position << endl;
            return;
        }
        current = current->next;
        position++;
    }
    cout << '节点' << val << '不在链表中！' << endl;
}

};

int main() { // 创建链表对象 LinkedList list; // 创建链表 list.create(); // 输出链表 cout << '链表内容：'; list.print(); // 插入节点 list.insert(); // 输出链表 cout << '链表内容：'; list.print(); // 删除节点 list.remove(); // 输出链表 cout << '链表内容：'; list.print(); // 查询节点 list.search(); return 0; }