关于链表:单链表知识点

单链表

1.程序表

长处：物理空间间断，反对随机拜访

毛病：空间不够就须要扩容，破费工夫和空间；插入删除效率低下

2.单链表

长处：按需申请开释空间；插入删除常数工夫

毛病：不反对随机拜访

3.留神点

(1)在批改指针自身的内容时，也就是扭转指针自身存储的地址，咱们须要的是二级指针

void list_push_back(struct node** head, type x)
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    assert(newnode);
    newnode->data = x;
    newnode->next = NULL;

    //这里想扭转头结点的地址，让它指向一块新的空间，也就是扭转一个*类型的值->于是咱们须要**作为形式参数!!
    if (*head == NULL)
    {
        *head = newnode;
    }

    else 
    {
        struct node* cur = *head;
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}

4.实现

//forward_list<int> s;外面的插入删除：insert_after erase_after
void list_print(struct node* head)
{
    struct node* cur = head;
    while (cur != NULL)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
struct node* buy_newnode(type x)
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    assert(newnode);
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}
void list_push_back(struct node** phead, type x)
{
    assert(phead);
    struct node*newnode =  buy_newnode(x);

    //这里想扭转头结点的地址，让它指向一块新的空间，也就是扭转一个*类型的值->于是咱们须要**作为形式参数!!
    if (*phead == NULL)
    {
        *phead = newnode;
    }

    else 
    {
        struct node* cur = *phead;
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}
//也须要传入二级指针：不论有没有元素，都须要扭转head的值，因为head必须是指向第一个结点的!!! 
void list_push_front(struct node** phead, type x)
{
    assert(phead);
    struct node* newnode = buy_newnode(x);
    newnode->next = *phead;
    *phead = newnode;

    //验证高低都能够但下面的更加简洁
    /*if (*phead == NULL)
    {
        *phead = newnode;
    }
    else
    {
        newnode->next = *phead;
        *phead = newnode;
    }*/
}
//一级指针不必查看：它可能就是一个空链表
//二级指针须要查看：head是存在的，head有这个变量，那就肯定有个地址。phead外面寄存的就是head的地址
void list_pop_front(struct node**phead)
{
    assert(phead);
    assert(*phead);//这里头删,head肯定须要有值才能够删除
    struct node* pre_head = *phead;
    *phead = (*phead)->next;
    free(pre_head);//开释它指向的空间
}
void list_pop_back(struct node**phead)
{
    assert(phead);
    assert(*phead);
    struct node* t = *phead;

    if (t->next == NULL)
    {
        free(*phead);
        *phead = NULL;
    }
    else
    {
        while (t->next->next != NULL)
        {
            t = t->next;
        }
        t->next = NULL;
        free(t->next);
    }     
}
struct node* list_find(struct node* head, type x)
{
    assert(head);
    struct node* t = head;
    while (t != NULL)
    {
        if (t->data == x)
        {
            return t;
        }
        t = t->next;
    }
    return NULL;
}
void list_insert(struct node** phead, struct node* pos, type x)
{ 
    assert(pos);
    assert(phead);
    if (pos == *phead)
    {
        list_push_front(phead, x);
    }
    else
    {
        struct node* t = *phead;
        while (t->next != pos)
        {
            t = t->next;
        }
        struct node*newnode = buy_newnode(x);
        newnode->next = pos;
        t->next = newnode;
    }
}
void list_erase(struct node**phead, struct node *pos)
{
    assert(phead);
    assert(pos);//如果链表为空，pos不可能无效
    if (pos == *phead)
    {
        list_pop_front(phead);
    }
    else
    {
        struct node* t = *phead;
        while (t->next != pos)
        {
            t = t->next;
        }
        t->next = pos->next;
        free(pos);
        //pos = NULL;//简直有效？因为pos是个形参，在这里置空无用，交给里面解决
    }
}
void list_insert_after(struct node* pos, type x)
{
    assert(pos);
    struct node * newnode = buy_newnode(x);

    newnode->next = pos->next;
    pos->next = newnode;
}
void list_erase_after(struct node* pos)
{
    assert(pos->next);
    struct node* t = pos->next;
    pos->next = pos->next->next;
    free(t);
}