总言

  数据结构基础：带头双向链表模拟实现。
  

文章目录

• 总言
• 1、带头双向链表各接口功能实现描述
• • 1.1、如何创建一个带头双向链表
  • 1.2、带头双向链表初始化:ListInit、BuyListNode
  • • 1.2.1、写法1.0：使用二级指针
    • 1.2.2、写法2.0：返回一级指针
  • 1.3、带头双向链表尾插、头插、打印
  • • 1.3.1、尾插：ListPushBack
    • 1.3.2、头插：ListPushFront
    • 1.3.3、打印：ListPrint
  • 1.4、带头双向链表头删、尾删、判空
  • • 1.4.1、头删：ListPopFront
    • 1.4.2、尾删：ListPopBack
    • 1.4.3、判空：ListIsEmpty
  • 1.5、在pos位置插入、删除
  • • 1.5.1、在pos位置前插入新结点：ListInsert
    • 1.5.2、基于 ListInsert 的头插、尾插
    • 1.5.3、删除pos位置处的结点：ListErease
    • 1.5.4、基于ListErease 的头删、尾删
  • 1.6、如何获取链表结点的数目：ListSize
  • 1.7、链表销毁
• 2、整体
• • 2.1、List.h
  • 2.2、List.c
• 3、带头双向循环链表与顺序表的基础比较

1、带头双向链表各接口功能实现描述

1.1、如何创建一个带头双向链表

  1）、基本说明
  根据题目描述，带头，即链表中带有一个哨兵位的头结点，双向，即链表中指针是双向指向的，我们的单链表前一个结点只指向后一个结点，但双向链表前后两个结点间则有互相指向的关系，换言之，对当前结点，我们需要一个存储它前一个结点的指针，也需要一个存储它后一个结点的指针。大致结构如图所示：

typedef int LTDataType;
typedef struct ListNode
{ListNode* prev;//前驱指针ListNode* next;//后续指针LTDataType data;//数据
}LTNode;

1.2、带头双向链表初始化:ListInit、BuyListNode

1.2.1、写法1.0：使用二级指针

  1）、基本说明
  对于双向链表，其带头、循环，因此链表中无数据时，初始时要有一个哨兵位的头结点，且其前驱指针和后续指针都指向自己本身。

ListNode* BuyListNode(LTDataType val)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));assert(newnode);//暴力检查newnode->data = val;newnode->next = newnode->prev = NULL;return newnode;
}void ListInit(ListNode** pphead)
{*pphead = BuyListNode(-1);//初始化，在链表中开辟一个哨兵位的头结点，不存储有效数据。(*pphead)->next = *pphead;//处理前驱指针指向，使其指向自己(*pphead)->prev = *pphead;//处理后续指针指向，使其指向自己
}

  ListNode** pphead：关于形参，此处需要传入二级指针，这样我们才能改变实参（结构体指针/一级指针）的指向。
  
  
  

1.2.2、写法2.0：返回一级指针

  1）、基本说明
  在上述初始化中，我们使用了二级指针，那么如何在不用二级指针的情况下进行带头双向链表的初始化呢？
  回顾我们做单链表的OJ题时，我们发现题中函数大多使用了返回值，此处我们可以参照该法，在使用一级指针的情况下完成链表初始化。
  如下：

ListNode* BuyListNode(LTDataType val)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));assert(newnode);//暴力检查newnode->data = val;newnode->next = newnode->prev = NULL;return newnode;
}ListNode* ListInit(void)
{ListNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

1.3、带头双向链表尾插、头插、打印

1.3.1、尾插：ListPushBack

  1）、基本说明
  问题： 在先前写过的单链表中，链表尾插需要二级指针，此处的双链表中，链表尾插是否仍旧需要二级指针？
  回答： 由于带头双向循环链表含有哨兵位的头结点，在进行插入、删除时，该哨兵位头结点作为链表的标头不会被改动，因此，就不存在头指针指向改变的问题。尾插只需要变动结点间的指向关系，即next、prev指针，而二者属于链表成员(结构体成员)，因此函数传参时使用一级指针即可。
  细节： 注意结点指向关系的变动，若不使用临时指针作为备份存储，则需要注意关系变动时的顺序问题。

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);//新增结点LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//找到原先链表的尾结点//改变结点中指针指向关系newnode->prev = tail;newnode->next = phead;phead->prev = newnode;tail->next = newnode;}

  示意图：

