05 双向链表

目录

1.双向链表
2.实现
3.OJ题
4.链表和顺序表对比

1. 双向链表

前面写了单向链表，复习一下
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多作为其他数据结构的子结构，如哈希桶、图的邻接等。另外这种结构在笔试面试中出现多

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构， 都是带头双向循环链表。另外这个结构虽然复杂，但是使用代码实现以后发现会带来很多优势，实现反而简单了

2. 实现

头文件

#pragma once

//数据类型
typedef int DataType;
//结构
typedef struct _SListNode
{
	DataType data;
	struct _SListNode* pNext;
}SListNode;

//插入
void PushFront(SListNode** pHead, DataType data);
void PushBack(SListNode** pHead, DataType data);
//pos之前插入
void Insert(SListNode** pHead, SListNode* pPos, DataType data);
//pos之后插入
void InsertAfter(SListNode** pHead, SListNode* pPos, DataType data);
//查找
SListNode* Find(SListNode* pHead, DataType data);
//删除
void PopFront(SListNode** pHead);
void PopBack(SListNode** pHead);
void Erase(SListNode** pHead, SListNode* pos);
// 删除pos位置后面的值
void EraseAfter(SListNode* pos);

//打印
void PrintList(SListNode* pHead);
//销毁
void Destory(SListNode** pHead);

插入只需要修改新节点的前后节点，新节点前后节点的链接，注意顺序，不能覆盖后面需要的值

插入和删除可以复用insert和erase的函数，所以也可以只写这两个，然后来实现头插尾插这些

#include "List.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

List* BuyNode(DATATYPE data)
{
	List* newnode = (List*)malloc(sizeof(List));
	if (newnode == NULL)
	{
		perror("mallco");
		return NULL;
	}

	//初始化数据
	newnode->data = data;
	newnode->pre = NULL;
	newnode->next = NULL;
	return newnode;
}

List* Init()
{
	List* head = BuyNode(-1);
	if (head == NULL)
	{
		perror("mallco");
	}

	head->pre = head;
	head->next = head;
	return head;
}

void PrintList(List* head)
{
	List* cur = head->next;
	while (cur != head)
	{
		printf("->%d ", cur->data);
		cur = cur->next;
	}
	printf("\r\n");
}


void PushFront(List* head, DATATYPE data)
{
	assert(head);
	//创建节点
	List* newnode = BuyNode(data);

	newnode->pre = head;
	newnode->next = head->next;

	head->next->pre = newnode;
	head->next = newnode;

	/*
	List* first = head->next;
	
	head->next = newnode;
	newnode->pre = head;

	newnode->next = first;
	first->pre = newnode;
	*/

	//Insert(head->next, data);
}

void PushBack(List* head, DATATYPE data)
{
	assert(head);
	//创建节点
	List* newnode = BuyNode(data);
	List* tail = head->pre;

	newnode->pre = tail;
	newnode->next = head;

	tail->next = newnode;
	head->pre = newnode;

	//Insert(head, data);
}

void Insert(List* pos, DATATYPE data)
{
	assert(pos);

	//创建节点
	List* newnode = BuyNode(data);
	List* prev = pos->pre;

	newnode->pre = pos->pre;
	newnode->next = pos;

	prev->next = newnode;
	pos->pre = newnode;
}

void PopFront(List* head)
{
	assert(head);
	assert(!Empety(head));

	List* del = head->next;

	head->next = del->next;
	del->next->pre = head;
	free(del);
	/*
	List* first = head->next;
	List* second = first->next;

	head->next = second;
	second->pre = head;

	free(first);
	*/

	//erase(head->next)
}

void PopBack(List* head)
{
	assert(head);
	assert(!Empety(head));

	List* del = head->pre;
	//保留尾节点前一个
	List* tailpre = del->pre;

	tailpre->next = head;
	head->pre = tailpre;
	free(del);

	//erase(head->pre)
}

void Erase(List* pos)
{
	assert(pos);
	List* posPre = pos->pre;
	List* posNext = pos->next;

	posPre->next = posNext;
	posNext->pre = posPre;
	free(pos);
}

