AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构：双向链表

2016-09-18 639
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
可视分析地图（DataV-Atlas），3 个项目，100M 存储空间
简介： 原创：转载请注明 在前面介绍了单项链表， http://blog.itpub.net/7728585/viewspace-2125007/ 在实际的应用中双向链表应用也是非常多的，因为我本生是一名DBA，我知道的在数据库中双向链表应用非常广泛，在双向链表中 我们多了一个*prior 指向前一个节点，那么这样如果我们已知一个节点的指针要求得上一个节点的指针就变得非常简单了， 时间复杂度由O(n)下降到一个常数O(1),关于这个实现函数我觉得没必要写了太简单了。
原创：转载请注明
在前面介绍了单项链表，
http://blog.itpub.net/7728585/viewspace-2125007/
在实际的应用中双向链表应用也是非常多的，因为我本生是一名DBA，我知道的在数据库中双向链表应用非常广泛，在双向链表中
我们多了一个*prior 指向前一个节点，那么这样如果我们已知一个节点的指针要求得上一个节点的指针就变得非常简单了，
时间复杂度由O(n)下降到一个常数O(1),关于这个实现函数我觉得没必要写了太简单了。我准备实现如下一些函数及功能
bool makenode(int datavalue,DULNODEP* p); //makenode next and prior is NULL
void freenode(DULNODEP p); //freenode
bool initlist(LISTHEADP* p); //initlist with no node head last current pointor is NULL
void destroylist(LISTHEADP p); //destroy a list,every list thing is not live
void clearlist(LISTHEADP p);//clear a list,but head is live and head last current pointor is NULL length=0
void insfirst(LISTHEADP h,DULNODEP s);//insfirst  insert one node at first postion length=0
void delfirst(LISTHEADP h); //delete first node current_point to next node
void inslast(LISTHEADP h,DULNODEP s); //inslast  insert one node at last postion
void dellast(LISTHEADP h) ; //delete last node current_point to prior node
void addnode(DULNODEP inode,int postion,LISTHEADP h);//insert one node after postion 
void removenode(int postion,LISTHEADP h) ;//delete node at give postion 
void replacenode(int postion,LISTHEADP h,DULNODEP inode);//replace one node
void viewchain(LISTHEADP h);//show info for chain
void viewheadinfo(LISTHEADP h);//only show head info

我将上一节演示的头结点增加了last指针指向最后一个节点，同时增加了current指针指向操作的指针。结构体如下：
typedef struct listhead
{
        DULNODEP head;
        DULNODEP last;
        DULNODEP current;
        int length;
} LISTHEAD,*LISTHEADP;

这样我们在实现 inslast和 dellast的时候变得非常简单了，而 delfirst和 insfirst本来就是通过head指针实现的，如果大家对栈和队列的实现有了解，着4个函数可以用来实现他们，这个我会在随后进行说明，这里只考虑双线链表，我基本上用注释解释了全部了功能下面一张图大概看看双向链表的结构，假设Noden为插入的节点就是如下，删除也差不多没画


下面以代码的方式给出实现：

点击(此处)折叠或打开

  1. 头文件：
  2. //error(1):delfirst() error list have no
  3. //error(2):getelemp() postion large than lenth or poastion = 0
  4. //error(3):viewchain() list no data

  6. #ifndef _liststr_
  7. #define _liststr_
  8. #define bool int
  9. #define true 1
  10. #define false 0
  11. typedef struct dulnode //node type
  12. {
  13.         int data; //example
  14.         struct dulnode *prior;
  15.         struct dulnode *next;
  16. } DULNODE,*DULNODEP;

  18. typedef struct listhead
  19. {
  20.         DULNODEP head;
  21.         DULNODEP last;
  22.         DULNODEP current;
  23.         int length;
  24. } LISTHEAD,*LISTHEADP;

  26. #define SIZENODE sizeof(DULNODE)
  27. #define SIZELISTHEAD sizeof(LISTHEAD)

  29. bool makenode(int datavalue,DULNODEP* p); //makenode next and prior is NULL
  30. void freenode(DULNODEP p); //freenode
  31. bool initlist(LISTHEADP* p); //initlist with no node head last current pointor is NULL
  32. void destroylist(LISTHEADP p); //destroy a list,every list thing is not live
  33. void clearlist(LISTHEADP p);//clear a list,but head is live and head last current pointor is NULL length=0
  34. void insfirst(LISTHEADP h,DULNODEP s);//insfirst insert one node at first postion length=0
  35. void delfirst(LISTHEADP h); //delete first node current_point to next node
  36. void inslast(LISTHEADP h,DULNODEP s); //inslast insert one node at last postion
  37. void dellast(LISTHEADP h) ; //delete last node current_point to prior node
  38. void addnode(DULNODEP inode,int postion,LISTHEADP h);//insert one elem after postion
  39. void removenode(int postion,LISTHEADP h) ;//delete elem at give postion
  40. void replacenode(int postion,LISTHEADP h,DULNODEP inode);//replace one node
  41. void viewchain(LISTHEADP h);//show info for chain
  42. void viewheadinfo(LISTHEADP h);//only show head info

  44. #endif

