顺序表的实现

单链表的实现

一、定义

从图示可清楚看到它有头结点，每个结点都有双指针，指向前一个结点和后一个节点，根据图示进行定义

typedef int Datatype;

typedef struct ListNode
{
	Datatype data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

二、创建结点

创建一个双指针的结点，带值进入，双指针置空。因为下一步初始化时要用到一个结点，因此创建结点写在前。

//创建结点
ListNode* Buynode(int x)
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	if (tmp==NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		tmp->data = x;
		tmp->next = NULL;
		tmp->prev = NULL;
	}
	return tmp;
}

三、初始化和销毁

初始化

头结点的数值我们传0(一般无多大意义)。要明白什么时候双向循环链表为空，那就是他的头指向他的尾。并且我们要改变他的头指针，因此传的是头指针的地址，接收用二级指针来接收。

//初始化
void ListInit(ListNode** phead)
{
	assert(phead);
	*phead = Buynode(0);
	(*phead)->next = *phead;
	(*phead)->prev = *phead;
}

销毁

销毁就是将每个结点释放置空，最后在释放头结点，完成链表的销毁

注：不能从头结点开始，会造成野指针，头结点要最后释放。要提前保存释放结点的下一个结点，方便更新释放结点。

//销毁
void ListDestroy(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}

四、尾部操作

尾插

此链表有很大优势，不需要遍历即可找到尾巴，即头结点的前一个结点。

创建新结点，尾结点的next指向新结点，新结点的next指向头结点，新结点的prev指向尾结点，最后头结点的prev指向新结点（这一步即更新了尾结点）。

//尾插
void ListPushBack(ListNode* phead, Datatype x)
{
	assert(phead);
	ListNode* newnode = Buynode(x);
	ListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->next = phead;
	newnode->prev = tail;
	phead->prev = newnode;
	
}

尾删

尾巴删除，直接找到尾巴，将尾巴的前一个和头结点建立联系，释放尾巴结点，最后置空即可。

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	if (phead->next == phead)
	{
		return NULL;
	}
	ListNode* tail = phead->prev;
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
	tail = NULL;
}

五、 在pos位置操作

固定位置插入删除，就必须先找到pos位置，我们先可以创建一个查找函数对pos进行定位。

查找函数

//查找
ListNode* Listfind(ListNode* phead, Datatype x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

pos位置插入

这个插入是前插，在pos位置前插入，具体就是将pos的prev、要插入结点、pos，三个结点相连接。

//pos位置插入
void ListInsert(ListNode* pos, Datatype x)
{
	ListNode* newnode = Buynode(x);
	pos->prev->next = newnode;
	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev = newnode;
}

pos位置删除

这就更简单，将pos位置前后的两结点相连接，释放掉pos即可。

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

六、头部操作

头部操作是对头结点的next进行操作，头结点不改变，务必注意这一点。

头插

在头结点和头结点的next结点中间插入一个结点，更新三个结点间的联系，与pos位置插入相同，我们可以简化代码，直接用ListInsert函数进行操作。

//头插
void ListPushFront(ListNode* phead, Datatype x)
{
	assert(phead);
	ListInsert(phead->next,x);
}

头删

与pos位置删除操作相同，直接用ListErase函数进行操作。

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	ListErase(phead->next);
}

附用 ListErase函数和ListInsert函数时，要清楚传的是头结点的next，头结点一定不能动。

 补充说明

既然头部操作可以附用ListErase函数和ListInsert函数，那么尾部操作当然也可以对ListErase函数和ListInsert函数进行服用来简化代码。

尾插

在尾巴后面加结点，即是在头结点前面加结点，ListInsert函数是在pos前加结点，我们只需将pos换成头结点，即可附用简化代码：

//尾插
void ListPushBack(ListNode* phead, Datatype x)
{
	assert(phead);
	ListInsert(phead, x);
	
}

尾删

删除最后一个结点，和删除pos位置结点操作相同，将pos换成尾结点即可附用ListErase函数简化代码：

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
    ListErase(phead->prev);

}

七、打印链表

不打印头结点，打印从头结点的next开始即可：

//打印
void PrintList(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead;
	cur = cur->next;
	while (cur!=phead)
	{
		printf("%d ",cur->data);
		cur=cur->next;
	}
}

到这一个带头双向循环链表的各个功能接口就实现了