List* FindNode(List* head, DATATYPE data)
{
	assert(head);
	List* cur = head->next;

	while (cur != head)
	{
		if (cur->data == data)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

bool Empety(List* head)
{
	assert(head);

	return head->next == head;

}

void Destory(List* head)
{
	assert(head);

	List* cur = head->next;
	while (cur != head)
	{
		List* next = cur->next;
		free(cur);
		cur = next;
	}

	free(head);
}

主文件

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "List.h"

int main()
{
	List* list = Init();
	PushFront(list, 3);
	PushFront(list, 2);
	PushFront(list, 1);
	PushBack(list, 4);
	PushBack(list, 5);
	PrintList(list);
	PopFront(list);
	PopBack(list);
	PrintList(list);
	List* pos = FindNode(list, 3);
	if (pos != NULL)
	{
		Insert(pos, 1);
		PrintList(list);
	}
	Erase(pos);
	PrintList(list);
	Destory(list);

	return 0;
}

3. OJ题

链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

在这里插入图片描述
思路

直接思路，拷贝一个一模一样的链表，关键是复制random对应的节点值，要遍历看原链表指向的random是在第几个，将新链表的random链接到对应位置，这种方法时间复杂度较高

另一种思路。在原链表每个节点后面插入一个拷贝出来的原链表值。重点在random的链接，这样新链表的random就是原链表对应的rand节点的下一个位置。然后再创建一个新链表，将每个拷贝节点尾插并还原原链表

在这里插入图片描述

如图，原链表指向是1->2->3->null，插入蓝色的新拷贝链表，1->蓝1->2->蓝2->3->蓝3->null,原1的random指向3,那么拷贝链表的random指向就应该是3的next,就是拷贝链表的3

解绑过程如下图

在这里插入图片描述

cur是当前节点，它的next是copy节点，首先链表头和尾本来是空，第一次置为第一个拷贝节点。将copy节点尾插到copytail链表，cur的next节点就是copy节点的下一个，然后将cur更新到copy的next，如下图

在这里插入图片描述这样一直循环

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	
    struct Node* cur = head;
    //拷贝节点插入在原节点后面
    while(cur != NULL)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        struct Node* next = cur->next;
        //插入
        cur->next = copy;
        copy->next = next;

        cur = next;
    }

    //控制拷贝节点的random
    cur = head;
    while(cur != NULL)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else{
            //指向对应的拷贝链表
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }

    //尾插拷贝链表,还原原链表
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    
    cur = head;
    while(cur != NULL)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        //尾插
        if(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        else{
            copytail->next = copy;
            copytail = copytail->next;
        }
        //恢复原链表
        cur->next = copy->next;
        cur = next;
    }
    return copyhead;
}

4. 顺序表和链表对比

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，物理上不一定
随机访问支持O(1)不支持O(N)
任意位置插入和删除元素可能需要搬元素,O(N)只需修改指针指向
插入动态顺序表,空间不够扩容没有容量概念
应用场景元素高效存储+频繁访问任意位置频繁插入和删除
缓存利用率高低

链表
优点:
1.任意位置插入删除O(1)
2.按需申请释放空间
缺点:
1.不支持下标随机访问
2.CPU告诉缓存命中率更低
顺序表
优点:
1.尾插尾删效率不错
2.下标的随机访问
3.CPU告诉缓存命中率更高
缺点:
1.除过尾插尾删,效率低O(N),需要挪动元素
2.空间不够,需要扩容
3.扩容需要代价,一般伴随空间浪费

cpu存储分类在这里插入图片描述数据的存储从服务器到硬盘,再到内存。其中内存还有寄存器和告诉缓存部分，访问速度越网上越快，但代价也越高，空间也越小。寄存器中拿数据是最快的，但一般寄存器只有几十字节

内存读取数据并不是需要多少读多少，它会将需要读取的数据后面的一部分也读入缓存中，因为这部分极有可能还会读取，这就是命中缓存，访问速度更快。所以顺序表式连续存储的，命中缓存的几率更高，速度也就更快

每个数据类型都各有优势，有不同的应用场景，不存在优劣

相关参考:
CPU缓存知识

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/344139.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Pycharm中出现Comparison with None performed with equality operators

Pycharm中出现Comparison with None performed with equality operators

此图中警告翻译过来是 &#xff1a;与使用相等运算符执行的None进行比较 这里不应该使用 或者 &#xff01; 而应改为 is 或者 is not
阅读更多...
聚观早报 | 华为P70 Art细节曝光；红魔9 Pro龙年限定版官宣

聚观早报 | 华为P70 Art细节曝光；红魔9 Pro龙年限定版官宣

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 1月24日消息 华为P70 Art细节曝光 红魔9 Pro龙年限定版官宣 努比亚Z60 Ultra龙年限定版 小米14 Ultra或没有双版…
阅读更多...
创新医疗服务：宠物在线问诊系统的搭建与应用

