• 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
• 数据结构c++双向链表（首尾指针） 插入操作 #pragma once #include <iostream> using namespace std; template <class T> class DoubleLinkList; template <class T> class Node { public: ...
数据结构c++双向链表（首尾指针）
插入操作
#pragma once
#include <iostream>

using namespace std;

template <class T>

template <class T>
class Node
{
public:
Node(T data)
{
this->data = data;
pre = nullptr;
next = nullptr;
}

friend ostream& operator<<(ostream& os, Node<T>* node)
{
return os << node->data;
}
private:
T data;

Node<T>	*pre;		//上一节点

Node<T> *next;		//下一节点
};

template <class T>
{
public:
{
first = last = new Node<T>(-1);
size = 0;
}

bool is_empyt()
{
if (size == 0)
return true;
return false;
}

void Clear()
{
if (is_empyt())
return;
auto p = first->next;
Node<T>* temp = nullptr;
while (p!=last)
{
temp = p;
delete temp;
p = p->next;
}
last = first;		//重置末节点
size = 0;
}

void show_list()
{
if (is_empyt())
return;
auto p = first->next;
while (p != nullptr)
{
cout << p;
p = p->next;
}
}

Node<T>* get_node(int index)
{
if (is_empyt())
return nullptr;
if (index<0 || index>size)
return nullptr;
auto p = first->next;
for (int i=0;i<size;++i)
{
if(i==index)
break;
p = p->next;
}
return p;
}

void insert_index(T data, int index)
{
if (index<0 || index>size)
return;
auto node = new Node<T>(data);
if (size == 0)
{
node->pre = first;
first->next = node;
last = node;
}
else if (index == 0)
{
node->pre = first;			//把首节点赋值给新节点的前驱
node->next = first->next;	//将第一个节点赋值给新节点的后驱
first->next->pre = node;	//将新节点赋值给第一个节点的前驱
first->next = node;			//将新节点赋值给首节点的后驱
}
else if(index == size)
{
last->next = node;
node->pre = last;
last = node;
}
else
{
auto pre_node = get_node(index-1);		//当前节点的上一节点
node->pre = pre_node;
node->next = pre_node->next;
pre_node->next->pre = node;
pre_node->next = node;
}
++size;
}

void push_back(T data)
{
insert_index(data, size);
}

void push_front(T data)
{
insert_index(data, 0);
}

T pop_index(int index)
{
if (index<0 || index>size-1)
return -1;
Node<T>* node = nullptr;
if (index == 0)		//首
{
node = first->next;
first->next = node->next;
node->pre = first;
if (size == 1)
last = first;
}
else if (index == size-1)		//尾
{
node = last;
last = last->pre;
last->next = nullptr;
}
else	//中
{
node = get_node(index);		//当前位置节点
node->pre->next = node->next;
node->next->pre = node->pre;
}
T data = node->data;
delete node;
--size;
return data;
}

T pop_back()
{
return pop_index(size-1);
}

T pop_front()
{
return pop_index(0);
}
private:
Node<T>* first;

Node<T>* last;

int size;
};


展开全文
• 通过java实现的双向链表，及反转功能，可能对面试有用哦
• 创建空的双向链表； 逐字符读取键盘输入的合法...（【提示】：可以利用双向链表的头指针和尾指针，其中头指针往链表尾部移动，尾指针向链表头部方向移动。当头尾指针最后能相遇时，则可认为输入字符串是首尾对称的。）
• ## 双向链表

千次阅读 2019-07-29 15:35:37
双向链表：在单链表的结点中增加一个指向其前驱的pre指针；该链表中第一个结点的前趋结点为NULL，最后一个结点的后继结点为NULL 。 双向链表具有单链表的所有操作：创建、销毁、获取链表长度、清空、获取某个元素、...
为什么需要双向链表？

单链表的结点都只有一个指向下一个结点，单链表的数据元素无法直接访问其前驱元素，所以逆序访问单链表中元素极其耗时；

