带头结点的双向链表

声明单链表结点类型

//定义结点结构
typedef struct DCNode
{
	int data;
	struct DCNode *prior, *next;
}DCNode, *DCLinkList;

操作

链表初始化

//链表初始化
void  InitDCLinkList(DCLinkList plist)
{
	assert(plist != NULL);
		if(plist == NULL)
		{
			return;
		}
	plist->prior = plist ->next = plist;
}

为了实现以下插入，删除等一系列操作，先封装以下功能：

获取节点个数

int GetLength(DCLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
	{
		return -1;
	}

	int length = 0;
	DCLinkList p = plist->next;

	while(p != plist)
	{
		length++;
		p=p->next;
	}

	return length;
}

根据位置找结点

DCLinkList FindNode(DCLinkList plist,int pos)
{
	assert(plist != NULL);
		if(plist == NULL)
		{
			return NULL;
		}

		if(pos < 0)
		{
			return NULL;
		}

		DCLinkList p =plist;

		while(pos && p ->next != plist)
		{
			pos--;
			p = p->next;
		}

		if(pos == 0)
		{
			return p;
		}

		return NULL;
}

申请节点

static DCLinkList _ApplyNode(int val,DCLinkList  prior,DCLinkList next)
{
	DCLinkList s = (DCLinkList)malloc(sizeof(DCNode));
	assert(s != NULL);
	if (s == NULL)
	{
		return NULL;
	}

	s->data = val;	
	s->prior = prior;
	s->next = next;

    return s;
}

插入

void Insert(DCLinkList plist,int val,int pos)
{
	assert(plist != NULL);
		if(plist == NULL)
		{
			return;
		}

		DCLinkList p = FindNode(plist,pos);
		if(p == NULL)
		{
			return;
		}

     //完成插入结点的衔接
	DCLinkList t = _ApplyNode(val ,p, p->next);
	if(t == NULL)
	{
		return;
	}

	//pos位置下一个节点的prior和pos位置的next
		p->next->prior = t;
        p->next = t;
}

头插

void Insert_Head(DCLinkList plist,int val)
{
	Insert(plist,val,0);
}

尾插

void Insert_Tail(DCLinkList plist,int val)
{

	assert(plist != NULL);
		if(plist == NULL)
		{
			return;
		}

	DCLinkList t = _ApplyNode(val ,plist->prior, plist);

	if(t == NULL)
	{
		return;
	}

	 plist->prior->next = t;
	 plist->prior= t;
}

删除

void Delete(DCLinkList plist,int pos)
{
	assert(plist != NULL);
	if(plist == NULL)
	{
		return;
	}

	DCLinkList p = FindNode(plist,pos);
		if(p == plist || p == NULL)
	{
		return;
	}

	p->prior->next=p->next;
	p->next->prior = p->prior;

	free(p);
}

头删

void Delete_Head(DCLinkList plist)
{
	Delete(plist,1);
}

尾删

void Delete_Tail(DCLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
	{
		return;
	}

	if(ListEmpty(plist))//链表为空不需要删除
	{
		return;
	}
	DCLinkList p = plist->prior;
	p->prior->next=p->next;
	p->next->prior = p->prior;

	free(p);
}

判空

int ListEmpty(DCLinkList plist)
{
	if(plist == NULL || plist->next == plist)
	{
		return 1;
	}

	return 0;
}

置空

void Clear(DCLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
	{
		return ;
	}

	while(!ListEmpty(plist))
	{
		Delete_Head(plist);
	}
}

显示

void  Show(DCLinkList plist)
{
	assert(plist != NULL);
		if(plist == NULL)
		{
			return;
		}

		DCLinkList p = plist ->next;
		while(p != plist)
		{
			printf("%d——>",p->data);
			p=p->next;
		}
		printf("NULL\n");
}