链表（Linked List）

今天上午凭借昨天晚上自己学习的指针，今天学习了链表，发现还是一个非常有用的数据结构，从此我知道了学习指针的重要性。

很多人给我说，指针这个东西其实没有什么太大的作用，认为链表其实也可以不用指针写，虽然代码篇幅要大一些，但是要好理解一些，但是其实用指针写利远远大于弊，这里列出一些我认为是优点的东西。

1. 指针变量速度上有一些优势。
2. 指针数组可以动态的申请和释放空间，不需要像普通数组一样直接必须申请一个非常大的空间放在那里（有点像vector）
3. 这种链表代码非常短，好写容易理解！顶一个！

下面来上两个代码:

首先，First Establish the Linked List

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node *next;
}; 
int x;
Node *p,*head,*r;
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>x;
    head=new Node;
    r=head;
    while(x!=-1)
    {
        p=new Node;
        p->data=x;
        p->next=NULL;//important!!!
        r->next=p;
        r=p;
        cin>>x;
    }
    p=head->next;
    while(p->next!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<p->data;
}

其次，上面代码的基础上加入了insert，delete操作

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node *next;
}; 
int x;
int len=0;
Node *p,*head,*r;
int insertit(int loc,int val)
{
    Node *s;
    int count=0;
    p=head;//important
    while(p!=NULL&&count<loc-1)
    {
        p=p->next;
        count++;
    }
    if(p!=NULL) 
    {
        s=new Node;
        s->data=val;
        s->next=p->next;
        p->next=s;
    }
}
int deleteit(int loc)
{
    int count =0;
    p=head;
    while(p!=NULL&&count<loc-1)
    {
        p=p->next;
        count++;
    }
    if(p!=NULL)
    {
        p->next=p->next->next;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>x;
    head=new Node;
    r=head;
    while(x!=-1)
    {
        p=new Node;
        p->data=x;
        p->next=NULL;//important!!!
        r->next=p;
        r=p;
        cin>>x;
    }
    int n;
    cout<<endl<<"Please input the number of operations:";
    cin>>n;
    int a,b;
    char c;
    for(int i=1;i<=n;++i)
    {   
        cin>>c>>a;
        if(c=='I')
        {
            cin>>b;
            insertit(a,b);
        }
        if(c=='D')
        {
            deleteit(a);
        }
    }
    p=head->next;
    while(p->next!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<p->data;
}

双向链表随后就到！

下面是双向链表的代码，其实和单向链表的代码非常的相似，这里就不再赘述，内有注释：

#include<bits/stdc++.h>
using namespace std;
struct Linked_List{
    int data;
    Linked_List *pre,*suc;
};
Linked_List *p,*end,*head;
void insertit(int loc,int val)
{
    Linked_List* newl;
    int count=0;
    p=head->suc;
    while(p!=NULL&&count<loc-1)
    {
        p=p->suc;
        count++;
    }
    if(p!=NULL)
    {
        newl=new Linked_List;
        newl->data=val;
        newl->pre=p->pre;
        p->pre->suc=newl;
        p->pre=newl;
        newl->suc=p; 
    }
}
void deleteit(int loc)
{
    //Linked_List* newl;
    int count=0;
    p=head->suc;
    while(p!=NULL&&count<loc-1)
    {
        p=p->suc;
        count++;
    }
    if(p!=NULL)
    {
        p->suc->pre=p->pre;
        p->pre->suc=p->suc;
    } 
}
int main()
{
    std::ios::sync_with_stdio(false);
    head=new Linked_List;
    head->pre=NULL; 
    end=head;
    int n,a;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        p=new Linked_List;//sign for a new space
        p->data=a;//input the value
        p->suc=NULL;
        if(end==head)//very important!//如果还是停留在头指针的位置！，那么不好意思，前驱没有 
        p->pre=NULL;
        else
        p->pre=end;
        end->suc=p;
        end=p; 
    }
    int  nm;
    cout<<"Please input the number of operations:";
    cin>>nm;
    int aa,b;
    char ch;
    for(int i=1;i<=nm;++i)
    {
        cin>>ch>>aa;
        if(ch=='I')
        {
            cin>>b;
            insertit(aa,b);
        }
        if(ch=='D')
        {
            deleteit(aa);
        }
    } 
    p=head->suc;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->suc;
    }
    p=end;
    cout<<endl<<endl<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->pre;
    } 
    return 0;
}

最后这里再提醒大家一句：就是双向链表一定要在前驱前面加一个NULL判定标记，否则你就等着凉吧！