带头双向循环链表 双向链表 基本操作 C语言实现 数据结构 顺序表和链表的区别

结构复杂，操作简单

#include
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}ListNode;

ListNode* BuyListNode(LTDataType x)//买结点
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)exit(1);
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

ListNode* ListInit()//初始化
{
	ListNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

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

bool IsEmpty(ListNode* phead)//判空
{
	assert(phead != NULL);
	return phead->next == phead;
}

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

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

void ListPushBack(ListNode* phead, LTDataType x)//尾插
{
	assert(phead != NULL);
	ListNode* newnode = BuyListNode(x);
    phead->prev->next = newnode;
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev = newnode;
}

优化

void ListPushBack(ListNode* phead, LTDataType x)//尾插
{
	assert(phead != NULL);
	ListInsert(phead, x);
}

void ListPushFront(ListNode* phead, LTDataType x)//头插
{
	assert(phead != NULL);
	ListNode* newnode = BuyListNode(x);
	phead->next->prev = newnode;
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next = newnode;
}

优化 

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

void ListPopBack(ListNode* phead)//尾删
{
	assert(phead!=NULL);
	assert(IsEmpty(phead)!=1);
	ListNode* ptr = phead->prev;
	ptr->prev->next = phead;
	phead->prev = ptr->prev;
	free(ptr);
}

优化 

void ListPopBack(ListNode* phead)//尾删
{
	assert(phead!=NULL);
	assert(IsEmpty(phead)!=1);
	ListErase(phead->prev);
}

void ListPopFront(ListNode* phead)//头删
{
	assert(phead != NULL);
	assert(IsEmpty(phead) != 1);
	ListNode* ptr = phead->next;
	phead->next = ptr->next;
	ptr->next->prev = phead;
	free(ptr);
}

优化 

void ListPopFront(ListNode* phead)//头删
{
	assert(phead != NULL);
	assert(IsEmpty(phead) != 1);
	ListErase(phead->next);
}

int ListSize(ListNode* phead)//结点个数
{
	assert(phead);
	ListNode* cur = phead->next;
	int i = 0;
	while (cur != NULL)
	{
		i++;
		cur = cur->next;
	}
	return i;
}

void ListDestory(ListNode* phead)//销毁
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != NULL)
	{
		ListNode* p =cur->next;
		ListErase(cur);
		cur = p;
	}
	free(phead);
	phead = NULL;//没用，传二级指针才有用
}

顺序表优点：下标随机访问

顺序表缺点：头部或中间插入删除效率低，扩容（有一定程度性能消耗，可能存在一定程度空间浪费）

链表优点：任意位置插入删除O(1)，按需申请释放

链表缺点：不支持下标随机访问