1.3.2、头插：ListPushFront

  1）、基本说明
  说明：带哨兵位的头插，需要理解此时头插的含义，哨兵位始终占据理论上的头结点不动，此处头插是指在哨兵位后(链表第二个结点)前插入。

void ListPushFront(LTNode* phead, LTDataType val)
{assert(phead);ListNode* newnode = BuyListNode(val);ListNode* head = phead->next;//备份//改变关系newnode->prev = phead;newnode->next = head;head->prev = newnode;phead->next = newnode;
}

  示意图：

  
  
  

1.3.3、打印：ListPrint

  1）、基本说明
  打印带头双向循环链表时，需要注意遍历链表的结束条件，需要确定何时停止，以及保证不打印出哨兵位的数据。
  一个思路是：用于遍历的指针初始时就指向哨兵位头结点后的首位有效结点，当遍历指针迭代更新，其指向哨兵位的头结点时，循环结束。

void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;//phead为哨兵位的头结点，非有效数据while (cur != phead)//注意条件{printf("%d ", cur->data);cur = cur->next;}
}

1.4、带头双向链表头删、尾删、判空

1.4.1、头删：ListPopFront

  1）、基本说明
  和头插一样，头删需要找准有效头结点，以及，在头删结点释放后，需要改变对应指针的指向关系。

void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);//防止删除哨兵位的头结点//assert(ListIsEmpty(phead));//找到当前哨兵位头结点后两位：有效头结点、新的有效头结点LTNode* head = phead->next;LTNode* headnext = head->next;//释放原先结点free(head);//修改指向关系phead->next = headnext;headnext->prev = phead;
}

  示意图：

  
  
  

1.4.2、尾删：ListPopBack

  1）、基本说明

void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListIsEmpty(phead));//找到对应的尾结点以及尾结点的上一位LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;//释放原先尾结点free(tail);//修改指向关系phead->prev = tailprev;tailprev->next = phead;
}

  示意图：

1.4.3、判空：ListIsEmpty

  1）、基本说明
  根据上述头删、尾删，在带头双向循环链表中，由于结点个数有限，删除操作不能一直进行下去。当我们删到只剩下一个哨兵位的头结点时，就应该停止，此时链表有效结点个数为零。
  因此，在链表删除结点时，需要进行判空操作，故将其提取写为一个函数：

bool ListIsEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

   phead->next == phead; 若为真，说明只剩下哨兵位的头结点，即代表此时链表为空；若为假，说明链表中还含有有效结点。
  
  
  
  

1.5、在pos位置插入、删除

1.5.1、在pos位置前插入新结点：ListInsert

  1）、基本说明
  带头双向链表，在pos位置前插入，由于有prev指针的存在，就不用遍历找pos前一个结点。

void ListInsert(LTNode* pos, LTDataType val)
{assert(pos);LTNode* newnode = BuyListNode(val);LTNode* posprev = pos->prev;//修改关系newnode->next = pos;newnode->prev = posprev;posprev->next = newnode;pos->prev = newnode;
}

  示意图：

1.5.2、基于 ListInsert 的头插、尾插

  1）、基本说明

void ListPushBack(LTNode* phead, LTDataType val)
{assert(phead);ListInsert(phead->next, val);
}

void ListPushFront(LTNode* phead, LTDataType val)
{assert(phead);ListInsert(phead, val); // 此处要注意phead->prev不是尾插
}

1.5.3、删除pos位置处的结点：ListErease

  1）、基本说明

void ListErease(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posnext->prev = posprev;
}

  示意图：

1.5.4、基于ListErease 的头删、尾删

  1）、基本说明

void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListIsEmpty(phead));ListErease(phead->prev);
}

void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListIsEmpty(phead));ListErease(phead->next);
}

1.6、如何获取链表结点的数目：ListSize

  1）、基本说明
  如何获取链表结点的数目大小？
  最常规的方法是遍历一遍链表，统计其结点数目：

int ListSize(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;int count = 0;while (cur != phead){count++;cur = cur->next;}return count;
}

  假如我们不遍历链表，那么可以如何获取链表结点数呢？
  一个相对可行的方法如下：

