1. Toy模板网首页
  2. > Toy博客

数据结构-双向链表(c++)超全超详细

9月前 作者：别，爱℡ 分类：Toy博客 阅读(44) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构-双向链表(c++)超全超详细。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入，删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

提示：以下是本篇文章正文内容，下面案例可供参考

一、双向链表是什么？

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prev和next，分别指向其前驱结点和后继结点。
数据结构-双向链表(c++)超全超详细

二、双向链表上的基本操作

1.定义双向链表

代码如下（示例）：

typedef struct DoubleLinkList {

	int data;		//结点的数据域

	DoubleLinkList* next;	//下一个结点的指针域

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

}DoubleLinkList,DoubleLinkNode;

2.初始化双链表

代码如下（示例）：

bool DoubleLinkListInit(DoubleLinkList* &L) {	//构造一个空的双向链表

	L = new DoubleLinkNode;	//生成新结点作为头结点，用头指针L指向新结点
	if (!L)return false;		//生成结点失败

	L->next = NULL;		//头结点的next指针域指空
	L->prev = NULL;		//头结点的prev指针域指空
	L->data = -1;

	return true;
}

3.前插法创建双链表

代码如下（示例）：

bool DoubleLinkListInsertFront(DoubleLinkList*& L, DoubleLinkNode* node) {

	if (!L || !node) return false;

	
	if (L->next == NULL) {//只有头结点
		node->next = NULL;
		node->prev = L;		//新结点的prev指针指向头结点
		L->next = node;		//头结点的next指针指向新结点
	}
	else {
		L->next->prev = node;	//第二个结点的prev指向新结点
		node->next = L->next;	//新结点的next指向第二个结点
		node->prev = L;			//新结点的prev指向第一个结点
		L->next = node;			//第一个结点的next指向新结点
	}
	return true;
}

4.尾插法创建双链表

代码如下（示例）：

bool DoubleLinkListInsertBack(DoubleLinkList*& L, DoubleLinkNode* node) {

	DoubleLinkNode* last = NULL;

	if (!L || !node) return false;

	last = L;

	while (last->next) last = last->next;

	node->next = NULL;
	node->prev = last;
	last->next = node;

	return true;
}

5.双向链表的遍历输出

代码如下（示例）：

void DoubleLinkListPrint(DoubleLinkList* &L) {

	DoubleLinkNode* p=L;

	if (!L) {
		cout << "链表为空" << endl;
		return;
	}

	cout << p->data << "  ";
	while (p->next) {
		cout << p->next->data << "  ";
		p = p->next;
	}

	//逆向打印
	cout << endl << "逆向打印" << endl;
	while (p) {
		cout << p->data << " ";
		p = p->prev;
	}
	cout << endl;

	return;
}

6.双链表的指定位置插入

代码如下（示例）：

bool DoubleLinkListInsert(DoubleLinkList* L,int i,int e) {

	if (!L || !L->next) return false;
	if (i < 1)return false;

	int j = 0;
	DoubleLinkList* p, * s;
	p = L;

	while (p && j < i) {//查找位置为i的结点，p指向该结点
		p = p->next;
		j++;
	}

	if (!p || j != i) {
		cout << "结点不存在" << i << endl;
		return false;
	}

	s = new DoubleLinkNode;
	s->data = e;

	s->next = p;
	s->prev = p->prev;

	p->prev->next = s;
	p->prev = s;

	return true;
}

7.双链表的按位取值

代码如下（示例）：

bool DoubleLinkListGetElem(DoubleLinkList* &L,int i,int& e) {

	int index;
	DoubleLinkList* p;

	if (!L || !L->next) return false;

	p = L->next;
	index = 1;

	while (p || index < i) { //链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;		//p指向下一个结点
		index++;				//计数器index加1
	}

	if (!p || index > i) {
		return false;   //i值不合法，i>n或i<=0
	}

	e = p->data;

	return true;
}

8.双链表的任意位置删除

代码如下（示例）：

