数据结构之单链表

  • Post author:
  • Post category:其他



在这里插入图片描述
在这里插入图片描述



一、链表的组成

链表是由一个一个的节点组成的,节点又是一个一个的对象,

相邻的节点之间产生联系,形成一条链表。

例子:假如现在有两个人,A和B,A保存了B的联系方式,这俩人之间就有了联系。

A和B就好比是节点,一个节点保存另一个节点的地址,这两个节点之间就产生了联系。



二、链表的重要的两类



一、单向非循环不带头链表的特点



1、单链表的尾节点

例子1:一条横线都有结束的标志,当这条横线的尾端不再延申,这条横线就是结束了。

例子2:一个人的手机通讯录中没有保存任何人的联系方式,通讯录中显示“空”这个汉字。

这条横线就好比是单链表,单链表也应该有结束的标志。

刚才这个人就好比是单链表中的最后一个节点,也就是尾节点,这个节点没有保存任何一个节点的地址,应该显示为null。



2、相邻节点之间的关系

例子:现在有一排宝箱,第一个宝箱里面放着第二个宝箱的钥匙,第二个宝箱里面放着第三个宝箱的钥匙。

宝箱就好比是节点,钥匙就好比是对象的地址,相邻的节点,前面的节点保存后面的节点的地址。



3、如何依次访问这条链表中的所有节点。

在解释这个问题之前,有1个知识需要我们了解:

1:例子:如果家里的人想要联系在外地打拼的年轻人,需要存下他们的电话号码或者地址,通过电话号码和地址就可以找到他,否则是无法是找到的。

年轻人就好比是Java中的对象,如果想要找到存放在堆中的对象,需要把对象的地址存到引用变量中,通过地址就可以找到这个对象。

例子:就拿我们刚才宝箱那个例子来说,如果我们想要访问每一个宝箱,看看里面有什么好东西,必须要得到第一个宝箱的钥匙,打开第一个宝箱,得到第二个宝箱的钥匙,打开第二个宝箱,得到第三个宝箱的钥匙,以此类推。

宝箱就是节点,钥匙就是地址。

结合这两个例子和上面说的相邻节点之间的关系,我们可以理解:

要得到第一个节点的地址,才能访问所有节点。


所以,将头节点的地址保存到一个引用变量head中,通过head,成功访问链表中的所有节点



1、具体是如何通过一个引用变量访问所有节点的呢?

在这里插入图片描述

例子:现在有五个人,分别在五个村子中,第一个人保存了第二个人的地址,第二个人保存了第三个人的地址,以此类推,第五个人谁的地址也没有保存,现在有一个中年老男人想要去找这五个人,他先是得到了第一个人的地址,找到第一个人后,让第一个人给了他第二个人的地址,就找到了第二个人,以此类推,五个人全都找到了。

这个中年老男人就好比是一个引用变量,这五个人就好比是五个节点,先让引用变量存储第一个节点的地址,找到第一个节点,在通过第一个节点找到第二个节点,依次类推,可以找到所有节点。



2、产生的问题

例子:我一只手只能放一个东西,如果想让我去拿另一个东西,我需要把目前手上的东西扔了,再去拿。

引用变量只能放一个对象的地址,如果我直接通过head依次去保存每一个对象的地址,访问每一个节点,那么访问完之后,head里面放的是null,第一个节点的地址就得不到了。


所以应该找个“替死鬼”,声明一个新的变量,将head里面的值拷贝到新的变量中



版权声明:本文为weixin_53908084原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。