从零开始学数据结构系列之第一章《双链表》

本文主要是介绍从零开始学数据结构系列之第一章《双链表》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

双链表的定义
双链表上的操作
初始化
插入操作
头插法
尾插法
删除操作
总代码
往期回顾

双链表的定义

为什么引入双链表？

单链表的结点中只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。

双链表的结点中有两个指针prior和next，分别指向前驱结点和后继结点。

双链表中结点类型的描述：

typedef struct Node
{int data;struct Node *next;struct Node *pre;
}Node;

双链表上的操作

双链表与单链表一样，为了操作方便也可以加入头结点，那么初始化双链表其实就是定义一个头结点，然后将指针域置空。
在这里插入图片描述

初始化

/* 
数据总数data 清零
同时列表的前端与后继都指向为空
*/
Node* InitList()
{Node* list = (Node*)malloc(sizeof(Node));  list -> data = 0;   list -> next = NULL;list -> pre = NULL;return list;
}

在这里插入图片描述

插入操作

在双链表中p所指的结点之后插入结点*s，其指针的变化过程如下图所示：

头插法

/* 
注意，这是头插法，
所以待插入列表数据的前端永远指向原先列表
待插入列表数据的后端如果是第一次插入则指向为空，后续都指向下一个列表
这里涉及到了4条“线”的连接
*/
void headInsert(Node* list, int data)
{Node* node = (Node*)malloc(sizeof(Node));  node -> data = data;node -> next = list -> next;node -> pre = list;/** 注意，这里是以防第一次插入的时候* 不能是NULL直接指向node*/if(list -> next){list -> next ->pre = node;}list -> next = node;list -> data++;
}

尾插法

/* 
这里涉及到了4条“线”的连接
尾插法最主要是找到最后一项的位置
待插入列表数据的后继永远指向NULL，也就是list -> next
*/
void tailInsert(Node* list, int data)
{Node* head = list;Node* node = (Node*)malloc(sizeof(Node));  node -> data = data;while(list -> next){list = list -> next;}node -> next = list -> next;node -> pre = list;list -> next = node;head ->data ++;  
}

删除操作

void delete(Node* list, int data) 
{Node* preNode = list;Node* node = list -> next;while(node){if(node -> data == data) {preNode -> next = node->next;/*防止最后一项删除不掉，如果是最后一项的话，不需要执行这一步操作，如果执行了就是NULL前项指向preNode了*/if(node -> next)node -> next -> pre = preNode;free(node);list -> data--;break;}preNode = node;node = node -> next;}
}

总代码

#include <stdio.h>
#include "stdlib.h"typedef struct Node
{int data;struct Node *next;struct Node *pre;
}Node;Node* InitList()
{Node* list = (Node*)malloc(sizeof(Node));  list -> data = 0;   list -> next = NULL;list -> pre = NULL;return list;
}void headInsert(Node* list, int data)
{Node* node = (Node*)malloc(sizeof(Node));  node -> data = data;node -> next = list -> next;node -> pre = list;	if(list -> next){list -> next ->pre = node;}list -> next = node;list -> data++;
}void tailInsert(Node* list, int data)
{Node* head = list;Node* node = (Node*)malloc(sizeof(Node));  node -> data = data;while(list -> next){list = list -> next;}node -> next = list -> next;node -> pre = list;list -> next = node;head ->data ++;  
}void delete(Node* list, int data) 
{Node* preNode = list;Node* node = list -> next;while(node){if(node -> data == data) {preNode -> next = node->next;if(node -> next)node -> next -> pre = preNode;free(node);list -> data--;break;}preNode = node;node = node -> next;}
}void printfList(Node* list)
{Node* head = list;list = list -> next;while(list != NULL){printf("%d->", list -> data);list = list -> next;}printf("NULL\n");
}void main()
{Node* list = InitList();headInsert(list,1);headInsert(list,2);headInsert(list,3);headInsert(list,3);tailInsert(list,4);tailInsert(list,5);tailInsert(list,6);printfList(list);delete(list,3);delete(list,6);printfList(list);}