点击(此处)折叠或打开

  1. 功能函数文件：
  2. #include<stdlib.h>
  3. #include<stdio.h>
  4. #include <string.h>
  5. #include"dulnode.h"

  7. static DULNODEP getelemp(const LISTHEADP h,int postion) ;

  9. //makenode
  10. bool makenode(int datavalue,DULNODEP* p)
  11. {
  12.         *p = (DULNODEP) malloc (SIZENODE);
  13.         if(!(*p))
  14.         {
  15.                 return false;
  16.         }
  17.         else
  18.         {
  19.                 memset(*p,0,SIZENODE);
  20.                 (*p)->data = datavalue;
  21.                 (*p)->next = NULL;
  22.                 (*p)->prior = NULL;
  23.                 return true;
  24.         }
  25. }

  27. //freenode

  29. void freenode(DULNODEP p)
  30. {
  31.         free(p);
  32. }

  34. //initlist with no node

  36. bool initlist(LISTHEADP* p)
  37. {
  38.         *p = (LISTHEADP)malloc(SIZELISTHEAD);
  39.         if(!*p)
  40.         {
  41.                 return false;
  42.         }
  43.         else
  44.         {
  45.                 memset(*p,0,SIZELISTHEAD);
  46.                 (*p)->head = NULL;
  47.                 (*p)->last = NULL;
  48.                 (*p)->current = NULL;
  49.                 (*p)->length = 0;
  50.                 return true;
  51.         }
  52. }
  53. //destroy a list,every list thing is not live
  54. void destroylist(LISTHEADP p)
  55. {
  56.         DULNODEP npc;
  57.         DULNODEP npn;
  58.         int i = 0;

  60.         if(npc = p->head)
  61.         {
  62.                 npn = p->head->next;
  63.                 for(i=0;i<p->length;i++)
  64.                 {
  65.                         free(npc);
  66.                         npc = npn;
  67.                         if(npn) //last one is null null->next will
  68.                         {
  69.                                 npn = npn->next;
  70.                         }
  71.                 }
  72.         }

  74.         free(p);
  75. }
  76. //clear a list,but head is live
  77. void clearlist(LISTHEADP p)
  78. {
  79.         DULNODEP npc;
  80.         DULNODEP npn;
  81.         int i = 0;

  83.         if(npc = p->head)
  84.         {
  85.                 npn = p->head->next;
  86.                 for(i=0;i<p->length;i++)
  87.                 {
  88.                         free(npc);
  89.                         npc = npn;
  90.                         if(npn) //last one is null null->next will
  91.                         {
  92.                                 npn = npn->next;
  93.                         }
  94.                 }
  95.         }
  96.         p->head = NULL;
  97.         p->last = NULL;
  98.         p->current = NULL;
  99.         p->length = 0;
  100. }

  102. //insfirst insert one node at first postion

  104. void insfirst(LISTHEADP h,DULNODEP s)
  105. {
  106.         if(!(h->head)) //list is empty or not
  107.         {
  108.                 h->head = s;
  109.                 h->last = s;
  110.                 h->current = s;
  111.                 h->length++;
  112.         }
  113.         else
  114.         {
  115.                 h->head->prior = s;
  116.                 s ->next = h->head;
  117.                 h->head = s;
  118.                 h->current = s;
  119.                 h->length++;

  121.         }

  123. }


  126. //delfirst
  127. void delfirst(LISTHEADP h) //delete first node current_point to next node
  128. {
  129.         DULNODEP p;
  130.         if(!(h->head))
  131.         {
  132.                 printf("error(1):delfirst() error list have no node!\n");
  133.                 exit(1);
  134.         }
  135.         else if(!(h->head->next)) //only one node
  136.         {
  137.                 free(h->head);
  138.                 h->head = NULL;
  139.                 h->current = NULL;
  140.                 h->last = NULL;
  141.                 h->length--;
  142.         }
  143.         else
  144.         {
  145.                 p = h->head ;
  146.                 h->head->next->prior = NULL;
  147.                 h->head = h->head->next;
  148.                 h->current = h->head;
  149.                 h->length--;
  150.                 free(p);
  151.         }
  152. }


  155. //inslast insert one node at last postion

  157. void inslast(LISTHEADP h,DULNODEP s)
  158. {
  159.         if(!(h->head)) //list is empty or not
  160.         {
  161.                 h->head = s;
  162.                 h->last = s;
  163.                 h->current = s;
  164.                 h->length++;
  165.         }
  166.         else
  167.         {
  168.                 h->last->next = s;
  169.                 s->prior = h->last;
  170.                 h->last = s;
  171.                 h->current = s;
  172.                 h->length++;
  173.         }
  174. }



  178. //dellast

  180. void dellast(LISTHEADP h) //delete last node current_point to prior node
  181. {
  182.         DULNODEP p;
  183.         if(!(h->head))
  184.         {
  185.                 printf("error(1):delfirst() error list have no node!\n");
  186.                 exit(1);
  187.         }
  188.         else if(!(h->head->next)) //only one node
  189.         {
  190.                 free(h->head);
  191.                 h->head = NULL;
  192.                 h->current = NULL;
  193.                 h->last = NULL;
  194.                 h->length--;
  195.         }
  196.         else
  197.         {
  198.                 p = h->last ;
  199.                 h->last->prior->next = NULL;
  200.                 h->last = p->prior;
  201.                 h->current = p->prior;
  202.                 h->length--;
  203.                 free(p);
  204.         }
  205. }


  208. static DULNODEP getelemp(const LISTHEADP h,int postion)
  209. {
  210.         int i=0;
  211.         DULNODEP p;
  212.         if(postion > h->length || postion ==0 )
  213.         {
  214.                 printf("error(2):getelemp() postion large than lenth or poastion = 0\n");
  215.                 exit(2);
  216.         }
  217.         p = h->head;

  219.         while(i<postion-1)
  220.         {
  221.                 i++;
  222.                 p = p->next;
  223.         }
  224.         return p;
  225. }

  227. //addnode add one node after give postion
  228. void addnode(DULNODEP inode,int postion,LISTHEADP h) //insert one elem after postion
  229. {
  230.         DULNODEP p;
  231.         p = getelemp(h,postion);
  232.         if(!p->next) //last node?
  233.         {
  234.                 p->next = inode;
  235.                 inode->prior = p;
  236.                 inode->next = NULL;
  237.                 h->last = inode;
  238.                 h->current = inode;
  239.         }
  240.         else
  241.         {
  242.                 inode->prior = p;
  243.                 inode->next = p->next;
  244.                 p->next->prior = inode;
  245.                 p->next = inode;
  246.                 h->current = inode;
  247.         }
  248.         h->length++;
  249. }

  251. //removenode remove one node at postion and current point to next postion

  253. void removenode(int postion,LISTHEADP h) //delete elem at give postion
  254. {
  255.         DULNODEP p;
  256.         p = getelemp(h,postion);

  258.         if(postion == 1 && !(p->next)) //node one and only one node
  259.         {
  260.                 h->head = NULL;
  261.                 h->current = NULL;
  262.                 h->last = NULL;
  263.                 free(p);
  264.         }
  265.         else if(postion == 1) //node one?
  266.         {
  267.                 p->next->prior = NULL;
  268.                 h->head = p->next;
  269.                 h->current = h->head;
  270.                 free(p);
  271.         }
  272.         else if(!(p->next)) //last node?
  273.         {
  274.                 h->current = NULL;
  275.                 h->last = p->prior;
  276.                 p->prior->next = NULL;
  277.                 free(p);
  278.         }
  279.         else
  280.         {
  281.                 h->current = p->next;
  282.                 p->next->prior = p->prior;
  283.                 p->prior->next = p->next;
  284.                 free(p);
  285.         }
  286.         h->length--;
  287. }


  290. //replacenode replace one node


  293. void replacenode(int postion,LISTHEADP h,DULNODEP inode)
  294. {
  295.         DULNODEP p;
  296.         p = getelemp(h,postion);

  298.         if(postion == 1 && !(p->next)) //node one and only one node
  299.         {
  300.                 h->head = inode;
  301.                 h->current = inode;
  302.                 h->last = inode;
  303.                 free(p);
  304.         }
  305.         else if(postion == 1)
  306.         {
  307.                 inode->next = h->head->next;
  308.                 h->head->next->prior = inode;
  309.                 h->head = inode;
  310.                 h->current = inode;
  311.                 free(p);
  312.         }
  313.         else if(!(p->next))
  314.         {
  315.                 inode->prior = p->prior;
  316.                 p->prior->next = inode;
  317.                 h->current = inode;
  318.                 h->last = inode;
  319.                 free(p);
  320.         }
  321.         else
  322.         {
  323.                 inode->prior = p->prior;
  324.                 inode->next = p->next;
  325.                 p->prior->next = inode;
  326.                 p->next->prior = inode;
  327.                 h->current = inode;
  328.                 free(p);
  329.         }
  330. }


  333. void viewchain(LISTHEADP h)
  334. {
  335.         int i=1;
  336.         DULNODEP p;
  337.         p = h->head;
  338.         if(!p)
  339.         {
  340.                 printf("error(3):viewchain() list no data\n");
  341.                 exit(3);
  342.         }

  344.         printf("Max chain length is:%d,current_pointor is:%p,head_pointor is:%p,last_pointor is:%p\n",h->length,h->current,h->head,h->last);
  345.         do
  346.         {
  347.                 printf("node:%d values is: %d\n",i,p->data);
  348.                 i++;

  350.         }while(p=p->next);
  351. }

  353. void viewheadinfo(LISTHEADP h)
  354. {

  356.         printf("Max chain length is:%d,current_pointor is:%p,head_pointor is:%p,last_pointor is:%p\n",h->length,h->current,h->head,h->last);
  357. }

