双向链表——设计与实现

1.双向链表可以完成普通链表的所有操作，并且解决了普通链表逆向遍历效率低的问题。

双向链表相对于普通链表没有多大提示，需要注意的就是插入删除操作时的异常处理，

插入删除0号节点的异常，第一次插入的异常，最后一次删除的异常。

直接代码

#ifndef __DLINKLIST_H__
#define __DLINKLIST_H__

typedef void DLinkList;
typedef struct DLinkListNode{
	struct DLinkListNode *next;
	struct DLinkListNode *pre;
}DLinkListNode;

DLinkList* DLinkList_Create();
void DLinkList_Destory(DLinkList *list);
int DLinkList_Length(DLinkList *list);
void DLinkList_Clear(DLinkList *list);
DLinkListNode* DLinkList_Get(DLinkList *list, int pos);
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos);
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos);



//new
DLinkListNode* DLinkList_DeleteNode(DLinkList *list, DLinkListNode *node);
DLinkListNode* DLinkList_Reset(DLinkList *list);
DLinkListNode* DLinkList_Current(DLinkList *list);
DLinkListNode* DLinkList_Next(DLinkList *list);
DLinkListNode* DLinkList_Pre(DLinkList *list);



#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DLinkList.h"

typedef struct _tag_DLinkList{
	DLinkListNode header;
	int length;
	DLinkListNode *slider;
}TDLinkList;


DLinkList* DLinkList_Create()
{
	TDLinkList *tlist;
	tlist = (TDLinkList *)malloc(sizeof(TDLinkList));
	if(NULL == tlist)
	{
		printf("DLinkList_Create err NULL == tlist)\n");
		return NULL;
	}
	memset(tlist, 0, sizeof(TDLinkList));
	return tlist;
}
void DLinkList_Destory(DLinkList *list)
{
	TDLinkList *tlist;
	if(NULL == list)
	{
		printf("DLinkList_Destory err (NULL == list)\n");
		return ;
	}
	tlist = (TDLinkList *)list;
	free(tlist);
	tlist = NULL;
	return ;
}
int DLinkList_Length(DLinkList *list)
{
	TDLinkList *tlist;
	if(NULL == list)
	{
		printf("DLinkList_Length err (NULL == list)\n");
		return -1;
	}
	tlist = (TDLinkList *)list;

	return tlist->length;
}
void DLinkList_Clear(DLinkList *list)
{
	TDLinkList *tlist;
	if(NULL == list)
	{
		printf("DLinkList_Length err (NULL == list)\n");
		return ;
	}
	tlist = (TDLinkList *)list;
	memset(tlist, 0, sizeof(TDLinkList));
	return ;
}
DLinkListNode* DLinkList_Get(DLinkList *list, int pos)
{
	TDLinkList *tlist;
	int i;
	DLinkListNode *current;
	if(NULL == list || pos < 0)
	{
		printf("DLinkList_Get err (NULL == list || pos < 0)\n");
		return NULL;
	}
	tlist = (TDLinkList *)list;
	if(pos >= tlist->length)
	{
		printf("DLinkList_Get err (tlist->length >= pos)\n");
		return NULL;
	}
	current = (DLinkListNode *)tlist;
	for(i = 0; i < pos; i++)
		current = current->next;

	return current->next;
}
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos)
{
	TDLinkList *tlist;
	int i;
	DLinkListNode *current, *next;
	if(NULL == list || NULL == node || pos < 0)
	{
		printf("DLinkList_Insert err (NULL == list || NULL == node || pos < 0)\n");
		return -1;
	}
	tlist = (TDLinkList *)list;
	if(pos > tlist->length)
		pos = tlist->length;
	current = (DLinkListNode *)tlist;
	for(i = 0; i< pos; i++)
		current = current->next;
	next = current->next;

	node->next = next;
	current->next = node;
	
	if(next != NULL)
	{
		next->pre = node;
		tlist->slider = node;
	}
	node->pre = current;

	if(current == (DLinkListNode *)tlist)
		node->pre = NULL;

	tlist->length++;

	return 0;
}
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos)
{
	TDLinkList *tlist;
	int i;
	DLinkListNode *current, *next, *ret;
	if(NULL == list || pos < 0)
	{
		printf("DLinkList_Delete err (NULL == list || pos < 0)\n");
		return NULL;
	}
	tlist = (TDLinkList *)list;
	if(pos >= tlist->length)
		pos = tlist->length-1;
	current = (DLinkListNode *)tlist;
	for(i = 0; i< pos; i++)
		current = current->next;
	ret = current->next;
	next = ret->next;

	current->next = next;

	if(next != NULL)
	{
		next->pre = current;
		if(current == (DLinkListNode *)tlist)
			next->pre = NULL;
	}
	tlist->length--;
	if(tlist->slider == ret)
		tlist->slider = ret->next;

	return ret;
}



