20分钟写一个链表

前言

有一个学长在面试的时候被问到这样一个问题，“你可以用20分钟写一个链表吗？”学长第一反应是，至少要一两个小时吧，链表的基本操作实现，增删查改等。
但是带头结点的循环双链表真的可以在20分钟写出来，这个谜底我们文末揭晓。

1.带头结点的循环双链表

在这里插入图片描述
带头结点的循环双链表的结构如上图所示，双链表每个结点有两个指针，prev和next，prev指向前驱结点，next指向后继结点。

哨兵位的头结点不存储有效数据，OJ题中提到的头结点一般都是第一个结点。没有明确说明，一般认为单链表不带哨兵位的头结点。而且即使尾插要讨论链表是否为空的情况，一般也不用哨兵位的头结点，除非题目需要多个单链表进行尾插，每次都讨论过于麻烦，考虑使用哨兵位的头结点，这篇文章的第二部分是一个例子，感兴趣可以看一下。链表OJ经典题目及思路总结（二）头结点

1.1 链表的分类、线性表的对比

带哨兵位的头结点，尾插以及其他操作不需要考虑链表是否为空；
双链表，两个指针，可以很方便找到前驱结点和后继结点。
循环的双链表，在有头指针的情况下可以方便访问头、尾结点。

链表一共有八种类型，如下图所示
在这里插入图片描述

顺序表、单链表、双链表的简单比较如下
在这里插入图片描述

1.2 双链表基本操作代码实现

1.2.1 初始化

带头结点的循环双链表，初始化只有头结点，prev和next指针都指向自己。这也表明，只要头指针的next域与头指针相等，即可判定链表为空。
与单链表相比，单链表是没有必要单独写一个初始化函数的；顺序表要初始化size等内容，也需要初始化函数。
带头结点的循环双链表很多操作，插入、删除都不需要更改头指针，因为有头结点的存在，链表不可能为空。所以插入、删除函数形参都是一级指针，为了保持接口的一致性，初始化函数也用一级指针，在函数内部动态申请空间、初始化，返回其地址即可。而单链表很多场景下一级指针搞不定，只能用二级指针，因此单链表的函数实现是一级、二级指针皆有。

代码实现如下方所示

//初始化
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

1.2.2 销毁、打印链表

销毁的思路是遍历并释放链表的结点，打印的思路是遍历并打印链表的结点。二者有一个共同点，就是遍历。值得一提的是，遍历的时候用临时变量cur（命名的可读性）来遍历，尽量不要动头指针，因为回头可能还有用。

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;LTNode* LTInit();
void LTDestroy(LTNode* phead);bool LTEmpty(LTNode* phead);
LTNode* BuyListNode(LTDataType x);
void LTPrint(LTNode* phead);void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);void LTInsert(LTNode* phead, LTDataType x);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTErase(LTNode* phead);

基本操作代码实现
Test.c

#include "List.h"
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if(node==NULL){perror("malloc failed");return NULL;//exit(-1);}node->data = x;node->prev = NULL;node->next = NULL;return node;
}
//初始化
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->prev = phead;phead->next = phead;return phead;
}
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}
void LTPrint(LTNode* phead)
{assert(phead);printf("<=>head<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}
bool LTEmpty(LTNode* phead)
{assert(phead);/*if (phead->next == phead)return true;elsereturn false;*/return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{LTInsert(phead,x);/*assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;	phead->prev = newnode;*/
}
void LTPopBack(LTNode* phead)
{LTErase(phead->prev);/*assert(phead);assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL;*/
}
void LTPushFront(LTNode* phead, LTDataType x)
{LTInsert(phead->next,x);/*assert(phead);LTNode* first = phead->next;LTNode* newnode = BuyListNode(x);//改链表指向的时候，可以先存储前驱或后继结点的位置，这样不需要过多考虑改指向的顺序问题phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;*///改结点间指向，也可以直接改，但要注意顺序，因为如果改的过程中，链表断开，找不到原来的前驱或后继结点就麻烦了//注意顺序/*newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;*/
}
void LTPopFront(LTNode* phead)
{LTErase(phead->next);/*assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* firstNext = first->next;phead->next = firstNext;firstNext->prev = phead;free(first);first = NULL;*/
}
void LTInsert(LTNode* pos, LTDataType x) 
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}
void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}