双向循环链表的增删查减

文章目录

• 1.链表结构体
• 2.链表头的初始化
• 3.节点的创建
• 4.插入
• 5.查找
• 6.删除
• 7.尾插
• 8.头插
• 9.尾删
• 10.头删
• 11.打印
• 12.清空和销毁

1.链表结构体

typedef int LTDataType;

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


ListNode* ListInit(ListNode *pphead);//初始化
ListNode* BuyListNode(LTDataType data);//创建节点
void ListInsert(ListNode *pos, LTDataType data);//在pos前面插入
ListNode* ListFind(ListNode *pphead, LTDataType data);//寻找节点
void ListErase(ListNode *pos);//删除
void ListPushBack(ListNode *pphead, LTDataType data);//尾插
void ListPushFront(ListNode *pphead, LTDataType data);//头插
void ListPopBack(ListNode *pphead);//尾删
void ListPopFront(ListNode *pphead);//头删
void ListPrint(ListNode *pphead);//打印
void ListClear(ListNode *pphead);//清空
void ListDestory(ListNode **pphead);//销毁
           

2.链表头的初始化

头的初始化有两种方式，要么传二级指针，要么开辟好空间的节点返回地址；

ListNode* ListInit(ListNode *pphead)//初始化
{
	/*assert(pphead);
	
	*pphead = (ListNode *)malloc(sizeof(ListNode));
	assert(*pphead);
	
	(*pphead)->prev = (*pphead)->next = *pphead;
	(*pphead)->data = 0;*/


	pphead = (ListNode *)malloc(sizeof(ListNode));
	assert(pphead);

	pphead->prev =pphead->next = pphead;
	pphead->data = 0;
	return pphead;
}
           

3.节点的创建

ListNode* BuyListNode(LTDataType data)//创建节点
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	assert(node);

	node->next = node->prev = NULL;
	node->data = data;
	return node;
}
           

4.插入

void ListInsert(ListNode *pos,LTDataType data)//早Pos前面插入
 {
	 assert(pos);
	 ListNode *node = BuyListNode(data);
	 ListNode *prev = pos->prev;//pos前面的节点
	//和pos前面节点链接
	 prev->next = node;
	 node->prev = prev;
	 //和pos链接
	 node->next = pos;
	 pos->prev = node;
 }
           

5.查找

ListNode* ListFind(ListNode *pphead, LTDataType data)//寻找节点
 {
	 assert(pphead);

	 ListNode *cur = pphead->next;
	 
	 while (cur!=pphead)
	 {
		 if (cur->data == data)
			 return cur;
		 cur = cur->next;
	 }
	 return NULL;
 }
           

6.删除

void ListErase(ListNode *pos)//删除
 {
	 assert(pos);
	 //pos前后节点
	 ListNode *prev = pos->prev;
	 ListNode *next = pos->next;
	 //前后节点链接
	 prev->next = next;
	 next->prev = prev;

	 free(pos);
	 pos = NULL;//没有多大意义，因为出了作用域就访问不到了
 }
           

7.尾插

尾插除了直接实现，还可以调用前面的插入函数；

双向循环链表头的前面就是尾；

void ListPushBack(ListNode *pphead,LTDataType data)//尾插
 {
	 assert(pphead);
	 //ListInsert(pphead, data);

	 ListNode *node = BuyListNode(data);
	 ListNode *tail = pphead->prev;//最后一个节点
	 //最后两个节点链接
	 tail->next = node;
	 node->prev = tail;
	 //和头链接
	 pphead->prev = node;
	 node->next = pphead; 
 }
           

8.头插

同理，头插也可以调用插入函数完成；

void ListPushFront(ListNode *pphead, LTDataType data)//头插
 {
	 assert(pphead);
	 //ListInsert(pphead->next, data);

	 ListNode *node = BuyListNode(data);
	 ListNode *next = pphead->next;//未插入前的第一个节点
	 //插入的接点和后面的进行链接
	 node->next = next;
	 next->prev = node;
	 //头链接
	 pphead->next = node;
	 node->prev = pphead;
 }
           

9.尾删

尾插也可以通过调用删除函数进行；

void ListPopBack(ListNode *pphead)//尾删
 {
	 assert(pphead);
	 assert(pphead->next != pphead);//头不能删
	 //ListErase(pphead->prev);

	 ListNode *tail = pphead->prev;//尾
	 ListNode *tailPrev = tail->prev;

	 pphead->prev = tailPrev;
	 tailPrev->next = pphead;

	 free(tail);
 }
           

10.头删

头删同样可以调用删除函数进行；

void ListPopFront(ListNode *pphead)//头删
 {
	 assert(pphead);
	 assert(pphead->next != pphead);
	 //ListErase(pphead->next);

	 ListNode *head= pphead->next;
	 ListNode *next = head->next;

	 pphead->next = next;
	 next->prev = pphead;

	 free(head);

 }
           

11.打印

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

12.清空和销毁

清空保留头结点，销毁头结点也要释放，同时要置空；

void ListClear(ListNode *pphead)//清空
 {
	 assert(pphead);
	 ListNode *cur = pphead->next;
	 while (cur!=pphead)
	 {
		 ListNode *next = cur->next;
		 free(cur);
		 cur = next;
	 }
	 pphead->prev = pphead->next = pphead;;
 }

 void ListDestory(ListNode **pphead)//销毁
 {
	 assert(pphead);
	 ListClear(*pphead);
	 free(*pphead);
	 *pphead = NULL;
 }