DLinkListNode* DLinkList_DeleteNode(DLinkList *list, DLinkListNode *node)
{
	TDLinkList *tlist;
	int i;
	DLinkListNode *current;
	if(NULL == list || NULL == node)
	{
		printf("DLinkList_DeleteNode err ((NULL == list || NULL == node)\n");
		return NULL;
	}
	tlist = (TDLinkList *)list;
	current = (DLinkListNode *)tlist;
	for(i = 0; i < tlist->length; i++)
	{
		current = current->next;
		if(node == current)
		{
			DLinkList_Delete(list, i);
			return current;
		}
	}

	return NULL;
}

DLinkListNode* DLinkList_Reset(DLinkList *list)
{
	TDLinkList *tlist;
	if(NULL == list)
	{
		printf("DLinkList_Reset err ((NULL == list)\n");
		return NULL;
	}
	tlist = (TDLinkList *)list;
	tlist->slider = tlist->header.next;

	return tlist->slider;
}

DLinkListNode* DLinkList_Current(DLinkList *list)
{
	TDLinkList *tlist;
	if(NULL == list)
	{
		printf("DLinkList_Current err (NULL == list)\n");
		return NULL;
	}
	tlist = (TDLinkList *)list;

	return tlist->slider;
}

DLinkListNode* DLinkList_Next(DLinkList *list)
{
	TDLinkList *tlist;
	if(NULL == list)
	{
		printf("DLinkList_Next err (NULL == list)\n");
		return NULL;
	}
	tlist = (TDLinkList *)list;
	if(tlist->slider != NULL)
		tlist->slider = tlist->slider->next;

	return tlist->slider;
}

DLinkListNode* DLinkList_Pre(DLinkList *list)
{
	TDLinkList *tlist;
	if(NULL == list)
	{
		printf("DLinkList_Pre err (NULL == list)\n");
		return NULL;
	}
	tlist = (TDLinkList *)list;
	if(tlist->slider != NULL)
		tlist->slider = tlist->slider->pre;
	return tlist->slider;
}

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "DLinkList.h"



typedef struct _Teacher
{
	DLinkListNode node;
	int age;
	char name[64];
}Teacher;


typedef struct _Teacher2
{
	DLinkListNode node;
	int age;
	char name[64];
}Teacher2;

typedef struct _Teacher3
{
	DLinkListNode node;
	int age;
	char name[64];
	int age3;

}Teacher3;
void main()
{
	int		ret = 0, i = 0;
	DLinkList* list = NULL;
	Teacher *tmp;
	Teacher t1, t2, t3, t4,t5;
	t1.age = 31;
	t2.age = 32;
	t3.age = 33;
	t4.age = 34;
	t5.age = 35;

	list = DLinkList_Create();
	if(NULL == list)
	{
		return;
	}
	DLinkList_Insert(list, (DLinkListNode *)&t1, 0);
	DLinkList_Insert(list, (DLinkListNode *)&t2, 0);
	DLinkList_Insert(list, (DLinkListNode *)&t3, 0);
	DLinkList_Insert(list, (DLinkListNode *)&t4, 0);
	DLinkList_Insert(list, (DLinkListNode *)&t5, 0);


	do{	
	tmp = (Teacher *)DLinkList_Current(list);
	if(tmp != NULL)
	{
		printf("tmp->age = %d ",tmp->age);
		DLinkList_Next(list);
	}
	}while(tmp);

	printf("\n");

	DLinkList_Reset(list);


	for(i = 0; i < DLinkList_Length(list); i++)
	{
		Teacher *tmp = (Teacher *)DLinkList_Get(list, i);
		if(tmp == NULL)
			return;
		printf("tmp->age = %d ",tmp->age);
	}
	printf("\n");
	while(DLinkList_Length(list))
	{
		DLinkList_Delete(list, 0);
	}

	system("pause");

	return ;
}