创新医疗服务：宠物在线问诊系统的搭建与应用

随着科技的不断进步&#xff0c;创新的医疗服务方式也日渐成为宠物主人关心爱宠健康的首选。本文将深入介绍如何搭建一套创新的宠物在线问诊系统&#xff0c;并展示其应用的技术代码。 1. 系统架构与技术选择 在开始搭建之前&#xff0c;我们需要设计系统的架构并选择合适的…
阅读更多...
【Linux工具篇】编辑器vim

【Linux工具篇】编辑器vim

目录 vim的基本操作 进入vim(正常模式&#xff09; 正常模式->插入模式 插入模式->正常模式 正常模式->底行模式 底行模式->正常模式 底行模式->退出vim vim正常模式命令集 vim插入模式命令集 vim末行模式命令集 vim操作总结 vim配置 Linux编译器…
阅读更多...
网络安全的使命：守护数字世界的稳定和信任

网络安全的使命：守护数字世界的稳定和信任

在数字化时代&#xff0c;网络安全的角色不仅仅是技术系统的守护者&#xff0c;更是数字社会的信任保卫者。网络安全的使命是保护、维护和巩固数字世界的稳定性、可靠性以及人们对互联网的信任。本文将深入探讨网络安全是如何履行这一使命的。 第一部分&#xff1a;信息资产的…
阅读更多...
使用Sobel算子把视频转换为只剩边缘部分

使用Sobel算子把视频转换为只剩边缘部分

效果展示 原始视频 修改后的视频 整体代码 import cv2vc cv2.VideoCapture(test.mp4)if vc.isOpened():open, frame vc.read() else:open Falsei 0 while open:ret, frame vc.read()if frame is None:breakif ret True:i 1# 转换为灰度图gray cv2.cvtColor(frame, cv…
阅读更多...
复合机器人颠覆传统上下料，实现高效精准生产

复合机器人颠覆传统上下料，实现高效精准生产

在追求高效、精准生产的现代制造业中&#xff0c;传统的上下料方式已经无法满足企业的需求。复合机器人的出现&#xff0c;为制造业带来了革命性的变革。它不仅提高了生产效率&#xff0c;降低了生产成本&#xff0c;还为企业创造了更大的竞争优势。复合机器人的广泛应用&#…
阅读更多...
多维时序 | Matlab实现CNN-BiGRU-Mutilhead-Attention卷积双向门控循环单元融合多头注意力机制多变量时间序列预测

多维时序 | Matlab实现CNN-BiGRU-Mutilhead-Attention卷积双向门控循环单元融合多头注意力机制多变量时间序列预测

多维时序 | Matlab实现CNN-BiGRU-Mutilhead-Attention卷积双向门控循环单元融合多头注意力机制多变量时间序列预测 目录 多维时序 | Matlab实现CNN-BiGRU-Mutilhead-Attention卷积双向门控循环单元融合多头注意力机制多变量时间序列预测效果一览基本介绍程序设计参考资料 效果一…
阅读更多...
GD32E230C8T6《调试篇》之 FMC（闪存）的读写 + USART打印

GD32E230C8T6《调试篇》之 FMC（闪存）的读写 + USART打印

实验&#xff1a;按键DIG4&#xff08;保存键&#xff09;&#xff0c;任意按下一个数字后&#xff0c;再按保存键写入flash;断电后重新上电&#xff0c;从 flash里读值&#xff0c;显示到数码管 实验工具GD32E230C8T6查看GPIO查看Datasheet 2.6.7章节GPIO 复用 查看用户手册代…
阅读更多...
Python Django的学生选课管理系统，实现多用户登录注册，可选课可评课

Python Django的学生选课管理系统，实现多用户登录注册，可选课可评课

学生选课管理系统是一个基于Python Django开发的教务管理系统&#xff0c;旨在提供方便快捷的选课服务和学籍管理功能。该系统分为教师端和学生端两个角色&#xff0c;为教师和学生提供了不同的功能和权限。 教师端功能&#xff1a; 教师可以登录系统后&#xff0c;进行课程管…
阅读更多...
如何在 Ubuntu 20.04 上安装 Nginx

如何在 Ubuntu 20.04 上安装 Nginx

前些天发现了一个人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;最重要的屌图甚多&#xff0c;忍不住分享一下给大家。点击跳转到网站。 如何在 Ubuntu 20.04 上安装 Nginx 介绍 Nginx是世界上最受欢迎的 Web 服务器之一&#xff0c;负责托管互联网…
阅读更多...
【LeetCode-406】根据身高重建队列(贪心)

【LeetCode-406】根据身高重建队列(贪心)

LeetCode406.根据身高重建队列 题目描述 题目链接 假设有打乱顺序的一群人站成一个队列&#xff0c;数组 people 表示队列中一些人的属性&#xff08;不一定按顺序&#xff09;。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi &#xff0c;前面 正好 有 ki 个身高大于…
阅读更多...
[C++]使用yolov8的onnx模型仅用opencv和bytetrack实现目标追踪

[C++]使用yolov8的onnx模型仅用opencv和bytetrack实现目标追踪

【官方框架地址】 yolov8: https://github.com/ultralytics/ultralytics bytetrack: https://github.com/ifzhang/ByteTrack 【算法介绍】 随着人工智能技术的不断发展&#xff0c;目标追踪已成为计算机视觉领域的重要研究方向。Yolov8和ByTetrack作为当前先进的算法&…
阅读更多...
设计模式——1_6 代理（Proxy）

设计模式——1_6 代理（Proxy）

诗有可解不可解&#xff0c;若镜花水月勿泥其迹可也 —— 谢榛 文章目录 定义图纸一个例子&#xff1a;图片搜索器图片加载搜索器直接在Image添加组合他们 各种各样的代理远程代理&#xff1a;镜中月&#xff0c;水中花保护代理&#xff1a;对象也该有隐私引用代理&#xff1a;…
阅读更多...
成熟的内外网数据交换方案，如何实现跨网传输？

成熟的内外网数据交换方案，如何实现跨网传输？

网络迅速发展&#xff0c;我们可以从网络上查找到各式各样的信息&#xff0c;但是同时网络安全问题也随之严重。近几年&#xff0c;各种有关网络安全的新闻不断被报道&#xff0c;数据泄露给很多企业带来了严重打击&#xff0c;不仅是经济损失&#xff0c;严重者还会对企业的声…
阅读更多...
二进制计算

二进制计算

二进制的引入 十进制规则:满10进1&#xff0c;由数字0到9组成。 而所谓十六进制&#xff0c;八进制&#xff0c;二进制的规则也是类似。 这里为了区分十六进制和八进制&#xff0c;十六进制前面会加上0x&#xff0c;八进制前面会加个0作为区分 而二进制的规则类似于十进制&…
阅读更多...
【时间序列篇】基于LSTM的序列分类-Pytorch实现 part2 自有数据集构建

【时间序列篇】基于LSTM的序列分类-Pytorch实现 part2 自有数据集构建

系列文章目录 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part1 案例复现 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part2 自有数据集构建 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part3 化为己用 在一个人体姿态估计的任务中&#xff0c;需要用深度学习模型…
阅读更多...
uniapp css样式穿透

uniapp css样式穿透

目录 前言css样式穿透方法不加css样式穿透的代码加css样式穿透的代码不加css样式穿透的代码 与 加css样式穿透的代码 的差别参考 前言 略 css样式穿透方法 使用 /deep/ 进行css样式穿透 不加css样式穿透的代码 <style>div {background-color: #ddd;} </style>…
阅读更多...
Go 虚拟环境管理工具 gvm 原理介绍与使用指南

Go 虚拟环境管理工具 gvm 原理介绍与使用指南

本文谈下我对 Go 版本管理的一些想法。让后&#xff0c;我将介绍一个小工具&#xff0c;gvm。这个话题说起来也很简单&#xff0c;但如果想用的爽&#xff0c;还是要稍微梳理下。 背景介绍 Go 的版本管理&#xff0c;并非包的依赖管理&#xff0c;而且关于如何在不同的 Go 版…
阅读更多...
一文读懂：D3.js的前世今生，以及与echarts的对比

一文读懂：D3.js的前世今生，以及与echarts的对比

D3.js&#xff08;Data-Driven Documents&#xff09;是一种用于创建动态、交互式数据可视化的JavaScript库。它通过使用HTML、CSS和SVG等Web标准&#xff0c;将数据与文档结合&#xff0c;使得数据可以以一种直观和易于理解的方式进行呈现。D3.js的重要性在于它赋予了开发者更…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站