思想有点类似使用空间复杂度换时间复杂度。 双向链表：在单链表的结点中增加一个指向其前驱的pre指针；该链表中第一个结点的前趋结点为NULL，最后一个结点的后继结点为NULL 。
双向链表具有单链表的所有操作：创建、销毁、获取链表长度、清空、获取某个元素、插入元素、删除元素；
定义双向链表类型结构
typedef struct line{
struct line *prior;//指向直接前趋
int data;
struct line *next;//指向直接后继
}line;

初始化双向链表
line *initLine(line *head){
//给头结点分配内存
//初始化头结点
int i;
for(i=2;i<=5;i++){
//初始化结点
line *body = (line *)malloc(sizeof(line));  //创建并初始化一个结点
body->data =i;
body->prior =NULL;
body->next = NULL;
//新增结点
list->next = body; //直接将前趋结点的next指针指向新结点；@新增结点body为list的后继结点
body->prior = list; //新结点指向直接前趋结点；@新增结点body的前趋为list
}
}


插入元素操作
需要考虑插入元素位置，链表头部、中间、尾部
代码实现
删除操作
展开全文
• 双向链表的结点时结构体，有数据本体，指向前一元素的指针prev以及指向后一元素的指针next组成。这些结构体通过指针构成一个链表，就形成了双向链表。 struct node{ int key; node *prev,*next;//注意不是node...
首先当然得了解单向链表了
传送门
首先，表中的各个元素称作“结点”。双向链表的结点时结构体，有数据本体，指向前一元素的指针prev以及指向后一元素的指针next组成。这些结构体通过指针构成一个链表，就形成了双向链表。

struct node{
int key;
node *prev,*next;//注意不是node *prev,next
};
另外，在表头设置一个特殊节点可以简化链表的实现，将这个结点称为“头节点”，头节点中不包括实际数据，但它可以让我们更轻松地对链表做更改。
init函数用于初始化链表。它会生成一个NIL节点作为链表的头节点，然后让prev和next都指向这个头节点，从而创建一个空表。
node *nil;
void init()
{
nil=(node*)malloc(sizeof(node));
nil->next=nil;
nil->prev=nil;
}

然后就是很重要的插入元素。
void insert(int key)
{
node *x=(node*)malloc(sizeof(node));
x->key=key;
x->next=nil->next;
nil->next->prev=x;
nil->next=x;
x->prev=nil;
}

listsearch函数用于搜索元素，它可以在链表中寻找包含指定键值的结点，并返回其指针，假设cur为指向当前位置结点的指针，那么只要从头节点的next所指的结点，即链表开头的元素逐个进行cur=cur->next，即可逐一访问每个结点。

node* listsearch(int key)
{
node *cur=nil->next;
while(cur!=nil&&cur->key!=key){
cur=cur->next;
}
return cur;
}
deletenode函数删除指定结点t。

void deletenode(node *t)
{
if(t==nil){
return ;
}
t->prev->next=t->next;//修改前面的指向
t->next->prev=t->prev;//修改后面的指向
free(t);
}

void deletefirst()
{

deletefirst(nil->next);
}

void deletelast()
{
deletenode(nil->prev);
}

void deletekey(int key)
{
deletekey(listsearch(key));
}
deletelastfirst函数，deletelast函数分别用于删除头节点next，prev所指向的结点，deletekey函数可以删除包含指定key的结点，它可以先通过listsearch函数搜索出与key一致的结点t，然后再使用deletenode(t)删除该节点。
整体运用一下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

struct node{
int key;
node *prev,*next;
};

node *nil;
void init()
{
nil=(node*)malloc(sizeof(node));
nil->next=nil;
nil->prev=nil;
}

void insert(int key)
{
node *x=(node*)malloc(sizeof(node));
x->key=key;
x->next=nil->next;
nil->next->prev=x;
nil->next=x;
x->prev=nil;
}

void deleteNode(node*t)
{
if(t==nil){
return ;
}
t->prev->next=t->next;
t->next->prev=t->prev;
free(t);
}

void deleteFirst()
{
deleteNode(nil->next);
}

void deleteLast()
{
deleteNode(nil->prev);
}

node* listSearch(int key)
{
node *cur=nil->next;
while(cur!=nil&&cur->key!=key){
cur=cur->next;
}
return cur;
}

void deleteKey(int key)
{
deleteNode(listSearch(key));
}

void printList()
{
node*cur=nil->next;
int isf=0;
while(1){
if(cur==nil){
break;
}
if(isf++>0){
printf(" ");
}
printf("%d",cur->key);
cur=cur->next;
}
printf("\n");
}

int main()
{
int n,key;
char com[20];
scanf("%d",&n);
init();
for(int i=0;i<n;i++){
scanf("%s%d",com,&key);
if(com[0]=='i'){
insert(key);
}else if(com[0]=='d'){
if(strlen(com)>=6){
if(com[6]=='F'){
deleteFirst();
}else if(com[6]=='L'){
deleteLast();
}else{
deleteKey(key);
}
}
}
}
printList();
return 0;
}
/*
7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
*/


展开全文
• 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
• 定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x，y以及结点指针left及右结点指针right。 包含的函数成员包括： (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
• 复习链表时挺好的
• C语言数据结构 双向链表的建立与基本操作 双向链表比单链表有更好的灵活性，其大部分操作与...由于定义双向链表指针域中多了一个prior指针，插入操作相应变得复杂，但基本操作也并不难理解。只需记住在处理前驱和后
• ## 单链表、双向链表、循环链表

千次阅读 多人点赞 2019-07-26 14:26:09
学习三种常见的链表结构，他们分别是：单链表、双向链表和循环链表。 单链表 单链表有两个较特殊节点，头结点和尾节点。头结点用来记录链表的基地址，可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向...


文章目录
常见链表单链表双向链表循环链表单向循环链表双向循环链表

常见链表
学习三种常见的链表结构，他们分别是：单链表、双向链表和循环链表。
单链表
单链表有两个较特殊节点，头结点和尾节点。头结点用来记录链表的基地址，可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向一个空地址NULL，表示链表上的最后一个节点。
和数组一样，链表也支持数据的查找、插入和删除操作。但相对于数据的插入删除需要做大量的搬移操作，链表的插入，删除的时间复杂度为O(1)。但是链表想要随机访问第k个元素，就没有数组高效，随机访问数据的时间复杂度为O(n)。单向链表的简单实现代码如下：
/*
*****************************************************************************
*
*
*
*
* History:
*    Created:  Apri, 2019
*
*
****************************************************************************/

typedef struct _node{
struct _node *next;
int date;
}node, *list;

#endif

/*
*****************************************************************************
*
*
* Description: Single link list file
*
*
* History:
*    Created:  Apri, 2019
*
*
****************************************************************************/
#include <stdio.h>
#include <stdlib.h>

{

printf("malloc failed !!\n");
exit(1);
}
}

/*
insert a node to single link list
头插法
*/
{
list p = NULL;

if (NULL == list_) {
printf("list is NULL ...\n");
exit(1);
}
p = (list)malloc(sizeof(list));
if(p == NULL) {
printf("malloc failed \n");
exit(1);
}
p->date = date;

p->next = list_->next;
list_->next = p;

return 1;
}
/*
* 尾插法实现
*/
{
list p = NULL;

if (NULL == list_) {
printf("list is NULL ...\n");
exit(1);
}
p = (list)malloc(sizeof(list));
if(NULL == p) {
printf("malloc fialed !\n");
exit(1);
}
while(list_->next) {

list_ = list_->next;
}
p->date = date;
list_->next = p;
p->next = NULL;

return 1;

}

{
printf(" list is null ...\n");
return;
}
printf("date ---- > %d \n", head->date);
}