typedef int LTDataType;
typedef struct ListNode
{ListNode* prev;ListNode* next;LTDataType data;
}LTNode;typedef struct List
{LTNode * phead;size_t size;
}

  在创建代表链表单结点的结构体的基础上，我们再创建一个结构体，该结构体成员为链表哨兵位的头结点，以及链表结点数目统计，这样我们每次增删查改时，相应变动size值即可。

  
  补充：可能有人会想，哨兵位的头结点中不存储有效数据，我们可以用其phead->val值统计链表的结点个数。
  这种方法如果要能执行是有条件限制的，typedef int LTDataType;，如果我们的数据类型是整型还好说。若是字符类型char，在有符号的情况下，val的最大值为128，但我们的结点数目不一定在这个范围内。同理，若该链表数据类型是double浮点型，那么哨兵位头结点中，val也不能用于记录结点数目。即这种方法具有局限性。
  
  
  

1.7、链表销毁

  1）、基本说明

void LiseDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

2、整体

2.1、List.h

#pragma once#include
#include
#include
#includetypedef int LTDataType;
typedef struct ListNode
{ListNode* prev;ListNode* next;LTDataType data;
}LTNode;//void ListInit(ListNode** pphead);
ListNode* ListInit(void);
void ListPrint(LTNode* phead);
bool ListIsEmpty(LTNode* phead);void ListPushBack(LTNode* phead, LTDataType val);
void ListPushFront(LTNode* phead, LTDataType val);void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);void ListInsert(LTNode* pos, LTDataType val);
void LiseDestory(LTNode* phead);

2.2、List.c

#include"List.h"ListNode* BuyListNode(LTDataType val)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));assert(newnode);//暴力检查newnode->data = val;newnode->next = newnode->prev = NULL;return newnode;
}//void ListInit(ListNode** pphead)
//{
//	*pphead = BuyListNode(-1);
//	(*pphead)->next = *pphead;
//	(*pphead)->prev = *pphead;
//}ListNode* ListInit(void)
{ListNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void ListPushBack(LTNode* phead, LTDataType val)
{assert(phead);ListNode* newnode = BuyListNode(val);ListNode* tail = phead->prev;//保存原先尾结点//改变关系newnode->prev = tail;newnode->next = phead;phead->prev = newnode;tail->next = newnode;
}void ListPushFront(LTNode* phead, LTDataType val)
{assert(phead);ListNode* newnode = BuyListNode(val);ListNode* head = phead->next;//备份//改变关系newnode->prev = phead;newnode->next = head;head->prev = newnode;phead->next = newnode;
}void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead;while (cur != phead)//注意条件{printf("%d ", cur->data);cur = cur->next;}
}void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);//防止删除哨兵位的头结点//assert(ListIsEmpty(phead));//找到当前哨兵位头结点后两位：有效头结点、新的有效头结点LTNode* head = phead->next;LTNode* headnext = head->next;//释放原先头结点free(head);//修改指向关系phead->next = headnext;headnext->prev = phead;
}void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListIsEmpty(phead));//找到对应的尾结点以及尾结点的上一位LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;//释放原先尾结点free(tail);//修改指向关系phead->prev = tailprev;tailprev->next = phead;
}bool ListIsEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}void ListInsert(LTNode* pos, LTDataType val)
{assert(pos);LTNode* newnode = BuyListNode(val);LTNode* posprev = pos->prev;//修改关系newnode->next = pos;newnode->prev = posprev;posprev->next = newnode;pos->prev = newnode;
}void ListPushBack(LTNode* phead, LTDataType val)
{assert(phead);ListInsert(phead->next, val);
}void ListPushFront(LTNode* phead, LTDataType val)
{assert(phead);ListInsert(phead, val); // 此处要注意phead->prev不是尾插
}void ListErease(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posnext->prev = posprev;
}void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListIsEmpty(phead));ListErease(phead->prev);
}void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListIsEmpty(phead));ListErease(phead->next);
}void LiseDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}int ListSize(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;int count = 0;while (cur != phead){count++;cur = cur->next;}return count;
}

3、带头双向循环链表与顺序表的基础比较

  对顺序表：
  优点： ①下标随机访问
  缺点： ①头部或中间的插入删除效率低、②扩容有一定程度性能的消耗，可能存在一定程度的空间浪费
  
  对带头双向循环链表：
  优点： 任意位置插入删除为O(1)，按需申请释放
  缺点： 不支持下标随机访问