备案控制台
开发者社区 人工智能 文章 正文

数据结构— —双向链表

2023-06-14 53
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构— —双向链表

数据结构— —双向链表


双向链表的算法实现


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


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


91db747eef804b0daa40d81a1059b5ac.png

其结构体定义：

typedef struct _LinkNode {


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


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


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


双向链表的初始


//前插法
bool DbListInsert_front(DbLinkList* &L, DbLinkNode *node){ if(!L || !node) return false;
//1.只有头节点
if(L->next==NULL){
typedef struct _DoubleLinkNode { int data; //结点的数据域
struct _DoubleLinkNode *next; //下一个节点的指针域 struct _DoubleLinkNode *prev; //上一个结点的指针域
}DbLinkNode, DbLinkList; //LinkList为指向结构体LNode的指针类型
bool DbInit_List(DbLinkList* &L)//构造一个空的双向链表L
{
L=new DbLinkNode; //生成新结点作为头结点，用头指针L指向头结点 if(!L)return false; //生成结点失败
L->next=NULL; //头结点的next指针域置空
L->prev=NULL; //头结点的指针域置空 L->data = -1; return true;
}

双向链表增加元素前插法

 node->next=NULL;                           11
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;
}


0617f37fffae41f6bffff9516cb606a6.png

尾插法

//尾插法
bool DbListInsert_back(DbLinkList* &L, DbLinkNode *node){ DbLinkNode *last = NULL; if(!L || !node) return false;
last = L;
while(last->next) last = last->next;
node->next = NULL;
last->next = node;
node->prev = last; return true; }

d5f4364e7465468f80aa4ca7a80b6ecb.png

任意位置插入

//指定位置插入
bool DbLink_Insert(DbLinkList* &L, int i, int &e){ if(!L||!L->next) return false; if(i<1) return false;
int j =0;
DbLinkList *p, *s;
p = L;
while(p && j<i){//查找位置为i的结点，p指向该结点 p = p->next;
j++;
}
if(!p || j!=i){ cout<<"不存在节点："<<i<<endl;
return false;
} cout<<"p: "<<p<<endl;
s=new DbLinkNode;//生成新节点
s->data = e;
s->next = p;
s->prev = p->prev;
p->prev->next = s;
p->prev = s;
return true;
}

双向链表的遍历

//双向链表的遍历输出
void DbLink_Print(DbLinkList* &L ){
DbLinkNode *p = NULL;
if(!L){
cout<<"链表为空."<<endl; return ;
}
p = L;
while(p->next){
cout<<p->next->data<<"\t";
p = p->next;
}
//逆向打印
cout<<endl<<"逆向打印"<<endl;
while(p){
cout<<p->data<<"\t";
p = p->prev;
}
cout<<endl;
}

双向链表获取元素

bool DbLink_GetElem(DbLinkList* &L, int i, int &e)//双向链表的取值
{
//在带头结点的双向链表L中查找第i个元素
//用e记录L中第i个数据元素的值
int index;
DbLinkList *p;
if(!L || !L->next) return false;
p = L->next;
index = 1;
while(p && index<i){//顺链表向后扫描，直到p指向第i个元素或p为空
p = p->next;
index++;
}
if(!p || index>i){ return false;  //i值不合法,i＞n或i<=0
}
e=p->data; return true;
}


11

双向链表删除元素

//任意位置删除
bool DbLink_Delete(DbLinkList* &L, int i) //双向链表的删除
{
DbLinkList *p;
int index = 0;
if(!L || !L->next){
cout<<"双向链表为空!"<<endl;
return false;
}
if(i<1) return false; //不能删除头节点
p=L;
while(p && index<i){
p = p->next;
index++;
}
if(!p){ //当节点不存在时，返回失败 return false;
}
p->prev->next=p->next; //改变删除结点前驱结点的next 指针域 if(p->next){
p->next->prev = p->prev; //改变删除节点后继节点的prev 指针域
}
delete p;         //释放被删除结点的空间
return true;
}

双向链表销毁

void DbLink_Destroy(DbLinkList* &L) //双向链表的销毁
{
//定义临时节点p指向头节点
DbLinkList *p = L;
cout<<"销毁链表!"<<endl;
while(p){
L=L->next;//L指向下一个节点 cout<<"删除元素: "<<p->data<<endl; delete p; //删除当前节点
p = L;   //p 移向下一个节点
}
}

完整代码实现：

#include <iostream>
#include <Windows.h>
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<i)
  {
    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;
}


文章标签：
算法
存储
关键词：
数据结构双向链表
数据结构链表
会飞的鱼-blog
目录
相关文章
过。
|
9天前
|
存储 Java
Java数据结构：链表
Java数据结构：链表
过。
21 2
TU^
|
13天前
|
存储 索引
数据结构~~链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
TU^
23 0
Skrrapper
|
7天前
|
缓存 算法
【数据结构】----链表--双向链表
【数据结构】----链表--双向链表
Skrrapper
13 0
Skrrapper
|
7天前
|
存储 缓存 算法
【数据结构】线性表----链表详解
【数据结构】线性表----链表详解
Skrrapper
15 0
过。
|
8天前
|
存储
数据结构——链表
数据结构——链表
过。
16 0
Sessy
|
8天前
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点.
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点
Sessy
17 1
碳基肥宅
|
9天前
|
Java
DAY-1 | Java数据结构之链表：删除无头单链表中等于给定值 val 的所有节点
力扣203题解：使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre，记录cur的前一个节点，遍历链表时，若cur.val!=key，pre和cur同时前进；若cur.val==key，则pre.next=cur.next，cur继续前进，确保pre不急于跟随以处理连续相同值的情况。遍历结束后，处理头节点可能需要删除的特殊情况。
碳基肥宅
21 0
wan__cheng
|
13天前
|
存储 缓存
数据结构（链表）
数据结构（链表）
wan__cheng
21 0
Vez&#39;nan的幸福生活
|
13天前
|
算法 测试技术
【数据结构与算法 | 基础篇】单向循环链表实现队列
【数据结构与算法 | 基础篇】单向循环链表实现队列
Vez&#39;nan的幸福生活
20 2
Vez&#39;nan的幸福生活
|
13天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
Vez&#39;nan的幸福生活
19 1