草庐IT

【算法基础】数据结构| 单链表+双链表 代码实现+图解+原理

是瑶瑶子啦 2023-04-03 原文

前言

因为瑶瑶子正在备战蓝桥杯和校内ACM选拔赛，最近在学习算法相关的知识。我是借助AcWing网站来学习的，这篇文章是我学习就我学习内容的一个笔记，其中的一些对原理的解释是我学习过程中可能看到弹幕或者评论的小伙伴，觉得讲的很有道理醍醐灌顶，就引用过来了。
这篇是关于数据结构，主要是利用数组模拟各种数据结构，主要是提高算法效率。
对于一些比较晦涩难懂\让人头秃的地方，我习惯采用画图的方式来理解，所以你将看到我基于算法模板或题目精心绘制的图解，希望能帮助一起学算法的同学噢！
因为瑶瑶子目前还是小菜鸡，可能会有理解不到位的地方，或者可以理解得更好的地方，还请大家多多指出哦！❤

注意！下面每一种数据结构的讲解方式，采用代码模板+文字说明&解释+图解

目录

1.单链表(邻接表）

作用：多用于邻接表，存储图和树

代码模板

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点,后一个
int head, e[N], ne[N], idx;
//NULL相当于-1,所以head = -1相当于head=NULL
// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{   
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}
//将x插入到下标是k的点之后
void insert(int k, int x)
{
	e[idx] = x;
	ne[idx] = ne[k]
	ne[k] = idx;
	idx ++;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}
  • 存储节点数组的e[N]和存储该节点的next指针数组ne[N]通过下标关联
  • idx只是记录当前的操作的位置，一般实现的链表idx是乱序的(前后的节点的数组下标不需要连续，需要通过当前的ne[i]找到下一个idx。这也是两者的联系。
  • head一开始=-1，这个-1相当于物理地址的NULL，表示链表为空，即head指向一个头节点，而使用头插法，又巧妙的使这个空节点成为尾节点。联想结构体实现的单链表，最后一个节点的指针域是NULL所以，数组实现单链表的最后一个节点，假设是i,那么ne[i]=-1；
  • 这里模拟的是没有头节点，head指针直接指向首元节点的单链表
  • 虽然数组模拟的链表没有用结构体/类模拟的好理解，但是本质都是一样的，我们可以类比一下，对于一个节点Node。
  • 所以其实画图的时候，也没必要分的那么清楚，其实在我学习数组模拟链表之前，我一直认为数组&链表属于物理结构，现在才发现，其实链表是一种逻辑结构！
比较点结构体/类模拟Node数组模拟Node
节点本身指针物理地址，node通过在数组下标，表示自身指针
数值域就在结构体中定义node.valval[node]，通过数组来存储数值域
指针域结构体中定义,node. nextnext[node],通过数组来存储

图解

插入操作（头插法）

2.双链表

学习了数组模拟单链表，其实双链表就很好理解了。其实就是多了一个指针域。

  • 单链表：ne[i]存储指针为i的节点的next指针
  • 双链表
    • l[i],指针为i的节点的前驱（指向前一个节点）
    • r[i],指针为i的节点的后驱（指向后一个节点）
//e[index],表示节点的值，l[index]表示节点的左指针，r[index]表示节点的右指针，idx表示当前用到哪个节点的”地址“

int e[N],l[N],r[N],idx;

//初始化
void init(){
  //0是左端点，1是右端点
  r[0] = 1,l[1] = 0;
  idx = 2;
}
//在节点a的右边插入一个数x
void insert(int a,int x){
  //1、让待插入节点占位
  e[idx] = x;
  //2、处理待插入点左右两侧
  l[idx] = a,r[idx] = r[a];//注意，这里必须是r[a]，因为a的下一个节点不一定和a顺序存储
  //3、处理前一个节点和后一个节点
  l[r[a]] = idx,r[a] = idx++;
}


Java岛冒险记【从小白到大佬之路】

LeetCode每日一题–进击大厂

图解表spanclasstoken算法$数据结构$java$c++$链表

有关【算法基础】数据结构| 单链表+双链表 代码实现+图解+原理的更多相关文章

  1. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  4. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  5. ruby-on-rails - 浏览 Ruby 源代码 - 2

    我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru

  6. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  7. ruby - 模块嵌套代码风格偏好 - 2

    我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的

  8. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  9. ruby - Net::HTTP 获取源代码和状态 - 2

    我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

  10. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

随机推荐