【数据结构】双向链表

一、双向链表

1.双向链表的结构设计

typedef struct DNode {
	int data;
	struct DNode* next; //后继指针
	struct DNode* prio; //前驱指针
	}DNode， *DList;

2.双向链表的结构示意图：

3.双向链表的实现

//初始化
void InitList(DList plist)
{
	assert(plist != NULL);
	plist->next = NULL;
	plist->prio = NULL;
}
//头插
bool Insert_head(DList plist, int val)
{
	assert(plist != NULL);
	DNode *p = (DNode*)malloc(sizeof(DNode));
	assert(p != NULL);
	p->data = val;
	p-<next = plist->next;
	plist->next = p;
	p->prio = plist;
	if(p->next != NULL) //多级指针记住判断
	{
		p->next->prio = p;
	}
}
//尾插
bool Insert_tail(DList plist, int val)
{
	assert(plist != NULL);
	DNode* p = (DNode*)malloc(sizeof(DNode);
	assert(p != NULL);
	p.data = val;
	DNode *q = plist;
	for(; q->next != NULL; p = p->next;)
	{
		;
	}
	p->next = q->next;
	q->next = p;
	p->prio = q;
	return true;
}
//查找第一个key值，返回节点地址，否则返回NULL
DNode* Search(DList plist, int key)
{
	assert(plist != NULL);
	DNode *p = plist->next;
	for(; p != NULL; p = p->next)
	{
		if(p->data = key)
			return p;
	}
	return NULL;
}
//删除第一个val的值
bool DelVal(DList plist, int val)
{
	assert(plist != NULL);
	DNode *p = Search(plist, val);
	p->prio->next = p->next;
	if(p->next != NULL) //多级指针
	{
		p->next->prio = p->prio;
	}
	free(p);
}
//销毁整个内存
void Destroy(DList plist)
{
	assert(plist != NULL);
	DNode *p = plist->next;
	for(; p != NULL; p=p->next)
	{
		plist->next = p->next;
		free(p);
}

4.双向链表的总结

双向链表其实和单链表一样，就是把；两条方向的单链表都处理好就行。
双向链表的考点就是多级指针，一定要注意判断