C语言的双向链表头插法和尾插法，指定节点删除

首页 > C语言的双向链表头插法和尾插法，指定节点删除

C语言的双向链表头插法和尾插法，指定节点删除

文章目录

- - - 前言
    - 头插法
    - 尾插法
    - 删除节点
    - 测试代码如下

前言

双向链表和单链表的唯一区别就是多个一个指针域而已，该指针域可以访问链表的上一个节点。

关于构造双向链表的过程我们常见的有两种方法，和单链表一样：头插法和尾插法。

头插法：字面意思也是很好理解，每次插入的元素在上一个节点之前

尾插法：字面意思也表达出了每次的元素插入会在上一个节点之后

详细插入过程可以参考如下

头插法

头插法基本过程如下图，已经描述的很清楚了

在这里插入图片描述

简单讲一下，这里需要有一个指向的顺序问题

第三步和第四步是需要有先后关系的

第三步： head -> next -> prev = p ，这一步是更新head节点下一个节点的pre域链接的；而第四步: head -> next = p，则是更新head的next域。

如果第四步在前，第三步的head -> next -> prev 就变为了 p -> prev = p，显然不合理。

实现算法如下（文末有完整源码）

Data *insert_head(int n) { Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head -> next;while (n--){ int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;/*考虑头节点的next域为空，防止访第3步head->next->prev访问到空的指针*/if (head -> next == NULL) {  p -> next = NULL;p -> prev = head;head -> next = p;} else{ p -> next = head -> next;p -> prev = head;head -> next -> prev = p;head -> next = p;}}return head -> next;
}

尾插法

具体步骤如下：

在这里插入图片描述

具体指向的过程看图就可以，非常清晰

这里多了一个第五步，是为了保证临时节点r的移动，持续指向插入节点的上一个节点。

实现代码如下:

Data *insert_tail(int n){ Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head;while (n --){ int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;/*同样为了防止第三部 r->next->prev访问到了空节点，提前进行处理*/if (r -> next == NULL) { p -> next = NULL;p -> prev = r;r -> next = p;} else  { p -> next = NULL;p ->prev = r;r -> next -> prev = p;r -> next = p;}r = p;}return head -> next;
}

删除节点

删除过程很简单，主要是上下节点的直接指向：

找到要删除的节点p，以及其上一个节点r
重新指向r的next域，跳过需要删除的节点

Data *delete_list(Data *head, int data) { Data *p;Data *r = head ;/*找到要删除的节点，命名为p，同时需要获取p的上一个节点r*/while (r->next) { if (r-> next ->data == data) { p = r->next;break;}r = r->next;}/*删除节点p*/r->next = p -> next;p->next->prev = r;p = NULL;return head;
}

测试代码如下

