关于链表:单链表知识点

单链表

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);
}