点击(此处)折叠或打开

  1. 主函数文件：
  2. #include<stdlib.h>
  3. #include<stdio.h>
  4. #include"dulnode.h"



  8. int main(void)
  9. {
  10.         LISTHEADP headp=NULL;
  11.         DULNODEP p1=NULL;
  12.         DULNODEP p2=NULL;
  13.         DULNODEP p3=NULL;
  14.         DULNODEP p4=NULL;

  16.         DULNODEP p5=NULL;
  17.         DULNODEP p6=NULL;

  19.         if(!(initlist(&headp)))
  20.                 {
  21.                         printf("initlist error\n");
  22.                 }
  23.         if(!(makenode(1,&p1)))
  24.                 {
  25.                         printf("makenode error\n");
  26.                 }
  27.         if(!(makenode(2,&p2)))
  28.         {
  29.                 printf("makenode error\n");
  30.         }
  31.         if(!(makenode(3,&p3)))
  32.         {
  33.                  printf("makenode error\n");
  34.         }
  35.         if(!(makenode(4,&p4)))
  36.         {
  37.                 printf("makenode error\n");
  38.         }

  40.         if(!(makenode(5,&p5)))
  41.         {
  42.                 printf("makenode error\n");
  43.         }

  45.         if(!(makenode(6,&p6)))
  46.         {
  47.                 printf("makenode error\n");
  48.         }

  50.         insfirst(headp,p1);
  51.         insfirst(headp,p2);
  52.         insfirst(headp,p3);
  53.         inslast(headp,p4);

  55.         viewchain(headp);

  57.         delfirst(headp);
  58.         viewchain(headp);
  59.         dellast(headp);
  60.         viewchain(headp);

  62.         addnode(p5,1,headp);
  63.         viewchain(headp);
  64.         replacenode(2,headp,p6);
  65.         viewchain(headp);
  66.         removenode(2,headp);
  67.         viewchain(headp);
  68.         clearlist(headp);
  69.         destroylist(headp);
  70.         return 0;

  72. }

