一、单链表基础概念讲解

上一张我们分析了顺序表，可以看出顺序表的好处有以下几点：
1、顺序表在查找某个元素时比较简单；顺序表可以直接通过下标的方式就可以访问到了这个元素
2、顺序表在插入到末尾，或者删除末尾元素也是比较简单的；这个时候也可以直接通过下标的方式直接访问到这个元素；
但是顺序表野有自己的缺点，如下：
1、顺序表在插入到中间某个位置时，是比较困难的；因为后面的元素需要挨个的移动；
2、同理，顺序表在删除中间某个位置的元素是，也是比较困难的；后面的元素也是要挨个移动到前面；
那么问题的关键就在这个地方了：
1、如果我们不是频繁的往中间去插元素或者去删除元素；我们知识在最后插入元素；或者主要的操作是遍历和查找元素的话，我们用顺序表，无疑是最快的；
那么，如果，那么我们就引入了链表的操作；
所谓的链表，就是每一个节点都是在存储上不连续的；都是可以通过上一个节点去访问到的；那么这其中有一个问题就是；如果在链表的最后面插入时候，就会存在需要遍历整个链表才能访问到最后一个元素的问题；所以我们为了解决这样的问题；我们直接定义出尾指针，来记录出最后一个节点；
综上：
我们可以看出链表的有点在于插入和删除；缺点是在查找某个元素时候，比较麻烦，需要遍历到这个元素才能把这个位置的内容取出；

二、单链表基本操作

1、单链表准备数据

什么是单链表；我们用图来表示以下：

image.png

我们的每个元素都是这样的；有自己的数据域，和一个指向下一个节点的指针阈；
所以我们这样来操作：

//结点
typedef struct Node {
    int data;
    Node * next;
}Node;
//创建列表
typedef struct ListMine {
    Node *head;
    Node *tail;
    int  length;
}ListMine;

2、单链表创建和析构

//创建空链表
void createList(ListMine* SL)
{
    SL->head = SL->tail = NULL;
    SL->length = 0;
}
void distroyList(ListMine* SL)
{
    Node* cur = SL->head;
    while (cur != NULL)
    {
        Node* tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    free(SL);
}

3、单链表插入和删除

图示：
1、插入操作：

image.png

2、删除操作：

image.png

//插入结点
bool insert(ListMine*SL, int i, int data)
{
    Node *p = SL->head; //0
    if (i > SL->length)
    {
        cout << "insert location error" << endl;
        return false;
    }
    Node *n = (Node*)calloc(1,sizeof(Node)); //分配新内存；
    n->data = data;
    n->next = NULL;
    if (i == 0)
    {
        SL->head = SL->tail = n;
        SL->length += 1;
        return true;
    }
    //之所以单独抽出来，是因为这样可以增快最后插入的时间
    //这就是为了告诉自己，尾指针的作用
    //后面如果有栈和队列的操作的时候，就会明白这个的重要性了
    if (i == SL->length)
    {
        SL->tail->next = n;
        SL->tail = n;
        SL->length ++;
        return true;
    }
    //后面这就是重要的一般插入的问题了
    int j = 0;
    while (j < i - 1 && p->next)
    {
        p = p->next;
        ++j;
    }
    n->next = p->next;
    p->next = n;
    SL->length++;
    return true;
}
//删除结点
bool del(ListMine*SL, int i)
{
    Node *p = SL->head; //0
    int j = 0;//0
    while (j < i-1 && p->next)
    {
        p = p->next;
        ++j;
    }
    Node *willfree = p->next;
    p->next = p->next->next;
    delete willfree;  //释放内存
    return true;
}

3、main函数验证

///主函数///
int main() {
    ListMine* SL = (ListMine*)calloc(1, sizeof(ListMine));
    createList(SL);
    int i = 0;
    for (; i < 10; i++)
    {
        insert(SL, i, i);

    }
    del(SL, 7);
    Node*cur = SL->head;
    while (cur!= NULL)
    {
        cout << "the data is " << cur->data << endl;
        cur = cur->next;
    }
    distroyList(SL);
}

运行结果如下：

image.png