bool DoubleLinkListDelete(DoubleLinkList*& L, int i) {

	DoubleLinkList* p;
	int index = 0;

	if (!L || !L->next) {
		cout << "双向链表为空！" << endl;
		return false;
	}
	if (i < 1) {
		cout << "不能删除头结点!" << endl;
		return false;
	}
	p = L;

	while (p && index < i) {
		p = p->next;
		index++;
	}
	if (!p)return false; //当结点不存在时，返回失败

	p->prev->next = p->next;
	if(p->next!=nullptr)
		p->next->prev = p->prev;

	delete p;

	return true;
}

9.双链表的销毁

代码如下（示例）：文章来源地址https://www.toymoban.com/news/detail-403786.html

void DoubleLinklistDestroy(DoubleLinkList*  &L) {

	DoubleLinkList* p = L;
	cout << "销毁链表" << endl;

	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

}

三、全部代码(主函数部分比较凌乱）

#include<iostream>
using namespace std;

typedef struct DoubleLinkList {

	int data;		//结点的数据域

	DoubleLinkList* next;	//下一个结点的指针域

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

}DoubleLinkList,DoubleLinkNode;


bool DoubleLinkListInit(DoubleLinkList* &L) {	//构造一个空的双向链表

	L = new DoubleLinkNode;	//生成新结点作为头结点，用头指针L指向新结点
	if (!L)return false;		//生成结点失败

	L->next = NULL;		//头结点的next指针域指空
	L->prev = NULL;		//头结点的prev指针域指空
	L->data = -1;

	return true;
}


//前插法
bool DoubleLinkListInsertFront(DoubleLinkList*& L, DoubleLinkNode* node) {

	if (!L || !node) return false;

	
	if (L->next == NULL) {//只有头结点
		node->next = NULL;
		node->prev = L;		//新结点的prev指针指向头结点
		L->next = node;		//头结点的next指针指向新结点
	}
	else {
		L->next->prev = node;	//第二个结点的prev指向新结点
		node->next = L->next;	//新结点的next指向第二个结点
		node->prev = L;			//新结点的prev指向第一个结点
		L->next = node;			//第一个结点的next指向新结点
	}
	return true;
}


//尾插法
bool DoubleLinkListInsertBack(DoubleLinkList*& L, DoubleLinkNode* node) {

	DoubleLinkNode* last = NULL;

	if (!L || !node) return false;

	last = L;

	while (last->next) last = last->next;

	node->next = NULL;
	node->prev = last;
	last->next = node;

	return true;
}


//双向链表的遍历输出
void DoubleLinkListPrint(DoubleLinkList* &L) {

	DoubleLinkNode* p=L;

	if (!L) {
		cout << "链表为空" << endl;
		return;
	}

	cout << p->data << "  ";
	while (p->next) {
		cout << p->next->data << "  ";
		p = p->next;
	}

	//逆向打印
	cout << endl << "逆向打印" << endl;
	while (p) {
		cout << p->data << " ";
		p = p->prev;
	}
	cout << endl;

	return;
}


//指定位置插入
bool DoubleLinkListInsert(DoubleLinkList* L,int i,int e) {

	if (!L || !L->next) return false;
	if (i < 1)return false;

	int j = 0;
	DoubleLinkList* p, * s;
	p = L;

	while (p && j < i) {//查找位置为i的结点，p指向该结点
		p = p->next;
		j++;
	}

	if (!p || j != i) {
		cout << "结点不存在" << i << endl;
		return false;
	}

	s = new DoubleLinkNode;
	s->data = e;

	s->next = p;
	s->prev = p->prev;

	p->prev->next = s;
	p->prev = s;

	return true;
}


//双向链表按位取值
bool DoubleLinkListGetElem(DoubleLinkList* &L,int i,int& e) {

	int index;
	DoubleLinkList* p;

	if (!L || !L->next) return false;

	p = L->next;
	index = 1;

	while (p || index < i) { //链表向后扫描，直到p指向第i个元素或者p为空
		p = p->next;		//p指向下一个结点
		index++;				//计数器index加1
	}

	if (!p || index > i) {
		return false;   //i值不合法，i>n或i<=0
	}

	e = p->data;

	return true;
}


//任意位置删除
bool DoubleLinkListDelete(DoubleLinkList*& L, int i) {

	DoubleLinkList* p;
	int index = 0;

	if (!L || !L->next) {
		cout << "双向链表为空！" << endl;
		return false;
	}
	if (i < 1) {
		cout << "不能删除头结点!" << endl;
		return false;
	}
	p = L;

	while (p && index < i) {
		p = p->next;
		index++;
	}
	if (!p)return false; //当结点不存在时，返回失败

	p->prev->next = p->next;
	if(p->next!=nullptr)
		p->next->prev = p->prev;

	delete p;

	return true;
}


//销毁双向链表
void DoubleLinklistDestroy(DoubleLinkList*  &L) {

	DoubleLinkList* p = L;
	cout << "销毁链表" << endl;

	while (p) {
		L = L->next; //L指向下一个结点
		delete p;   //删除当前结点
		p = L;     //p移向下一个结点
	}

}








int main() {
	
	DoubleLinkList* L;
	DoubleLinkList* s;

	//1.初始化一个空的双向链表
	if (DoubleLinkListInit(L)) {
		cout << "初始化链表成功!" << endl;
	}
	else {
		cout << "初始化链表失败！" << endl;
	}

	//2.使用前插法插入数据
	int n;

	cout << "使用前插法创建双向链表" << endl;
	cout << "请输入元素个数：";
	cin >> n;
	cout << endl << "依次输入" << n << "个元素: ";

	while (n > 0) {
		s = new DoubleLinkNode;
		cin >> s->data;
		DoubleLinkListInsertFront(L, s);
		n--;
	}

	DoubleLinkListPrint(L);

	//3.使用尾插法插入数据
	
	cout << "使用尾插法创建双向链表" << endl;
	cout << "请输入元素个数：";
	cin >> n;
	cout << endl << "依次输入" << n << "个元素: ";

	while (n > 0) {
		s = new DoubleLinkNode;
		cin >> s->data;
		DoubleLinkListInsertBack(L, s);
		n--;
	}


	DoubleLinkListPrint(L);

	//4.任意位置插入元素
	for (int j = 0; j < 3; j++) {
		int i, x;
		cout << "请输入要插入的位置和元素(用空格隔开):";
		cin >> i >> x;

		if (DoubleLinkListInsert(L, i, x)) {
			cout << "插入成功！" << endl;
		}
		else {
			cout << "插入失败！" << endl;
		}
		DoubleLinkListPrint(L);
	}

	//5.双向链表删除元素
	if (DoubleLinkListDelete(L, 2)) {
		cout << "删除链表第2个元素成功" << endl;
	}
	else
		cout << "删除链表第2个元素失败！" << endl;


	DoubleLinkListPrint(L);

	//6.销毁链表
	DoubleLinklistDestroy(L);


	return 0;
}

总结

以上就是今天要讲的内容，本文仅仅简单介绍了双向链表的基本操作，如有错误，欢迎大家指针，看完记得点个赞。

到了这里，关于数据结构-双向链表(c++)超全超详细的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】双向链表 超详细 （含：何时用一级指针或二级指针；指针域的指针是否要释放）

    【数据结构】双向链表 超详细 （含：何时用一级指针或二级指针；指针域的指针是否要释放）

    目录 一、简介 二. 双链表的实现 1.准备工作及其注意事项 1.1 先创建三个文件 1.2 注意事项：帮助高效记忆 1.3   关于什么时候 用 一级指针接收，什么时候用 二级指针接收？ 1.4 释放节点时，要将节点地址 置为NULL，难道 节点内部的 指针域的指针 就不用置为 NULL吗？  2.双链

    2024年02月20日
    浏览(87)
  • 数据结构-链表结构-双向链表

    数据结构-链表结构-双向链表

    双向链表也叫双链表，与单向链表不同的是，每一个节点有三个区域组成：两个指针域，一个数据域 前一个指针域：存储前驱节点的内存地址 后一个指针域：存储后继节点的内存地址 数据域：存储节点数据 以下就是双向链表的最基本单位 节点的前指针域指向前驱，后指针

    2024年02月04日
    浏览(44)
  • 【数据结构】双向奔赴的爱恋 --- 双向链表

    【数据结构】双向奔赴的爱恋 --- 双向链表

    关注小庄 顿顿解馋๑ᵒᯅᵒ๑ 引言：上回我们讲解了单链表(单向不循环不带头链表)，我们可以发现他是存在一定缺陷的，比如尾删的时候需要遍历一遍链表，这会大大降低我们的性能，再比如对于链表中的一个结点我们是无法直接访问它的上一个结点，那有什么解决方法呢

    2024年04月08日
    浏览(93)
  • 数据结构——双向链表

    数据结构——双向链表

    🍇系列专栏：🌙数据结构 🍉  欢迎关注：👍点赞🍃收藏🔥留言 🍎 博客主页：🌙_麦麦_的博客_CSDN博客-领域博主 🌙如果我们都不能够拥有黑夜，又该怎样去仰望星空？   目录 一、前言 二、正文——双向链表的实现 2.1模块化 2.2 数据类型与结构体定义  2.3链表的初始化

    2024年02月02日
    浏览(47)
  • 数据结构双向链表

    数据结构双向链表

    Hello，好久不见，今天我们讲链表的双向链表，这是一个很厉害的链表，带头双向且循环，学了这个链表，你会发现顺序表的头插头删不再是一个麻烦问题，单链表的尾插尾删也变得简单起来了，那废话不多说，让我们开始我们的学习吧！ 首先我们要了解它的物理和逻辑结构

    2024年02月11日
    浏览(44)

  • 数据结构---双向链表

    单向链表：一块内存指向下一个内存。 单链表存在一些缺陷： 1.查找速度慢。 2.不能从后往前找。 3.找不到前驱。 链表的结构分为8种： 1.单向和双向 2.带头和不带头 带头的链表有一个带哨兵位的头结点，这个节点不存储有效数据。 好处 ：尾插更方便，不需要二级指针了，

    2024年02月02日
    浏览(45)
  • 数据结构 - 双向链表

    数据结构 - 双向链表

    文章目录 目录 文章目录 前言 一、什么是双向链表? 双向链表有什么优势? 二、双向链表的设计和实现 1.设计思想 尾增 : 在链表的末尾添加新的元素  头插 : 在链表头部插入节点  删除 : 根据val的值删除节点  查找 : 根据索引的值查找并返回节点 总结 大家好,今天给大家讲解

    2024年02月09日
    浏览(37)
  • 数据结构-双向链表

    数据结构-双向链表

    在单链表那一篇博客中介绍了单链表和双向链表的优缺点，所以此篇博客直接分享怎样实现一个带头双向循环链表。 单链表博客： 首先我们需要写一个结构体，双向带头链表的话需要一个前驱指针prev和一个后驱指针next，前驱指针的作用是方便找尾节点，因为头节点的prev指

    2024年02月05日
    浏览(48)
  • 数据结构—双向链表

    数据结构—双向链表

    目录 1.  链表的种类 2.  最实用的两种链表类型 3.  实现双向带头循环链表                   3.1 创建头节点         3.2 实现双向循环功能—返回头指针         3.3  尾插           3.4 头插         3.5 尾删         3.6 头删 4.  实现两个重要接口函数  

    2023年04月23日
    浏览(67)
  • 数据结构——实现双向链表

    数据结构——实现双向链表

    怎么说呢？光乍一听名字好像很难的样子是吧，那如果你这样认为的话，可就要让你大跌眼镜了哦，其实双向带头循环链表从操作和理解上来说都是要易于单项不带头不循环链表（俗称单链表）的。 咱们就来见识见识吧！希望真的能让你们“大跌眼镜”哈！ 双向带头循环链

    2024年02月07日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包