#include 
#include typedef struct DoubleLink { int data;struct DoubleLink *next;struct DoubleLink *prev;
}Data;/*打印链表,先next顺序打印，再prev逆序打印*/
void print_list(Data *head) { if(head == NULL)return;printf("next 
");while (head -> next) { printf("%d ",head->data);head = head -> next;}printf("%d
",head->data);Data *p = head;printf("
prev 
");while (p -> prev != p) { printf("%d ",p->data);p = p ->prev;}printf("
");
}/*尾插法*/
Data *insert_tail(int n){ Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head;while (n --){ int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;if (r -> next == NULL) { p -> next = NULL;p -> prev = r;r -> next = p;} else  { p -> next = NULL;p ->prev = r;r -> next -> prev = p;r -> next = p;}r = p;}return head -> next;
}/*头插法*/
Data *insert_head(int n) { Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head -> next;while (n--){ int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;if (head -> next == NULL) { p -> next = NULL;p -> prev = head;head -> next = p;} else{ p -> next = head -> next;p -> prev = head;head -> next -> prev = p;head -> next = p;}}return head -> next;}/*删除链表,删除节点data为2的链表*/
Data *delete_list(Data *head, int data) { if(head == NULL)return NULL;Data *p;Data *r = head ;while (r->next) { if (r-> next ->data == data) { p = r->next;break;}r = r->next;}r->next = p -> next;p->next->prev = r;p = NULL;return head;
}int main()
{ printf("construct the double list tail
");Data * head = insert_tail(5);print_list(head);printf("construct the double list head
");Data * tail = insert_head(5);print_list(tail);printf("delete the double list node
");Data * test = insert_head(5);Data *result = delete_list(test,2);print_list(result);return 0;
}

输出结果如下:

construct the double list tail
1 2 3 4 5next 
1 2 3 4 5
prev 
5 4 3 2 1 construct the double list head
1 2 3 4 5next 
5 4 3 2 1
prev 
1 2 3 4 5 delete the double list node
1 2 3 4 5
next 
5 4 3 1
prev 
1 3 4 5

更多相关：

剑指offer：面试题35. 复杂链表的复制

题目：复杂链表的复制请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。示例 1：输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出...
leetcode-86 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...
leetcode-142 环形链表II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。示例 1：输入：head = [3,2,0,-4], pos = 1...
leetcode-92 反转链表II

题目描述如下：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版需要记录第m-1个节点和第n+1个...
leetcode-206 反转链表

描述如下：反转一个单链表。示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...
剑指offer：面试题25. 合并两个排序的链表

题目：合并两个排序的链表输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。示例1：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制： 0 <= 链表长度 <= 1000 解题: /*** Definition for singly-linked li...
剑指offer：面试题24. 反转链表

题目：反转链表定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制： 0 <= 节点个数 <= 5000 解题：方法一：双指针我们可以申请两个指针，第一个指针叫 new_next，最...
LRU算法 -- 链表完整实现

LRU算法(Least Recently Used) 算是我们经常遇到的一种淘汰算法，其中内存管理模块进行内存页回收时有用到，针对不经常使用的内存页，LRU淘汰策略能够将该内存页回收给操作系统。属于我们操作系统设计中的时间局部性原理，最长时间未被访问的数据优先淘汰，当内存中已存在的数据再次被访问时，则进行热度的提升。本文为...
leetcode-24 两两交换链表中的节点

题目描述给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. 方法一（递归）：将配对交换过程拆解为多个以两个元素为一对的子问题 …n(k-1) -> n(k)->n(k+1)...
C语言的有序单链表合并

已知两个已排序链表头节点指针headA与headB，将这两个链表合并，合并后仍为有序的，返回合并后的头节点。主要步骤如下：创建一个临时的头节点，头节点每次指向headA 或者 headB较小的节点当headA->data 比headB->data小的时候，headA的当前节点加入临时头节点，同时headA指针向后移动；否则h...
python制作统计图_刻意练习11：Python描述统计、简单统计图形

学习计划 MyPlan11 主题：Python描述统计、简单统计图形时间：8.5-8.11周内完成参考资料：新书《谁说菜鸟不会数据分析python篇》各位星友们，在这个星球里每个人都要逼迫自己学习未知的领域或知识点，每天进步一点点，积累的时间久了，菜鸟也能起飞。完成情况：在pandas中，使用describe函数进行描述统...
python3socket非阻塞_利用Python中SocketServer 实现客户端与服务器间非阻塞通信

利用SocketServer模块来实现网络客户端与服务器并发连接非阻塞通信。首先，先了解下SocketServer模块中可供使用的类： BaseServer：包含服务器的核心功能与混合（mix-in）类挂钩；这个类只用于派生，所以不会生成这个类的实例；可以考虑使用TCPServer和UDPServer。 TCPServer/UDPS...
剑指offer：面试题37. 序列化二叉树

题目：序列化二叉树请实现两个函数，分别用来序列化和反序列化二叉树。示例: 你可以将以下二叉树： 1 / 2 3 / 4 5 序列化为 "[1,2,3,null,null,4,5]" 解题： /*** Definition for a binary tree no...
sd.js 2.0封装：更加简化请求传参内容

sd.js import $global from "./global"; import $g from "./sg"; import $ from "jquery"; import {Message, Loading} from "element-ui";//引入饿了么相关组件 import {Base64} from "js-...
sd.js帮助您简化繁重的获取数据、存储数据（CRUD）骚操作（吐槽~在安卓9.0以下或者IOS10.X以下手机端H5页面不支持，在这两

原生sd.js---------------------------------------------------------------- const API_ROOT_URL = "http://www.api.com";const $d= {_postList_url: API_ROOT_URL + "/api...