本章重点

• 链表的分类
  
• 带头双向循环链表接口实现
  
• 顺序表和链表的区别
  
• 缓存利用率参考存储体系结构 以及 局部原理性。
  

一、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

二、带头双向循环链表接口实现

1.申请结点：struct ListNode* BuyLTNode(LTDataType x)

动态申请结点，函数返回的是一个指针类型，用malloc开辟一个LTNode大小的空间，并用node指向这个空间，再判断是否为空，如为空就perror，显示错误信息。反之则把要存的数据x存到newnode指向的空间里面，把指针置为空。

// 申请结点
struct ListNode* BuyLTNode(LTDataType x)
{
  struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->data = x;
  node->prev = node;
  node->next = node;
  return node;
}

2.初始化：struct ListNode* LTInit()

// 初始化
void LTInit(struct ListNode* phead)
{
  phead = BuyLTNode(-1);
  phead->prev = phead;
  phead->next = phead;
}

我们首先看看这个初始化有什么问题嘛？

phead为空指针，说明我们的初始化没有效果，这是因为phead是函数里面的形参，出了作用域就销毁，plsit仍然是空指针，形参的改变不能影响实参，但是我们可以通过返回phead的地址解决问题。

单链表开始是没有节点的，可以定义一个指向空指针的结点指针，但是此链表不同，需要在初始化函数中创建个头结点，它不用存储有效数据。因为链表是循环的，在最开始需要让头结点的next和pre指向头结点自己。

因为其他函数也不需要用二级指针（因为头结点指针是不会变的，变的是next和pre，改变的是结构体，只需要用结构体针即可，也就是一级指针）为了保持一致此函数也不用二级指针，把返回类型设置为结构体指针类型。

// 初始化 - 改变实参plsit
struct ListNode* LTInit()
{
  struct ListNode* phead = BuyLTNode(-1);
  phead->prev = phead;
  phead->next = phead;
  return phead;
}

3.尾插：void LTPushBack(struct ListNode* phead, LTDataType x)

尾插首先要找到尾结点，再将要尾插的结点与尾结点和带头结点链接，由于是带头结点，所以此处不需要关注头结点为空的问题。

// 尾插
void LTPushBack(struct ListNode* phead, LTDataType x)
{
  assert(phead);
  struct ListNode* tail = phead->prev;
  struct ListNode* newnode = BuyLTNode(x);
  newnode->prev = tail;
  tail->next = newnode;
  newnode->next = phead;
  phead->prev = newnode;
}

4.尾删：void LTPopBack(struct ListNode* phead)

尾删只需要找到尾结点的前驱结点，再把带头结点和前驱结点链接，释放尾结点就完成了尾删。

不过这里需要处理一下只有带头结点的删除，此时真正的链表为空，此时就不能删除了。

// 尾删
void LTPopBack(struct ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//链表为空
  struct ListNode* tail = phead->prev;
  struct ListNode* tailPrev = tail->prev;
  free(tail);
  tailPrev->next = phead;
  phead->next = tailPrev;
}

5.头插：void LTPushFront(struct ListNode* phead, LTDataType x)

头插需要注意顺序，如果先让phead和newnode链接，那么就找不到phead结点的后续结点，这样就无法让newnode和phead结点的后续结点链接。

// 头插
void LTPushFront(struct ListNode* phead, LTDataType x)
{
  assert(phead);
  struct ListNode* newnode = BuyLTNode(x);
  //顺序不可颠倒
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}

【编织时空四：探究顺序表与链表的数据之旅】（下）：https://developer.aliyun.com/article/1424881