加入星计划,您可以享受以下权益:

  • 创作内容快速变现
  • 行业影响力扩散
  • 作品版权保护
  • 300W+ 专业用户
  • 1.5W+ 优质创作者
  • 5000+ 长期合作伙伴
立即加入
  • 正文
  • 推荐器件
  • 相关推荐
  • 电子产业图谱
申请入驻 产业图谱

一文带你搞懂双链表

2022/04/19
780
阅读需 10 分钟
加入交流群
扫码加入
获取工程师必备礼包
参与热点资讯讨论

链表是常用的数据结构,为方便学习,对链表进行细分,分为五种:

1、不带头节点的单链表
2、带头节点的单链表
3、不带头结点的双链表
4、带头结点的双链表
5、带头结点的双向循环链表

链表基本概念

 

头指针:

  1. 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针头指针具有标识作用,所以常用头指针冠以链表的名字无论链表是否为空,头指针均不为空,头指针是链表的必要元素

头节点:

  1. 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了头结点不一定是链表必须要素

单链表和双链表的区别

  1. 单链表的每一个节点中只有指向下一个结点的指针,不能进行回溯。双链表的每一个节点给中既有指向下一个结点的指针,也有指向上一个结点的指针,可以快速的找到当前节点的前一个节点。

上面的三幅图对于理解链表的插入、删除很重要,看代码的时候要对着看。

实际中经常使用的一般为带头双向循环链表,下面是一个双向循环链表的 demo,是最简单的情况。

双向循环链表demo

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

typedef struct node
{
 int data; //"数据域" 保存数据元素
 struct node * next; //保存下一个数据元素的地址
 struct node * prev; //保存上一个数据元素的地址
}Node;

//创建表头表示链表 
Node* creatList()
{
 Node * HeadNode = (Node *)malloc(sizeof(Node));
 //初始化,自己指向自己 
 HeadNode->next = HeadNode->prev = HeadNode;
 return HeadNode;
}
//创建节点 
Node* creatNode(int data)
{
 //C语言:malloc + free 
 //C++:new + delete 
 Node* newNode = (Node *)malloc(sizeof(Node));
 //初始化
 newNode->data = data;
 newNode->next = NULL;
 newNode->prev = NULL;
 return newNode;
}
//遍历链表
void printList(Node *headNode)
{
 //双向链表不光可以用 next 打印,也可以用 prev 进行打印
 //next指针打印:先进后出   
 //prev指针打印:先进先出 
    Node *p = headNode -> next;
    while(p != headNode){
        printf("%dt",p->data);
        p = p -> next;
    }
    printf("n");
}

//插入节点:头插法
void insertNodebyHead(Node *headNode,int data)
{
 //创建插入的节点 
    Node *newNode = creatNode(data);
 //注意顺序,赋值会改变指针指向,因此要先连后断 
 /*
 headNode -> next =  newnode;
 newnode -> prev = headNode;
 newnode -> next = headNode -> next;
 headNode ->next->prev = newNode;
 */
 // 从上面调整顺序,得到下面 
 newNode -> prev = headNode;
 newNode -> next = headNode -> next;
 headNode ->next->prev = newNode;
 headNode -> next =  newNode;
}

//插入节点:尾插法 
void insertNodebyTail(Node *headNode,int data)
{
 //创建插入的节点 
 Node *newNode = creatNode(data);
    
 //找到最后一个节点
 Node *lastNode = headNode;
 while(lastNode->next != headNode)
 {
  lastNode = lastNode->next;//往下走 
 }
 
 //注意顺序
 headNode->prev =  newNode;
 newNode->next = headNode;
 lastNode->next = newNode;
 newNode->prev = lastNode;

}

//删除节点
void deleteNodebyAppoin(Node *headNode,int posData)
{
 // posNode 想要删除的节点,从第一个节点开始遍历 
 // posNodeFront 想要删除节点的前一个节点 
    Node *posNode = headNode -> next;
    Node *posNodeFront = headNode;
    
 if(posNode == NULL)
  printf("链表为空,无法删除");
 else{
  while(posNode->data != posData)
  {
   //两个都往后移,跟着 posNodeFront 走 
   posNodeFront = posNode;  
   posNode = posNodeFront->next;
   if (posNode->next == headNode)
   {
    printf("没有找到,无法删除");
    return; 
   }
  }
  //找到后开始删除 
  posNodeFront->next = posNode->next;
  posNode->next->prev = posNodeFront;
  free(posNode);
 } 
}

int main()
{
 Node* List = creatList();
 
 insertNodebyHead(List,1); 
 insertNodebyHead(List,2); 
 insertNodebyHead(List,3);  
 printList(List);
 
 insertNodebyTail(List,0); 
 printList(List);
 
 deleteNodebyAppoin(List,2);
 printList(List);
 
 return 0;
}

结果:

 

双链表的创建、遍历和单链表差不多,只是头插法、尾插法、删除操作多了几个步骤。

对于容易有疑问的地方,博主都写了注释,请仔细看。不理解的地方对着图更好理解。

推荐器件

更多器件
器件型号 数量 器件厂商 器件描述 数据手册 ECAD模型 风险等级 参考价格 更多信息
SN74LVC1G06DCKT 1 Texas Instruments Single 1.65-V to 5.5-V inverter with open-drain outputs 5-SC70 -40 to 125

ECAD模型

下载ECAD模型
$2.11 查看
NC7WZ07P6X 1 Fairchild Semiconductor Corporation Buffer, LVC/LCX/Z Series, 2-Func, 1-Input, CMOS, PDSO6, 1.25 MM, EIAJ, SC-88, SC-70, 6 PIN
$0.28 查看
HCPL2631SDM 1 Fairchild Semiconductor Corporation Logic IC Output Optocoupler, 2-Element, 5000V Isolation, 10MBps, LEAD FREE, SURFACE MOUNT, DIP-8
$2.67 查看

相关推荐

电子产业图谱

研究生在读,熟悉硬件、STM32单片机、嵌入式Linux。已收获小米、联发科、浙江大华、上能电气、英威腾、汇川技术、格力、富士康等大厂offer。在这里分享求职经验、嵌入式学习规划、考研、嵌入式Linux技术文章等。