【数据结构-链表】链表的c++实现

本文包含了链表的常用操作，包括创建链表、插入节点、删除节点、遍历链表、求链表长度和删除链表，使用c++实现。

#include <iostream>
#include <cstdio>
using namespace std;

struct Node
{
    int data;
    Node* next;
};

//在链表中插入值为data的节点
void insert(Node* head, int data)
{
    Node* node = new Node();
    node->data = data;
    node->next = head->next;
    head->next = node;
}

//在值为elem的节点后插入值为data的结点
void insertAfter(Node* head, int elem, int data)
{
    Node* node = head->next;
    while(node!=nullptr && node->data!=elem)
        node = node->next;
    if(node==nullptr)
    {
        cout<<"找不到值为"<<elem<<"的结点"<<endl;
        return;
    }

    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = node->next;
    node->next = newNode;
}

//在链表最后添加一个值为data的节点
void append(Node* head, int data)
{
    Node* node = head;
    while(node->next!=nullptr)
        node = node->next;

    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = node->next;
    node->next = newNode;
}

//删除值为data的节点
void deleteNode(Node* head, int data)
{
    Node* node = head;
    while(node->next!=nullptr && node->next->data!=data)
        node = node->next;
    if(node->next==nullptr)
    {
        cout<<"找不到值为"<<data<<"的结点"<<endl;
        return;
    }

    Node* temp = node->next;
    node->next = node->next->next;
    delete temp;
}

//链表长度
int length(Node* head)
{
    int len = 0;
    Node* node = head->next;
    while(node!=nullptr)
    {
        len++;
        node = node->next;
    }
    return len;
}

//递归删除链表
void deleteLinkList(Node* head)
{
    if(head->next!=nullptr)
        deleteLinkList(head->next);
    delete(head);
}

//打印链表
void print(Node* head)
{
    Node* node = head->next;
    while(node!=nullptr)
    {
        cout<<node->data<<" ";
        node = node->next;
    }
    cout<<endl;
}


int main()
{
    Node* head = new Node(); //头结点
    int n; //链表中的元素个数
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int t;
        cin>>t;
        insert(head, t);
    }
    print(head);
    cout<<length(head)<<endl;

    insertAfter(head, 2, 4);
    print(head);
    cout<<length(head)<<endl;

    append(head, 5);
    print(head);
    cout<<length(head)<<endl;

    deleteNode(head, 5);
    print(head);
    cout<<length(head)<<endl;

    deleteLinkList(head);
    return 0;
}