單鏈表

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