下面我们给出结果来分析：
Max chain length is:4,current_pointor is:0xd210a0,head_pointor is:0xd21080,last_pointor is:0xd210a0
node:1 values is: 3
node:2 values is: 2
node:3 values is: 1
node:4 values is: 4
Max chain length is:3,current_pointor is:0xd21060,head_pointor is:0xd21060,last_pointor is:0xd210a0
node:1 values is: 2
node:2 values is: 1
node:3 values is: 4
Max chain length is:2,current_pointor is:0xd21040,head_pointor is:0xd21060,last_pointor is:0xd21040
node:1 values is: 2
node:2 values is: 1
Max chain length is:3,current_pointor is:0xd210c0,head_pointor is:0xd21060,last_pointor is:0xd21040
node:1 values is: 2
node:2 values is: 5
node:3 values is: 1
Max chain length is:3,current_pointor is:0xd210e0,head_pointor is:0xd21060,last_pointor is:0xd21040
node:1 values is: 2
node:2 values is: 6
node:3 values is: 1
Max chain length is:2,current_pointor is:0xd21040,head_pointor is:0xd21060,last_pointor is:0xd21040
node:1 values is: 2
node:2 values is: 1

首先构造了4个节点前面3个用insfrist 这样就是 3 2 1的排列最后一个用inslast 那么就是 3 2 1 4 可以看到确实如此