return;
}
/*
* delete element from tail of link list
* */
{
if(NULL == list_) {
printf("list is NULL ...\n");
exit(1);
}
if(list_->next == NULL) {
free(list_);
list_ = NULL;
}
while(list_->next->next) {
list_ = list_->next;
}
free(list_->next);
list_->next= NULL;

return ;
}
/*
* */
{
list p = NULL;
if(NULL == list_) {
exit(1);
}

if(list_->next) {
p = list_->next;
list_->next = p->next;
free(p);
}
return;
}
/*
*
* */
{
int size = 0;
if(NULL == list_) {
exit(1);
}
while(list_->next) {
++size;
list_ = list_->next;
}
return size;
}
void delete_specific_date(list list_, int date)
{
list p = NULL;
int size = 0;
if(NULL == list_) {
printf("list is NULL ...\n");
exit(1);
}
if (size <= 0) {
exit(1);
}
p = list_->next;
while(p->date != date) {
p = list_->next;
}

list_->next = p;
free(list_);

return;
}
int main()
{
int i;

#if 0
for (i = 0; i < 2; i++) {

}
#endif
}


双向链表
#ifndef DOUBLE_LINKLIST_

#include "stdbool.h"
typedef int ElementType;
ElementType date;

#endif

#include <stdio.h>
#include <stdlib.h>

