单链表的创建和遍历的分析实现(思路分析) [数据结构][Java]

单链表的创建和遍历的分析实现(思路分析)

前面我们讲过了单链表的概述,这里我们来讲述如何完成单链表的创建和遍历

这里我们提出一个问题,我们直接来解决这个问题就可以了:

使用带head结点(头结点)的单向链表来实现 — 水浒英雄排行榜管理

1. 完成对人物的增删改查操作:
2. ① 第一种方式在添加英雄时,直接添加到链表的尾部就可以了
   ② 第二种方式添加英雄的时候,根据英雄的排名将英雄添加到指定的位置上,如果排名重复则添加失败,并且给出提示
   • 英雄排名就是一个属性,这个属性记录了英雄的排名

这里如何完成单链表的增加元素的操作和遍历的操作:

• 这里的增加元素的方式就是直接添加到链表的尾部

那么我们要如何来实现?

• 首先我们进行一个思路分析:

  1. 我们要定义个结点类

     • 结点类中有数据域和指针域,数据域中就是存储水浒英雄的一些属性,比如说英雄的排名等等,指针域则是指向下一个节点(节点又称之为:结点)

  2. 创建一个链表类: —> 这个类中有创建单链表和给单链表添加元素,还有遍历单链表的方法

     • 注意: 我们添加元素的操作其实就是将我们的每个元素都依次添加到链表的最后

       • 不考虑英雄排名的顺序将我们的结点添加到单向链表中的思路分析:

         1. 找到当前这个链表的最后一个结点
         2. 将找到的链表中的最后一个节点的指针域指向我们要添加的这个新的节点

     • 我们在做遍历操作的时候一定要创建一个辅助变量(指针),这个辅助变量(指针)的作用就是帮助我们来遍历链表

       • 那么我们为什涉及到遍历就要通过一个辅助变量(指针)来完成?

         • 因为我们涉及到遍历操作的时候我们就要一个一个节点的去遍历,我们对于遍历的操作肯定是要放到循环中实现,那么在循环中我们可以通过第一个节点获取到第二个节点,但是当我们使用第一个节点调用next属性获得第二个节点的时候,这个时候我们就不能获取到第三个结点了,因为我们的获取到的第二个节点都还是临时的,所以我们就要让我们获取到的第二个节点固定下来,这个时候我们就要使用一个变量来接收这个第二个节点,这样我们的第二个节点就被固定了下来,那么我们就可以使用这个固定的结点去完成一个循环,一直向下遍历:
           • 总结: 其实我们遍历就是从第一个节点走到最后一个节点,那么我们就要使用一个临时变量(或者说辅助变量或者辅助指针)去和我们所有的结点一个一个的去接触 —> 就是将一个个的结点都赋给temp变量

  3. 编写一个测试类进行测试

补充:

链表是没有大小限制的,所以我们在向链表中添加元素的时候不需要判断链表是否已满

• 链表是不会满的 —> 除非内存被占用完

补充二:

执行链表的遍历的时候要注意: 如果链表的头指针为空 , 此时我们就不能进行一个遍历 ,因为此时我们的链表其实是不存在的 , 因为此时我们的头指针指向了空 , 就说明我们都还没有头结点 ,此时我们如果遍历就会发生空指针异常

• 难点分析: 这个时候一定要注意: 我们java是面向对象编程 ,对于一个链表我们肯定也是封装为一个类 , 对于链表对象的一些操作我们都会放到这个类中去 , 我们会将这些一个一个的操作编写成为一个一个的方法 , 我们如果具体要使用的时候就去调用这些方法即可 , 那么此时我们的链表已经被我们封装成为了一个类 , 那么我们要获得一个链表的对象的时候就要通过这个链表类的构造器创建一个链表类的对象 , 创建好了对象之后我们再去调用方法

  • 注意: 这个时候问题来了: 如果这个时候我们调用这个对象来调用一个方法的时候出现了一个控空指针异常,那么这个时候这个空指针异常发生的原因是什么? 是我们没有创建链表对象? —> 不是的 ,我们已经创建好了链表的对象, 那么这个空指针异常究竟是因为什么? —> 其实我们可以推断出来 ,这个时候空指针异常肯定是发生在了我们的这个对象调用的方法中 , 这个时候很大的可能就是我们的头指针为空导致的空指针异常 , 我们一般在链表类中都是会声明一个成员属性表示链表的头结点 , 我们需要通过这个头结点来完成一系列对链表的操作 , 包括增删改查等等等等一系列的操作 , 所以我们一定要注意 : 一定要记的判断我们的头指针是否为空 ! ! ! ,从而避免问题的发生 , 我们一定要养成一个好的编程思想和编程习惯