前言

对于线性表中最基础的2种数据结构，顺序表与单链表，我们在此进行对比。
随后，我们继续深入学习链表的第二种形式——循环带头双链表

一、顺序表与单链表对比

若需频繁对内部数据进行操作，一般选用顺序表存储数据
若需频繁增加，删除数据，而对数据本身无过多操作，则选用链表

二、对于双链表函数的定义以及实现

1.对于双链表节点的定义

代码如下（示例）：

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;//下一节点
	struct ListNode* prev;//上一节点
	LTDataType data;
}LTNode;

2.对于双链表函数的定义与实现

代码如下（示例）：

LTNode* ListInit();
void ListDestory(LTNode* phead);
LTNode* BuyListNode(LTDataType x);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
bool ListEmpty(LTNode* phead);
size_t ListSize(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);
// pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x);
// 删除pos位置
void ListErase(LTNode* pos);

此处双链表接口函数，如果需要传输地址，全部只传一级指针。
这是因为，双链表带头结点，无论有无节点，都不需要改变头结点地址。这同时也是单链表不传二级指针的第二种方法，只需要给它加个头节点即可。

接下来，我们对上述函数一一实现。

LTNode* ListInit()
{
	LTNode* head=(LTNode*)malloc(sizeof(LTNode));
	assert(head);//申请空间失败直接中止
	head->next=head->prev=head;//如果置空，则不满足循环
	return head;
	//表头不存数据，所以不初始化头节点的data
}

此函数就使用返回值LTNode*，从而避免传递二级指针，目的在于保证接口函数的一致性

void ListDestory(LTNode* phead)
{
	assert(phead);//若phead为NULL，则中止函数
	LTNode* cur=phead->next,*del=NULL;
	while(cur!=phead)
	{
		del=cur;
		free(del);
		cur=cur->next;
		del=NULL;//好习惯不能丢，其实丢了也行
	}
	free(phead);
}

需要和单链表区别的点在于while循环的终止条件，由于它循环，所以不能是指空

LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode=(LTNode*)malloc(sizeof(LTNode));
	assert(newnode);//检查一下是否成功
	newnode->next=newnode->prev=NULL;
	newnode->data=x;
	return newnode;
}

创造理由：简化其他函数

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//若phead为NULL，则中止函数
	LTNode* newnode=BuyListNode(x);
	phead->prev->next=newnode;
	newnode->prev=phead->prev;
	newnode->next=phead;
	phead->prev=newnode;
}

相比单链表的找尾，是多么的简单友好啊！！

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);//若phead为NULL，则中止函数
	LTNode* newnode=BuyListNode(x);
	phead->next->prev=newnode;
	newnode->next=phead->next;
	newnode->prev=phead;
	phead->next=newnode;
}

相比单链表的头插要传二级指针，更改首节点，是多么的友好啊！！！

void ListPopBack(LTNode* phead)
{
	assert(phead);//若phead为NULL，则中止函数
	if(phead->prev==phead)
	return ;
	//assert(!ListEmpty(phead));暴力检查
	else
	{
		LTNode* del=phead->prev;
		phead->prev->prev->next=phead;
		phead->prev=phead->prev->prev;//这么写，纯属好玩
		free(del);
		del=NULL;//好习惯
	}
}

void ListPopFront(LTNode* phead)
{
	assert(phead);//若phead为NULL，则中止函数
	if(phead->next==phead)
	return ;
	//assert(!ListEmpty(phead));暴力检查
	else
	{
		LTNode* del=phead->next;
		phead->next->next->prev=phead;
		phead->next=phead->next->next;//这么写，纯属好玩
		free(del);
		del=NULL;//好习惯
	}
}

其实这里函数的实现非常简单，每次看这些函数，都让人直呼想哭。
唯一需要注意的就是改变节点的prev和next时要注意顺序,但这和单链表比起来，无论是难易程度还是效率，双链表完胜

bool ListEmpty(LTNode* phead)
{
	assert(phead);//若phead为NULL，则中止函数
	return phead->next==phead;
}

size_t ListSize(LTNode* phead)
{
	assert(phead);//若phead为NULL，则中止函数
	size_t i=0;
	LTNode* cur=phead->next;
	while(cur!=phead)
	{
		cur=cur->next;	
		i++;
	}
	return i;
}

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);//若phead为NULL，则中止函数
	LTNode* cur=phead->next;
	while(cur!=phead)
	{
		if(cur->data==x)
		return cur;
		cur=cur->next;	
	}
	printf("未找到值为X的节点\n");//可有可无
	return NULL;
}

// pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode=BuyListNode(x);
	pos->prev->next=newnode;
	newnode->prev=pos->prev;
	newnode->next=pos;
	pos->prev=newnode;
}

注意交换顺序即可

// 删除pos位置
void ListErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next=pos->next;
	pos->next->prev=pos->prev;
	free(pos);
	pos=NULL;
}

总结

综上，我们已经完全掌握了线性表最基础的两种，并且对比了它们的优缺点，知道了应该在什么情况下使用哪一种。