/*
@func :创建头结点和尾结点，新增的节点插入头结点和尾结点之间
*/
{
perror("malloc failed.");
exit(1);
}
if (!pNew) {
perror("malloc failed.");
exit(1);
}
pNew->next = NULL;

}
/*
@func: 头插法，新增的节点插入头结点后面
*/
{
exit(1);
}
if (!pNew) {
perror("malloc failed.");
exit(1);
}
pNew->date = date;
/*先确定新增节点的前后指针指向*/

return true;
}
{
exit(1);
}
return true;
else
return false;
}
/*
@func: 删除一个节点
*/
{
exit(1);
}
exit(1);
}
ElementType val = pDel->date;

if (pDel) {
free(pDel);
pDel = NULL;
}
return val;
}

{
exit(1);
}
exit(1);
}
while (tmp->next != NULL) {
printf("val ---> %d\n", tmp->date);
tmp = tmp->next;
}
}
int main()
{
printf("delete val is %d .\n", delete(d_link));
printf("delete val is %d .\n", delete(d_link));

}

循环链表
单向循环链表
#ifndef ROBIN_LINKLIST_

#include "stdbool.h"
typedef int ElementType;
typedef struct _node {
ElementType date;
struct _node* next;

#endif

#include <stdio.h>
#include <stdlib.h>

{
perror("malloc failed.");
exit(1);
}
/*next指针指向自己*/
if (!node) {
perror("malloc failed.");
exit(1);
}
}
/*
@func : insert a element to linklist
*/
{
exit(1);
}
if (!node) {
perror("malloc failed.");
exit(1);
}
node->date = date;

return true;
}
/*
@func : delete a element from linklist
*/
{
exit(1);
}
return true;
}else {
return false;
}
}
{
exit(1);
}
printf("val ---> %d\n", tmp->date);
tmp = tmp->next;
}
}
int main()
{
/*test code*/

}


双向循环链表
#ifndef DOUBLE_ROBIN_LINKLIST_

#include "stdbool.h"

typedef int ElementType;
ElementType date;

#endif

#include <stdio.h>
#include <stdlib.h>

{
perror("malloc failed.");
exit(1);
}

/*创建尾节点*/
if (!tail) {
perror("malloc failed.");
exit(1);
}

}
{
exit(1);
}

return true;
}
else {
return false;
}
}
/*
@func： 头插法
*/
{
exit(1);
}
if (!pNew) {
perror("malloc is NULL.");
exit(1);
}
pNew->date = date;

return true;
}
/*
@func: 头删法
*/
{
exit(1);
}
exit(1);
}
ElementType val = pDel->date;

