数据结构—双向链表

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

1. 链表的种类

2. 最实用的两种链表类型

1. 链表的种类

由上面的组合可以知道链表由2^3种类型

2. 最实用的两种链表类型

2.1 单向不带头不循环链表—之前博客实现了

2.2 双向带头循环链表

3. 实现双向带头循环链表

3.1 创建头节点

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

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

3.2 实现双向循环功能—返回头指针

LTNode* ListInit()
{
	LTNode* phead = BuyListNode(-1);//给头的data随便给个初始值
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

3.3 尾插

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

	//ListInsert(phead, x);

}

3.4 头插

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;

    phead newnode next
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;

	//ListInsert(phead->next, x);
}

3.5 尾删

void ListPopBack(LTNode* phead)
{
	assert(phead);

	assert(phead->next != phead);
	//assert(!ListEmpty(phead));

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

	free(tail);

	tailPrev->next = phead;
	phead->prev = tailPrev;

	//ListErase(phead->prev);
}

3.6 头删

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

	ListErase(phead->next);
}

4 实现两个重要接口函数

随机插入接口函数ListInsert可以实现头插、尾插直接复用

随机删除接口函数ListErase可以实现头删、尾删直接复用

4.1 随机插入

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);

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

4.2 随机删除

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

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