双向带头循环链表

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; }*/