雙向帶頭循環鏈表

1.順序表和鏈表

（1）順序表

• 優點：

  a、支持隨機訪問，很多算法都需要隨機訪問（快排、二分）

  b、cpu高速緩存命中率更高（cpu讀數據時，先去找緩存，如果沒有就去內存把數據加載到緩存。在加載時它不是隻加載一個數據，而是附近一片數據，所以如果是數組，它的數據是連續的，都會被加載到緩存了）

• 缺點：
  a、除了最後位置，其他位置插入刪除效率低

  b、空間增容需要時間和可能會浪費空間

（2）雙向帶頭循環鏈表

• 優點：
  a、任意位置插入刪除效率O(1)

  b、按需申請釋放空間，不浪費時間和空間

  c、cpu高速緩存命中率更低（還會污染緩存，讓緩存有很多無用的數據）

• 缺點：
  a、不支持隨機訪問，一些算法無法使用（快排、二分）

  b、鏈表存數據還得存儲指針

2.模擬實現

#define _CRT_SECURE_NO_WARNINGS 1 
#include"list.h"


struct node* buy_node(type x)
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;

    return newnode;
}

struct node* list_init()
{
    struct node* newnode = buy_node(-1);
    newnode->next = newnode;
    newnode->prev = newnode;
    return newnode;
}
//不需要二級指針，因為有哨兵，只是改變上一個結點的值
void list_push_back(struct node* head, type x)
{
    /*assert(head);
    
    struct node* newnode = buy_node(x);
    struct node* tail = head->prev;
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = head;
    head->prev = newnode;*/

    //也可以複用
    list_insert(head, x);//在Head的前面插入一個節點就是尾插
}
void list_pop_back(struct node* head)
{
    //assert(head);
    //assert(head->next != head);//這才是最少有一個節點，而不是assert(head->next)

    //struct node* tail = head->prev;
    //struct node* newtail = tail->prev;
    //free(tail);
    //newtail->next = head;
    //head->prev = newtail;

    //複用
    list_erase(head->prev);
 
}
void list_push_front(struct node* head, type x)
{
    /*assert(head);
    struct node* newnode = buy_node(x);
    struct node* next = head->next;

    newnode->prev = head;
    head->next = newnode;
    newnode->next = next;
    next->prev = newnode;*/

    //複用
    list_insert(head->next, x);
}
void list_pop_front(struct node* head)
{
    /*assert(head);

    struct node* next = head->next->next;
    free(head->next);

    head->next = next;
    next->prev = head;*/
    
    //複用
    list_erase(head->next);
}
void list_print(struct node* head)
{
    struct node* t = head->next; 
    while (t != head)
    {
        printf("%d ", t->data);
        t = t->next;
    }
    printf("\n");
}
struct node* list_find(struct node* head, type x)
{
    assert(head);
    struct node* t = head->next;
    while (t != head)
    {
        if (t->data == x)
        {
            return t;
        }
        t = t->next;
    }
    return NULL;
}
//插入pos之前的那個結點
void list_insert(struct node* pos, type x)
{
    assert(pos);
    struct node* newnode = buy_node(x);
    struct node* prev = pos->prev;

    prev->next = newnode;
    newnode->prev = prev;

    newnode->next = pos;
    pos->prev = newnode;
}
void list_erase(struct node* pos)
{
    assert(pos);

    struct node* prev = pos->prev;
    struct node* next = pos->next;
    free(pos);
    prev->next = next;
    next->prev = prev;
}
void list_destroy(struct node* head)
{
    assert(head);
    struct node* t = head;

    while (t != head)
    {
        struct node* next = t->next;
        free(t);
        t = next;
    }
    free(head);
    head = NULL;//沒有用其實
    //上面這麼寫無法改變head的值，不能讓它變成NULL，用二級指針才可以；但是要保持接口一致性,用一級指針就需要自己寫head = NULL
}
/*void list_destroy(struct node** phead)
{
    assert(*phead);
    struct node* t = *phead;

    while (t != *phead)
    {
        struct node* next = t->next;
        free(t);
        t = next;
    }
    free(*phead);
    *phead = NULL; 
}*/

​