printf("delete ---> %d\n", val);
if(pDel) {
free(pDel);
pDel = NULL;
}
return val;
}

{
exit(1);
}
exit(1);
}
printf("val ---> %d\n", tmp->date);
tmp = tmp->next;
}
}
int main()
{
}

展开全文
• 指针双向链表逻辑结构单指针双向链表则需要采用异或链表的方式，下图是一个具有五个节点的双向链表的逻辑结构示意图，没有头结点。其中每个节点的后半部分表示指针域，存储了它的前驱节点的指针与后继借点的指针的...
• 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。 给你位于...
• 改进：不需要对每个结点的链域进行置空初始化，因为最后还是会重新赋值。只需要对头结点 L 初始化： L->prior = L； 原方法：每次选出最小元素，采用尾插法排序，较为繁琐，而且指针变量太多。新方法：每次选出...
• 对循环双链表实现下述功能： void meau(); //菜单函数 void Initlist(List *list); //初始化 void show(List *list); //打印链表内容 bool Push_back(List *list,ElemType x); //尾插法 b
• 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为...
• 双向链表基本操作函数头文件。包括创建链表，销毁链表，向前插入节点，向后插入节点，打印链表，清空链表，等
• 链表中的双指针，一般是指初始时设置两个移动指针，它们可能以不同的初始状态或不同的移动方式进行移动。 1.删除链表的倒数第N个节点 题目描述：给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。 ...
• 10.逆置（通过改变指针的方式将元素逆序）；11.按元素查找（查找指定元素是否存在）；12.按位置删（删除指定位置元素）；13.按元素删（删除指定元素）；14.清空（清除所有元素，但链表未销毁，还可以继续进行操作）...
• 双向链表：单向链表只能向着一个方向遍历链表节点，而在节点指针域中增加了前向指针双向链表，则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。 function DoublyLinkedList() { ...
• ## 双向链表（详解）

千次阅读 多人点赞 2020-10-19 02:09:10
双向链表操作 在学习了单链表之后，就顺带学习了双链表的操作。... 而在双向链表中，我们需要有两个指针域，一个负责向后连接，一个负责向前连接。 /* 单链表的结构 */ struct List{ int data; // 数据域 st
• ## 详解双向链表的基本操作(C语言)

万次阅读 多人点赞 2020-04-06 22:06:19
1.双向链表的定义 上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。 单向链表特点：   1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.   2.只能从头...
• 已知p指针，那么a结点的地址就在p指针所指结点的prior里存着， a结点要变成s的前驱， 所以要给s的Prior域赋值，赋的是a结点的地址，即p的prior。 接下来 将s结点变成a结点的后继，就要给a结点的...
• 添加（默认添加到双向链表的最后） （1）.先找到双向链表的最后这个节点（temp） （2）.temp.next = newHeroNode （3）.newHeroNode.pre = temp; 修改思路和单链表一样 删除 （1）.以为是双向链表，因此，我们可以...
• 指针异或运算实战二、异或指针双向链表的实现 一、异或运算的基本知识 1. 什么是异或运算 假设二进制数10跟二进制数01进行异或运算的时候，即10 ^ 01，从右往依次进行运算，相同情况的异或结果为0，否则为1。...
• 有个节点为e，指向他的指针为s①插入：想要把e插入到ai的后面，只需要把s的next指向p的next，再把p的next指向e就可以了②删除：想要删除ai+1节点，只需要把p的next指针指向p的next的next就可以了二、静态链表就是用...
• //从双向链表中删除一个节点 //说明 //1.对于双向链表，我们可以直接找到删除的这个节点 //2.找到后，自我删除即可 public void del(int no) { //判断当前链表是否为空 if (head.next==null){//空链表 System...
• 本文实例讲述了Python二叉搜索树与双向链表实现方法。分享给大家供大家参考，具体如下： # encoding=utf8 ''' 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点，...

...