结构体的建立

typedef  int LTDatatype;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDatatype data;
}LTNode;

初始化

/*void ListInit(LTNode**pphead);*///初始化，初始化要传指针，要建立一个哨兵节点，要实质上把plist改变
LTNode* ListInit();//初始化,也可以不用二级，用一个返回值就行
LTNode* ListInit()
{
  LTNode* guard= (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
    return NULL;
  }
  guard->next = guard;
  guard->prev = guard;
  return guard;
}

创建节点

LTNode* BuyNode(LTDatatype x)
{
  LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
  return NULL;
  }
  guard->next = NULL;
  guard->data = x;
  guard->prev = NULL;
  return guard;
}

头插节点

void ListPushFront(LTNode* pphead, LTDatatype x)
{
  LTNode* newnode = BuyNode(x);
  LTNode* next = pphead->next;
  newnode->next = next;
  next->prev = newnode;
  newnode->prev = pphead;
  pphead->next = newnode;
}

尾插节点

void ListPushBack(LTNode* pphead, LTDatatype x)
{
  assert(pphead);//pphead不可能为空
  LTNode* newnode = BuyNode(x);
  LTNode* tail = pphead->prev;//先找到尾
  tail->next = newnode;//开始尾插
  newnode->prev = tail;
  newnode->next = pphead;
  pphead->prev =newnode;
}//这种写法即使pphead是NULL，依然能插入，因为通过tail找到了pphead

头删节点

void ListPopFront(LTNode* pphead)
{
  LTNode* next = pphead->next;
  pphead->next = next->next;
  next->next->prev = pphead;
  free(next);
}

尾删节点

void ListPopBack(LTNode* pphead)
{
  assert(pphead);
  assert(!ListEmpty(pphead));//判断是否为空
  LTNode* tail1 = pphead->prev;
  LTNode* tail2 = tail1->prev;
  free(tail1);
  tail1 = NULL;
  tail2->next = pphead;
  pphead->prev = tail2;
}
bool ListEmpty(LTNode* pphead)
{
  assert(pphead);
    return pphead->next == pphead;//检测是否只剩头节点
}

节点查找

LTNode* ListFind(LTNode* pphead,LTDatatype x)
{
  assert(pphead);
  size_t n = 0;
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
    if (cur->data == x)
    {
      return cur;
    }
  }
}

节点前插入

void ListInsert(LTNode* pos, LTDatatype x)//在pos之前插入,若在pphead前插入，实际会变成尾插
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}

节点删除

void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  prev->next = next;
  next->prev = prev;
  free(pos);
  pos = NULL;
}

销毁链表

void ListDestory(LTNode* pphead)//传一级，二级都可以
{
  assert(pphead);
  //1.先释放带数字的节点，最后释放头哨兵
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  LTNode* next = cur->next;
  free(cur);
  cur = next;
  }
  free(pphead);
  pphead = NULL;//如果传一级指针，这里的置空不起作用，若想起作用，要传二级指针
}
//建议：使用一级指针，然后让调用ListDestory的人置空，保持接口的一致性，这里最后回到主函数把plist=NULL;即可

Dlist.h

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef  int LTDatatype;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDatatype data;
}LTNode;
/*void ListInit(LTNode**pphead);*///初始化，初始化要传指针，要建立一个哨兵节点，要实质上把plist改变
LTNode* ListInit();//初始化,也可以不用二级，用一个返回值就行
void ListPushBack(LTNode* pphead,LTDatatype x);//不需要传地址，因为再怎么改变都不会改变哨兵位的头，改的是哨兵位的指向
void ListPushFront(LTNode* pphead, LTDatatype x);
void ListPopBack(LTNode* pphead);
void ListPrint(LTNode* pphead);
void ListPopFront(LTNode* pphead);
bool ListEmpty(LTNode* pphead);
size_t ListSize(LTNode* pphead);
LTNode* ListFind(LTNode* pphead, LTDatatype x);
void ListInsert(LTNode* pos, LTDatatype x);
void ListErase(LTNode* pos);
void ListDestory(LTNode* pphead);

Dlist.c

