欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浅谈带头结点的双向循环链表和单链表

程序员文章站 2024-03-21 19:11:46
...

带头结点的双向循环链表和单链表的区别

  相比我们讲的无头单向非循环的单链表结构,他的插入和删除都是O(1),也不需要增容,浪费空间换取时间,但是需要申请和释放空间。

面试题:写一个双向链表

思路
  主要实现函数ListInsert,ListFind,ListErase,其他的函数如头插,尾插,头删,尾删等函数可以用以上几个关键的函数代替实现。

代码实现

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* node = (ListNode*)malloc(sizeof(ListNode*));
	node->val = x;

	ListNode* next = head->next;
	node->next = next;
	head->next = node;
	next->prev = node;
	node->prev = head;
}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != head);

	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;

	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != head);

	ListNode* node = phead->next;
	ListNode* next = node->next;
	head->next = next;
	next->prev = head;
	free(node);
}

void ListInsert(ListNode* phead, LTDataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	ListNode posPrev = pos->prev;

	posPrev->next = newNode;
	newNode->next = pos;
	pos->prev = newNode;
	newNode->prev = posPrev;
}

void ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);

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

void ListErase(ListNode* pos)
{
	assert(pos);
	//pos不能是phead,否则头结点没了
	//assert(pos != phead);

	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

void ListDestory(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		ListErase(cur);
		cur = next;
	}
	free(phead);0
}