数据结构— —双向链表

双向链表的算法实现

单链表中每个结点除了存储自身数据之后，还存储了下一个结点的地址，因此可以轻松访问下一个结点，以及后面的后继结点，但是如果想访问前面的结点就不行了，再也回不去了。例如删除结点 p 时，要先找到它的前一个结点 q，然后才能删掉 p 结点，单向链表只能往后走，不能向前走。如果需要向前走，怎么办呢？

可以在单链表的基础上给每个元素附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表称为双向链表.

 

其结构体定义：

typedef struct _LinkNode {

int data; //结点的数据域 struct _LinkNode *next; //下一个节点的指针域

struct _LinkNode *prev; //上一个结点的指针域

}LinkNode, LinkList; //LinkList 为指向结构体 LNode 的指针类型

双向链表的初始

双向链表增加元素前插法

 尾插法

 

任意位置插入

双向链表的遍历

双向链表获取元素

双向链表删除元素

双向链表销毁

完整代码实现：

#include 
#include 
 
using namespace std;
 
typedef struct _DbLinkList
{
	int data;//数据域
	struct _DbLinkList* prev;//前驱结点
	struct _DbLinkList* next;//后继结点
 
}DbLinkList, DbLinkNode;
 
bool DbLinkList_Init(DbLinkList*& L)
{
	//分配头结点
	L = new DbLinkNode;
 
	if (!L)
	{
		return false;
	}
 
	L->next = NULL;
	L->prev = NULL;
	L->data = -1;
	return true;
}
 
//头插
bool InsertDbLink_front(DbLinkList*& L, DbLinkList* node)
{
	if (!L || !node)
	{
		return false;
	}
 
	if (L->next == NULL)
	{
		node->next = NULL;
		node->prev = L;
		L->next = node;
	}
	else
	{
		L->next->prev = node;
		node->next = L->next;
		node->prev = L;
		L->next = node;
 
		//L->next->prev = node; //第二个节点的 prev 指向新节点
		//node->next = L->next; //新节点 next 指针指向第二个节点
		//node->prev = L; //新节点 prev 指针指向头节点
		//L->next = node;
	}
 
	return true;
}
 
//尾插
bool InsertDbLink_back(DbLinkList* &L, DbLinkNode* node)
{
	if (!L || !node)
	{
		return false;
	}
 
	DbLinkList* q;
	q = L;
 
	while (q->next)
	{
		q = q->next;
	}
 
	q->next = node;
	node->prev = node;
	return true;
}
 
//任意位置插入
bool DbLink_Insert(DbLinkList*& L,int i,int &e)
{
	DbLinkList* q, * s;
	int j = 1;
	
 
	q = L->next;
	
	if (!L || !L->next)
	{
		return false;
	}
 
	while (!q || j < i)
	{
		q = q->next;
		j++;
	}
 
	if (!q || i != j)
	{
		return false;
	}
 
	s = new DbLinkNode;
	s->data = e;
 
	q->prev->next = s;
	s->prev = q->prev;
	s->next = q;
	q->prev = s;
 
	return true;
}
 
//按指定位置查找元素
bool seekElem(DbLinkList*& L, int i, int& e)
{
	DbLinkList* p;
	int j = 1;
 
	p = L->next;
 
	if (!L || !L->next)
	{
		return false;
	}
 
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
 
	if (!p || j > i)
	{
		return false;
	}
 
	e = p->data;
 
	return true;
}
 
bool DbLink_Delete(DbLinkList*& L, int i)
{
	DbLinkNode* pos;
	int j = 1;
	pos = L->next;
 
	if (!L || !L->next)
	{
		return false;
	}
 
	if (i < 1)
	{
		return false;
	}
 
	while (!pos ||j
	{
		pos = pos->next;
		j++;
	}
 
	if (!pos)
	{
		return false;
	}
 
 
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
 
	delete pos;
 
	return true;
 
}
 
//链表的销毁
void DestroyLink(DbLinkList* &L)
{
	DbLinkNode* q = L;
 
	if (!L)
	{
		cout << "链表为空" << endl;
	}
 
	while (q)
	{
		L = L->next;
		delete q;
		q = L;
	}
 
	cout << "链表销毁了" << endl;
}
 
void DbLink_Print(DbLinkList*& L)
{
	DbLinkNode* s = NULL;
	s = L;
	
	if (!L)
	{
		cout << "链表为空." << endl;
		return;
	}
 
	while (s->next)
	{
		s = s->next;
		cout << s->data << "\t";
	}
	cout << endl;
 
	while (s!=L)
	{
		cout << s->data << "\t";
		s = s->prev;
	}
	cout << endl;
}
 
int main(void)
{
	DbLinkList* L, * s, * a;
 
	//双向链表初始化
	if (DbLinkList_Init(L))
	{
		cout << "初始化循环链表成功" << endl;
	}
	else
	{
		cout << "初始化循环链表失败" << endl;
	}
 
	//前插
	int j;
	
	cout << "请输入你要插入的个数：";
	cin >> j;
 
	for (int i = 0; i < j; i++)
	{
		s = new DbLinkNode;
		cin >> s->data;
		InsertDbLink_front(L, s);
	}
	DbLink_Print(L);
	
	//尾插
	int z;
 
	cout << "请输入你要插入的个数：";
	cin >> z;
 
	for (int i = 0; i < z; i++)
	{
		a = new DbLinkNode;
		cin >> a->data;
		InsertDbLink_front(L, a);
	}
	DbLink_Print(L);
 
	//任意位置插入
	int element, w;
 
	cout << "请输入你要插入的数：";
	cin >> w;
 
	cout << "请输入你要插入的位置：";
	cin >> element;
 
	DbLink_Insert(L, element, w);
	DbLink_Print(L);
 
 
	//查找元素
	int b;
 
	cout << "请输入你要查找元素的位置：";
	cin >> b;
 
	seekElem(L, b, element);
	cout << element << endl;
 
	//删除指定位置的元素
	
	DbLink_Delete(L, 3);
	DbLink_Print(L);
 
	//销毁链表
	DestroyLink(L);
	DbLink_Print(L);
 
	system("pause");
	return 0;
}