数据结构：双向链表_代码007(未授权)

本文介绍: 双向链表相关操作的介绍，以及顺序表与链表的区别

在这里插入图片描述

在这里插入图片描述
与单链表不同的是：

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”
“哨兵位”存在的意义：遍历循环链表避免死循环。

typedef int ListDataType;
typedef struct List
{
	ListDataType data;
	struct List* prev;//指向前驱节点
	struct List* next;//指向后继节点
}List;

在这里插入图片描述

List* BuyNode(ListDataType x)
{
	List* newnode = (List*)malloc(sizeof(List));
	if (newnode == NULL)
	{
		perror(malloc);
		return NULL;
	}
	newnode->data = x;
	newnode->next = newnode;
	newnode->prev = newnode;
}

创建哨兵位：

int main()
{
	//哨兵位
	List* head = BuyNode(-1);
	return 0;
}

void ListPushBack(List* phead, ListDataType x)
{
	assert(phead);
	List* newnode = BuyNode(x);

	newnode->next = phead;
	newnode->prev = phead->prev;
	//尾节点指向新节点
	phead->prev->next = newnode;
	
	phead->prev = newnode;
}

void ListPushFront(List* phead, ListDataType x)
{
	assert(phead);
	List* newnode = BuyNode(x);

	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next = newnode;
	//只有头节点时，就是头节点的prev
	phead->next->prev = newnode;
}

void ListPrint(List* phead)
{
	assert(phead);

	List* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

void ListPopBack(List* phead)
{
	assert(phead);
	//只有头节点
	assert(phead->next != phead);

	List* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
}

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

	List* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
}

List* ListFind(List* phead, ListDataType x)
{
	assert(phead);
	assert(phead->next != phead);
	List* cur = phead->next;

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

void ListPosFrontInsert(List* pos, ListDataType x)
{
	assert(pos);

	List* newnode = BuyNode(x);
	List* prev = pos->prev;

	newnode->prev = prev;
	newnode->next = pos;

	prev->next = newnode;
	pos->prev = newnode;
}

void ListPosBackInsert(List* pos, ListDataType x)
{
	assert(pos);

	List* newnode = BuyNode(x);
	List* next = pos->next;

	newnode->next = next;
	newnode->prev = pos;

	next->prev = newnode;
	pos->next = newnode;
}

void ListPosDel(List* pos)
{
	assert(pos);

	List* prev = pos->prev;
	List* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

void ListPosAfterDel(List* phead, List* pos)
{
	assert(phead);
	assert(pos);
	if (pos->next == phead)
	{
		ListPopFront(phead);
	}
	else
	{
		List* del = pos->next;
		del->next->prev = pos;
		pos->next = del->next;
		free(del);
	}
}

void ListDestroy(List* phead)
{
	assert(phead);
	assert(phead->next != phead);

	List* cur = phead->next;
	while (cur != phead)
	{
		List* next = cur->next;
		free(cur);
		cur = next;
	}
	cur = NULL;
	free(phead);
	phead = NULL;
}

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，物理上不一定连续
随机访问	O(1)	O(N)
任意位置插入或删除	可能需要搬运元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够需要扩容	没有容量的概念
应用场景	元素高效存储，频繁访问	任意位置频繁插入/删除
缓存利用率	高	低