关于数据结构:双向带头循环链表

双向带头循环链表

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

​