然后使用delfrist 删除第一个就是3 那么剩下 2 1 4 然后使用dellast 那么删除 4 就是 2 1 可以看到确实如此

然后我们使用addnode 在位置1后面加入元素 5 那么就是 2 5 1 确实如此
然后我们使用replacenode 将位置2的元素 data 5的数据换位 data为 6的数据变为 2 6 1
最后调用removenode将位置2的元素删除变为了 2 1 最后是清空和销毁链表。
整个过程预期和测试结果一致

文章标签：
DataV数据可视化
关键词：
数据结构链表
数据结构双向链表
相关实践学习
DataV Board用户界面概览
本实验带领用户熟悉DataV Board这款可视化产品的用户界面
阿里云实时数仓实战 - 项目介绍及架构设计
课程简介 1)学习搭建一个数据仓库的过程，理解数据在整个数仓架构的从采集、存储、计算、输出、展示的整个业务流程。 2)整个数仓体系完全搭建在阿里云架构上，理解并学会运用各个服务组件，了解各个组件之间如何配合联动。 3&nbsp;)前置知识要求 &nbsp; 课程大纲 第一章&nbsp;了解数据仓库概念 初步了解数据仓库是干什么的 第二章&nbsp;按照企业开发的标准去搭建一个数据仓库 数据仓库的需求是什么 架构 怎么选型怎么购买服务器 第三章&nbsp;数据生成模块 用户形成数据的一个准备 按照企业的标准，准备了十一张用户行为表 方便使用 第四章&nbsp;采集模块的搭建 购买阿里云服务器 安装 JDK 安装 Flume 第五章&nbsp;用户行为数据仓库 严格按照企业的标准开发 第六章&nbsp;搭建业务数仓理论基础和对表的分类同步 第七章&nbsp;业务数仓的搭建&nbsp; 业务行为数仓效果图&nbsp;&nbsp;
重庆八怪
目录
相关文章
XIAZHI
|
26天前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
52 4
龙大吉
|
19天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
42 5
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
73 4
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
25 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
36 2
XIAZHI
|
26天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
43 0
小强在此
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
小强在此
29 7
GuGuStudy
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
27 3
java冯坚持
|
2月前
|
算法 Java
数据结构与算法学习五：双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现，并通过实例演示了双向链表的优势和应用。
java冯坚持
20 0
数据结构与算法学习五：双链表的增、删、改、查
努力学习的小廉
|
2月前
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
努力学习的小廉
37 2