关键词：
参考博客：
http://www.cnblogs.com/skywang12345/p/3561803.html
https://blog.csdn.net/howlaa/article/details/38513235
1、概述
线性表是一种线性结构，由数组、单项链表和双向链表组成，这里讲讨论双向链表的理论知识和实现代码。
双向链表和单项链表类似，双向链表由两个指针作为指针域，分别指向前驱节点和后驱节点。可以从任何节点开始向前或者向后删除、增加、查找节点。
双链表的示意图如下：
在插入节点的时候有两种方式：前插法和尾插法，这里介绍的是前插法。如下图所示：
注意，一定要理解这个图，不然理解后面代码的插入操作会有问题
代码描述：
1 void DInsertBefore(DListNode *p,DataType x) 2 //带头节点的双链表中，将值为X的新节点插入P之前，设P!=null 3 DListNode *s = malloc(sizeof(DListNode));//1、这个是申请一个新节点，用来放X的。 4 s->data = x;//2、把新节点的数据放为x 5 s->prior = p->prior;//3、这个是新节点的前驱节点接到原来P的前驱节点上 6 s->next = p;//4、新节点的后节点接到P上 7 p->prior->next = s;//5、这个是把P的前驱节点O的后继节点接到S上 8 p->prior = s;//6、把P的前驱节点接到S上。 9
2、代码编写：
doubleLink.h
#ifndef _DUBLE_LINK_ #define _DUBLE_LINK_ namespace DoubleLinkSpace template<class T> class Dnode public: T value; Dnode *prev; Dnode *next; public: Dnode() Dnode(T t, Dnode *prev, Dnode *next) value = t; this->prev = prev; this->next = next; ; template<class T> class DoubleLink public: DoubleLink(); ~DoubleLink(); int size(); bool is_empty(); T get_fist(); T get_last(); T get(int index); int insert(int index, T t); int insert_first(T t); int append_last(T t); int del(int index); int del_first(); int del_last(); private: int count; Dnode<T> *phead; Dnode<T> *get_node(int index); ; //构造函数 template<class T> DoubleLink<T>::DoubleLink() phead = new Dnode<T>(); phead->next = phead->prev = phead; count = 0; //析构函数 template<class T> DoubleLink<T>::~DoubleLink() Dnode<T> *ptmp; Dnode<T> *pnode = phead->next; //删除所有节点 while (pnode != phead) ptmp = pnode; pnode = pnode->next; delete ptmp; delete phead; //获取链表节点数 template<class T> int DoubleLink<T>::size() return count; //判断链表是否为空 template<class T> bool DoubleLink<T>::is_empty() return (count == 0) ? true : false; //二分查找实现链表节点查找 template<class T> Dnode<T> *DoubleLink<T>::get_node(int index) if (index < 0 || index >= count) return nullptr; if (index <= count / 2) int i = 0; Dnode<T>* pindex = phead->next; while (i < index) pindex = pindex->next; i++; return pindex; int j = 0; int rindex = count - index - 1; Dnode<T>* rpindex = phead->prev; while (j < rindex) rpindex = rpindex->prev; j++; return rpindex; //获取节点的数据域 template<class T> T DoubleLink<T>::get(int index) Dnode<T> *tmpNode = get_node(index); if (tmpNode != nullptr) return tmpNode->value; else T ret; return ret; //获取第一个节点值 template<class T> T DoubleLink<T>::get_fist(void) Dnode<T> *tmpNode = get_node(0); if (tmpNode != nullptr) return tmpNode->value; else return 0; //获取最后一个节点值 template<class T> T DoubleLink<T>::get_last(void) Dnode<T> *tmpNode = get_node(count - 1); if (tmpNode != nullptr) return tmpNode->value; else return 0; //前插法插入节点 template<class T> int DoubleLink<T>::insert(int index, T t) if (index == 0) return insert_first(t); Dnode<T> *pindex = get_node(index); Dnode<T> *pnode = new Dnode<T>(t, pindex->prev, pindex);//pnode->prev = pindex->prev;pnode->next = pindex pindex->prev->next = pnode; pindex->prev = pnode; count++; return 0; //在节点头插入 template<class T> int DoubleLink<T>::insert_first(T t) Dnode<T> *pnode = new Dnode<T>(t, phead, phead->next); phead->next->prev = pnode; phead->next = pnode; count++; return 0; //在节点尾插入 template<class T> int DoubleLink<T>::append_last(T t) Dnode<T> *pnode = new Dnode<T>(t, phead, phead->next); phead->prev->next = pnode; phead->prev = pnode; count++; return 0; //删除指定节点 template<class T> int DoubleLink<T>::del(int index) Dnode<T> *pindex = get_index(index); pindex->next->prev = pindex->prev; pindex->prev->next = pindex->next; delete pindex; count--; return 0; //删除头部节点 template<class T> int DoubleLink<T>::del_first() return del(0); //删除尾部节点 template<class T> int DoubleLink<T>::del_last() return del(count - 1); #endif
doubleLinkTest.cpp
#include <iostream> #include <string> #include "doubleLink.h" using namespace std; using namespace DoubleLinkSpace; // 双向链表操作int数据 void int_test() int iarr[4] = 10, 20, 30, 40 ; cout << "\\n----int_test----" << endl; // 创建双向链表 DoubleLink<int>* pdlink = new DoubleLink<int>(); pdlink->insert(0, 20); // 将 20 插入到第一个位置 pdlink->append_last(10); // 将 10 追加到链表末尾 pdlink->insert_first(30); // 将 30 插入到第一个位置 // 双向链表是否为空 cout << "is_empty()=" << pdlink->is_empty() << endl; // 双向链表的大小 cout << "size()=" << pdlink->size() << endl; // 打印双向链表中的全部数据 int sz = pdlink->size(); for (int i = 0; i<sz; i++) cout << "pdlink(" << i << ")=" << pdlink->get(i) << endl; void string_test() string sarr[4] = "ten", "twenty", "thirty", "forty" ; cout << "\\n----string_test----" << endl; // 创建双向链表 DoubleLink<string>* pdlink = new DoubleLink<string>(); pdlink->insert(0, sarr[1]); // 将 sarr中第2个元素 插入到第一个位置 pdlink->append_last(sarr[0]); // 将 sarr中第1个元素 追加到链表末尾 pdlink->insert_first(sarr[2]); // 将 sarr中第3个元素 插入到第一个位置 // 双向链表是否为空 cout << "is_empty()=" << pdlink->is_empty() << endl; // 双向链表的大小 cout << "size()=" << pdlink->size() << endl; // 打印双向链表中的全部数据 int sz = pdlink->size(); for (int i = 0; i<sz; i++) cout << "pdlink(" << i << ")=" << pdlink->get(i) << endl; struct stu int id; char name[20]; ; static stu arr_stu[] = 10, "sky" , 20, "jody" , 30, "vic" , 40, "dan" , ; #define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) ) void object_test() cout << "\\n----object_test----" << endl; // 创建双向链表 DoubleLink<stu>* pdlink = new DoubleLink<stu>(); pdlink->insert(0, arr_stu[1]); // 将 arr_stu中第2个元素 插入到第一个位置 pdlink->append_last(arr_stu[0]); // 将 arr_stu中第1个元素 追加到链表末尾 pdlink->insert_first(arr_stu[2]); // 将 arr_stu中第3个元素 插入到第一个位置 // 双向链表是否为空 cout << "is_empty()=" << pdlink->is_empty() << endl; // 双向链表的大小 cout << "size()=" << pdlink->size() << endl; // 打印双向链表中的全部数据 int sz = pdlink->size(); struct stu p; for (int i = 0; i<sz; i++) p = pdlink->get(i); cout << "pdlink(" << i << ")=[" << p.id << ", " << p.name << "]" << endl; int main() int_test(); // 演示向双向链表操作“int数据”。 string_test(); // 演示向双向链表操作“字符串数据”。 object_test(); // 演示向双向链表操作“对象”。 return 0;
3、测试结果
----int_test---- is_empty()=0 size()=3 pdlink(0)=30 pdlink(1)=20 pdlink(2)=10 ----string_test---- is_empty()=0 size()=3 pdlink(0)=thirty pdlink(1)=twenty pdlink(2)=ten ----object_test---- is_empty()=0 size()=3 pdlink(0)=[30, vic] pdlink(1)=[20, jody] pdlink(2)=[10, sky] 请按任意键继续. . .
java数据结构线性表之链表(代码片段)
目录（1）链表（2）单向链表（2.1）单向链表API设计（2.2）单向链表代码实现（3）双向链表（3.1）结点API设计（3.2）双向链表API设计（3.3）双向链表代码实现& 查看详情
java数据结构线性表之链表(代码片段)
目录（1）链表（2）单向链表（2.1）单向链表API设计（2.2）单向链表代码实现（3）双向链表（3.1）结点API设计（3.2）双向链表API设计（3.3）双向链表代码实现& 查看详情
数据结构与算法合集
数据结构【Java】大话数据结构(1)线性表之顺序存储结构 【Java】大话数据结构(2)线性表之单链表 【Java】大话数据结构(3)线性表之静态链表 【Java】大话数据结构(4)线性表之循环链表 【Java】大话数据结构(5)线... 查看详情
数据结构学习笔记二线性表之链表篇（双向链表）(代码片段)
链表根据带头不带头、单向或双向、循环非循环三个方面可组成成八种类型。这八种类型中仅有两种是我们常用的。第一种是单向不带头非循环链表，也就是单链表。单链表因为结构简单，但是实际操作比较复杂，所... 查看详情
数据结构与算法-线性表之循环链表(代码片段)
前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说... 查看详情
数据结构线性表之实现单循环链表(代码片段)
数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实... 查看详情
线性表之双向链表
一，双向链表的基础知识1.双向链表的概念 双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表的每个结点中都有两个指针域，一个指向其前驱结点，一个指向其后继结点。2.双向链表... 查看详情
数据结构与算法-自定义双向链表api(代码片段)
类名MyTowWayLinkeList构造方法名publicMyTowWayLinkeList()成员内部类publicclassNode；结点类成员方法publicvoidinsert(Tt)；往线性表添加一个元素publicvoidinsert(inti,Tt)；在指定位置添加一个元素publicvoidclear()；清空整个线性表&# 查看详情
算法习题---线性表之单链表的查找(代码片段)
...针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1，否则，只返回0。注意：这里的链表中没有给出链表长度哟二... 查看详情
数据结构(线性表之单链表)(代码片段)
文章目录🥇为何要使用链表🥇单链表是什么单链表的数据存储方式🥇单链表之创建链表🥇单链表之打印链表🥇单链表之计算链表长度🥇单链表之增删查改单链表之头插法单链表之尾插法单链表之把一个... 查看详情
数据结构学习总结线性表之单链表(代码片段)
一，回忆链表 链表，别名链式存储结构或单链表，用于存储逻辑关系为"一对一"的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。&nbs... 查看详情
双向链表简单实现--数据结构与算法纪录片第一记(代码片段)
从这个月开始得准备春招的东西，所以打算重新学习数据结构与算法，以后的博客就以这个为主。 今天是线性结构中的双向链表。 代码实现与测试： DoubleLinkNode： packagelinear.doublelink;/***@Description:链表节点结构... 查看详情
c语言严蔚敏数据结构线性表之链表实现(代码片段)
...近在考成都大学皇家计算机科学与技术专业，复习专业课数据结构，正好学习到线性结构中的线性表用链表这种存储结构来实现。 首先，数据结构包括1、数据的操作2、逻辑结构3、存储结构(数据结构三要素。 直接上代... 查看详情
数据结构线性表之实现单链表(代码片段)
数据结构线性表之实现单链表数据结构线性表之实现单链表相关文章单链表定义单链表相关操作数据结构线性表之实现单链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实现顺序表(三)数... 查看详情
算法习题---线性表之单链表逆序打印(代码片段)
...链表数据使用头插法，逆序排列，然后正序打印即可三：算法实现（这里使用方法一：递归实现简单易懂）#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib 查看详情
线性表之链表(代码片段)
单链表也是一种链式存取的线性表，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，以next指针指向下一个节点而链接起来，相比于顺序表，链表有着快速增加，删除节点的优势，其节点... 查看详情
数据结构与算法笔记——链表(单链表循环链表双向链表)(代码片段)
...1.2、链表定义链表（Linkedlist）是一种常见的基础数据结构，是一种线性表，但是不像顺序 查看详情
03线性表之链表(代码片段)
肚子饿了就要吃 ~ 嗝 ———路飞 1.本章重点链表表示和实现（单链表+双链表）链表的常见OJ题顺序表和链表的区别和联系2.为什么需要链表引子：顺序表的问题及思考(1)动态顺序表特点：插入数据，... 查看详情