链表（模板）

思路：

对于链表的插入和删除节点操作，由于头结点的插入和删除和其他节点的插入和删除操作不同，所以为了方便操作，可以增加一个虚的头节点，对于插入和删除操作设置两个指针pre和cur,pre指向需要删除或是插入的位置，pre指向需要删除或插入的位置的前一个节点

1.插入操作：创建一个新的节点，将pre的next指针指向新的节点，将新节点的next指向cur

2.删除操作：将pre的next指针指向cur的下一个节点

代码：

#include<iostream>
using namespace std;
//对于创建静态链表：构造一个结构体表示链表的每个节点：
//每个节点包含数据域和指针域
struct node{
    int val;
    node* next;
};
int n,x,y,z;
string op;
//插入节点，需要从链表头开始遍历整个链表，设置两个指针，一个指针为pre，一个指针为cur
//cur指针指向值为x的节点，由于要在cur之前插入，所以需要知道cur之前的节点，要将cur之前的
//节点指向新的节点，将新的节点的指针指向cur
void insertnode(node* head,int x,int y){
    node* pre=head;
    node* cur=head->next;
    while(cur!=NULL){
        //注意如果能找到x，则找到第一个x就退出循环，进行插入操作
        //如果没能找到x，则在链表的尾插入节点
        if(cur->val==x){
            break;
        }
        pre=cur;
        cur=cur->next;
    }

     node* t=new node();
            t->val=y;
            pre->next=t;
            t->next=cur;
}
//删除节点，同理，需要两个指针pre和指针cur，对于删除节点操作，需要将pre指向cur的下一个节点
void deletenode(node* head,int x){
      node* pre=head;
      node* cur=head->next;
      while(cur!=NULL){
        if(cur->val==x){
            pre->next=cur->next;
            delete cur;
            break;
        }
        pre=cur;
        cur=cur->next;
      }

}
int main(){
    cin>>n;
    //由于在删除和插入操作的时候头节点是特殊的，与其他节点的插入和删除操作不同
    //所以可以通过创建一个虚的头结点，这样就可以同一操作了
    node* head=new node();
    head->next=NULL;
    for(int i=1;i<=n;i++){
        cin>>op;
        if(op=="insert"){
            cin>>x>>y;
            insertnode(head,x,y);
        }else if(op=="delete"){
            cin>>z;
            deletenode(head,z);
        }
    }
    //实际的链表的头结点是虚的节点的下一个节点
    node* p=head->next;
    if(head->next==NULL){
        cout<<"NULL"<<endl;
    }
    while(p!=NULL){
        cout<<p->val<<" ";
        p=p->next;
    }
    return 0;
    
    }