双向链表与单链表的主要区别和完整实现代码。

---

前置文章：单链表

双向链表（DuLinkList）

存储结构

typedef struct DuLNode
{
	ElemType data; //数据域
	struct DuLNode* prior; //直接前驱
	struct DuLNode* next; //直接后继
}DuLNode, * DuLinkList;

与单链表主要区别

比单链表多了个头结点，因此可以从最后一个结点往前遍历
与单链表主要区别在 存储结构、初始化、插入和删除的方法上，其他的可通用

与单链表代码不同的地方：

/* 双向链表结构 */
typedef struct DuLNode
{
	ElemType data; //数据域
	struct DuLNode* prior; //直接前驱
	struct DuLNode* next; //直接后继
}DuLNode, * DuLinkList;

//初始化双链表 有头结点
Status InitList(DuLinkList& L)
{
	L = new DuLNode;
	L->prior = NULL;
	L->next = NULL;
	return 1;
}

/*
	双链表的取址（按位查找）: 时间复杂度O(n)
	参数一：要取址的双链表
	参数二：要取址的位置
	这是获取插入位置前一个的地址
	如果想把数据插入1号位置，就返回第1-1号位置的地址
*/
DuLNode* GetElem_Dul(DuLinkList L, int i)
{
	DuLNode* p = L;
	//if (p->next == NULL)//如果头结点L的后继为空，则返回头结点L的地址
	//{
	//	return p;
	//}
	int j = 0;
	while (p && j < i-1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return 0;
	}
	
	return p;
}
/*
	双链表的插入（按位序前插入）:时间复杂度O(n)
	参数一：要插入的双链表
	参数二：要插入的位置
	参数三：要插入的数据
	注意：成功：返回1；失败：返回0。
*/
Status ListInsert(DuLinkList& L, int i, ElemType e)
{
	DuLNode* p = GetElem_Dul(L, i);//获取插入位置的前驱结点
	DuLNode* s = new DuLNode; //创建新结点
	s->data = e;//新结点存放新数据e
	s->next = p->next;//改s的前驱和后继
	if (p->next != NULL)
	{
		p->next->prior = s;//p的指针指向新节点s
	}
	
	s->prior = p;//将p的指针指向的下一个数据地址赋值给新结点s的指针
	p->next = s;
	

	return 1;
}
/*
	双链表的删除:   时间复杂度O(n)
	参数一：要删除的双链表
	参数二：要删除的位置
	注意：成功：返回1；失败：返回0。
*/
Status ListDelete(DuLinkList& L, int i)
{
	DuLNode* p = L;//创建临时结点指向头结点，头结点不存数据
	int j = 0;//记录p指向的是第几个结点，第0个结点为头结点，头结点不存数据，只存地址
	while (p->next && (j < i - 1))//循环找到第i-1个结点的前一个结点
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || (j > i - 1))
	{
		return 0;
	}
	DuLNode* q = p->next;//创建新结点q,指向要删除的数据内存地址
	p->next->next->prior = p;//修改q->next的前驱
	p->next = p->next->next;//修改p的后继
	delete q;//释放q结点

	return 1;
}

完整实现代码

#include<iostream>
#include<string>

using namespace std;

/*
	双链表 Double Link List
	比单链表多了个头结点，因此可以从最后一个结点往前遍历
	
	与单链表主要区别在 存储结构、插入和删除的方法上，其他的可通用
*/

typedef int ElemType;
typedef int Status;

typedef struct DuLNode
{
	ElemType data; //数据域
	struct DuLNode* prior; //直接前驱
	struct DuLNode* next; //直接后继
}DuLNode, * DuLinkList;

//初始化双链表 有头结点
Status InitList(DuLinkList& L)
{
	L = new DuLNode;
	L->prior = NULL;
	L->next = NULL;
	return 1;
}

/*
	双链表的取值（按位查找）: 时间复杂度O(n)
	参数一：要取值的双链表
	参数二：要取值的位置
	参数三：待保存的对象
	注意：成功：返回1；失败：返回0。
*/
Status GetElem(DuLinkList L, int i, ElemType& e)
{
	DuLNode* p = L->next;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return 0;
	}
	e = p->data;
	return p->data;
}
/*
	双链表的取址（按位查找）: 时间复杂度O(n)
	参数一：要取址的双链表
	参数二：要取址的位置
	这是获取插入位置前一个的地址
	如果想把数据插入1号位置，就返回第1-1号位置的地址
*/
DuLNode* GetElem_Dul(DuLinkList L, int i)
{
	DuLNode* p = L;
	//if (p->next == NULL)//如果头结点L的后继为空，则返回头结点L的地址
	//{
	//	return p;
	//}
	int j = 0;
	while (p && j < i-1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return 0;
	}
	
	return p;
}

/*
	双链表的查找（按值查找）:   时间复杂度O(n)
	参数一：要查找的双链表
	参数二：要查找的数据
	注意：成功：返回下标地址；失败：返回NULL。
*/
DuLNode* LocateElem(DuLinkList L, ElemType e)
{
	DuLNode* p = L->next;//创建新结点，并指向第一块数据
	while (p && p->data != e)//如果p不为空且data != e,指向下一个
	{
		p = p->next;
	}
	return p;//找到e返回p的地址，没找到返回NULL
}

/*
	双链表的插入（按位序前插入）:时间复杂度O(n)
	参数一：要插入的双链表
	参数二：要插入的位置
	参数三：要插入的数据
	注意：成功：返回1；失败：返回0。
*/
Status ListInsert(DuLinkList& L, int i, ElemType e)
{
	DuLNode* p = GetElem_Dul(L, i);//获取插入位置的前驱结点
	DuLNode* s = new DuLNode; //创建新结点
	s->data = e;//新结点存放新数据e
	s->next = p->next;//改s的前驱和后继
	if (p->next != NULL)
	{
		p->next->prior = s;//p的指针指向新节点s
	}
	
	s->prior = p;//将p的指针指向的下一个数据地址赋值给新结点s的指针
	p->next = s;
	

	return 1;
}


/*
	双链表的删除:   时间复杂度O(n)
	参数一：要删除的双链表
	参数二：要删除的位置
	注意：成功：返回1；失败：返回0。
*/
Status ListDelete(DuLinkList& L, int i)
{
	DuLNode* p = L;//创建临时结点指向头结点，头结点不存数据
	int j = 0;//记录p指向的是第几个结点，第0个结点为头结点，头结点不存数据，只存地址
	while (p->next && (j < i - 1))//循环找到第i-1个结点的前一个结点
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || (j > i - 1))
	{
		return 0;
	}
	DuLNode* q = p->next;//创建新结点q,指向要删除的数据内存地址
	p->next->next->prior = p;//修改q->next的前驱
	p->next = p->next->next;//修改p的后继
	delete q;//释放q结点

	return 1;
}

int main()
{
	DuLinkList L;
	//初始化双链表
	InitList(L);
	//插入双链表
	for (int i = 1; i < 6; i++)
	{
		ListInsert(L, i, i);
	}
	//取值
	int e;
	for (int i = 1; i <= 5; i++)
	{
		cout << GetElem(L, i, e) << endl;
	}

	//查找
	cout << "5的地址为：" << LocateElem(L, 1) << endl;
	//删除
	ListDelete(L, 2);
	cout << "删除第一个元素1：" << endl;
	for (int i = 1; i < 5; i++)
	{
		cout << GetElem(L, i, e) << endl;
	}

	return 1;
}