#define _CRT_SECURE_NO_WARNINGS
#include"Dlist.h"
LTNode* ListInit()
{
  LTNode* guard= (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
  return NULL;
  }
  guard->next = guard;
  guard->prev = guard;
  return guard;
}
LTNode* BuyNode(LTDatatype x)
{
  LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
  if (guard == NULL)
  {
  return NULL;
  }
  guard->next = NULL;
  guard->data = x;
  guard->prev = NULL;
  return guard;
}
void ListPrint(LTNode* pphead)
{
  assert(pphead);
  printf("guard<=>");
  LTNode* cur = pphead->next;
  while (cur!= pphead)
  {
  printf("%d<=>", cur->data);
  cur= cur->next;
  }
  printf("\n");
}
void ListPushBack(LTNode* pphead, LTDatatype x)
{
  assert(pphead);//pphead不可能为空
  LTNode* newnode = BuyNode(x);
  LTNode* tail = pphead->prev;//先找到尾
  tail->next = newnode;//开始尾插
  newnode->prev = tail;
  newnode->next = pphead;
  pphead->prev =newnode;
}//这种写法即使pphead是NULL，依然能插入，因为通过tail找到了pphead
void ListPushFront(LTNode* pphead, LTDatatype x)
{
  LTNode* newnode = BuyNode(x);
  LTNode* next = pphead->next;
  newnode->next = next;
  next->prev = newnode;
  newnode->prev = pphead;
  pphead->next = newnode;
}
void ListPopBack(LTNode* pphead)
{
  assert(pphead);
  assert(!ListEmpty(pphead));//判断是否为空
  LTNode* tail1 = pphead->prev;
  LTNode* tail2 = tail1->prev;
  free(tail1);
  tail1 = NULL;
  tail2->next = pphead;
  pphead->prev = tail2;
}
bool ListEmpty(LTNode* pphead)
{
  assert(pphead);
  return pphead->next == pphead;//检测是否只剩头节点
}
void ListPopFront(LTNode* pphead)
{
  LTNode* next = pphead->next;
  pphead->next = next->next;
  next->next->prev = pphead;
  free(next);
}
size_t ListSize(LTNode* pphead)
{
  size_t n = 0;
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  ++n;
  cur = cur->next;
  }
  return n;
}
LTNode* ListFind(LTNode* pphead,LTDatatype x)
{
  assert(pphead);
  size_t n = 0;
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  if (cur->data == x)
  {
    return cur;
  }
  }
}
void ListInsert(LTNode* pos, LTDatatype x)//在pos之前插入,若在pphead前插入，实际会变成尾插
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}
void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  prev->next = next;
  next->prev = prev;
  free(pos);
  pos = NULL;
}
void ListDestory(LTNode* pphead)//传一级，二级都可以
{
  assert(pphead);
  //1.先释放带数字的节点，最后释放头哨兵
  LTNode* cur = pphead->next;
  while (cur != pphead)
  {
  LTNode* next = cur->next;
  free(cur);
  cur = next;
  }
  free(pphead);
  pphead = NULL;//如果传一级指针，这里的置空不起作用，若想起作用，要传二级指针
}
//建议：使用一级指针，然后让调用ListDestory的人置空，保持接口的一致性，这

顺序表和链表的区别

顺序表优点：1.尾插尾删的效率很高

2.可以随机访问（通过下标），链表需要遍历

3.和链表相比cpu高速缓存面中率很高

寄存器相当于锅，如有数组{1，2，3，4}，这四个元素是存在主存里面的，数据结构是在主存里面管理我们的数据，链表也一样（堆是一个虚拟的内存的划分）

越往上速度越快，成本更高，L1,L2,L3被称为CPU的高速缓存

代码编译好了就是指令，通过CPU去运行指令，CPU访问通过访问内存数据运行指令，

CPU执行指令，不会直接访问内存

1.先看数据在不在三级缓存，在（命中），就直接访问

2.不在（不命中），先加载到缓存，再访问

顺序表的缺点：1.头部和中部的插入删除效率低——O(N)

2.扩容（动态开辟空间）——性能消耗，有一定空间浪费

链表的优点：1.任意位置插入删除效率很高O(1)

2.按需申请释放（不存在空间浪费）

链表的缺点：1.不支持随机访问（现实中随机访问很重要）

数据结构——双向循环链表