链表(Linked List)

1. 链表(Linked List)
   1. 链表介绍

链表是有序的列表，但是它在内存中是存储如下

小结

1. 链表是一个有序列表
2. 链表的数据，在内存空间不一定是连续分布的.
   1. 单链表的介绍

   单链表(带头结点) 逻辑结构示意图如下 //

   

   所谓带头节点，就是链表的头有一个head节点, 该节点不存放具体的数据，只是为了操作方便而设计的这个节点.

   1. 单链表的应用实例

   使用带head头的单向链表实现 –水浒英雄排行榜管理

3. 完成对英雄人物的增删改查操作， 注: 删除和修改,查找可以考虑学员独立完成

   思路分析:

   

   代码实现

   package com.atguigu.chapter18.linkedlist ? import util.control.Breaks._ ? object SingleLinkedListDemo { def main(args: Array[String]): Unit = { //测试单向链表的添加和遍历 val hero1 = new HeroNode(1, "宋江", "及时雨") val hero2 = new HeroNode(3, "宋江3", "及时雨3") val hero3 = new HeroNode(4, "宋江4", "及时雨4") val hero4 = new HeroNode(2, "宋江2", "及时雨2") //创建一个单向链表 val singleLinkedList = new SingleLinkedList singleLinkedList.add(hero1) singleLinkedList.add(hero2) singleLinkedList.add(hero3) singleLinkedList.add(hero4) ? // singleLinkedList.add2(hero1) // singleLinkedList.add2(hero2) // singleLinkedList.add2(hero3) // singleLinkedList.add2(hero4) singleLinkedList.list() ? val hero5 = new HeroNode(3, "吴用", "智多星") singleLinkedList.update(hero5) println("==========================") singleLinkedList.list() ? println("@@@@@@@@@@测试删除@@@@@@@@@@@") singleLinkedList.del(4) singleLinkedList.del(2) singleLinkedList.del(1) singleLinkedList.list() } } ? //定义我们的单向链表管理Hero class SingleLinkedList { ? //先初始化一个头结点, 头结点一般不会动 val head = new HeroNode(0, "", "") ? //删除节点 //1. 思路 // 删除的思路 // 1). head 不能动 // 2). 使用temp变量, 我们要删除的应该是temp 的下一个结点., 即，我们在比较时，始终比较的是 temp.next 的节点值 ? //2. 代码 ? def del(no: Int): Unit = { var temp = head var flag = false // 标志变量用于确定是否有要删除的节点 breakable { while (true) { if (temp.next == null) { break() } if (temp.next.no == no) { //找到了 flag = true break() } temp = temp.next //temp后移 } } ? if (flag) { //可以删除 temp.next = temp.next.next ? } else { printf("要删除的no=%d 不存在\n" , no) } } ? //修改节点的值, 根据no编号为前提修改, 即no不能改 //课后思考题： 如果将这个节点替换，如何实现 def update(newHeroNode: HeroNode): Unit = { if (head.next == null) { println("链表为空") return } //先找到节点 var temp = head.next var flag = false breakable { while (true) { if (temp == null) { break() } if (temp.no == newHeroNode.no) { //找到. flag = true break() } temp = temp.next // } } //判断是否找到 if (flag) { temp.name = newHeroNode.name temp.nickname = newHeroNode.nickname } else { printf("没有找到 编号为%d 节点，不能修改\n", newHeroNode.no) } ? } ? //编写添加方法 //第一种方法在添加英雄时，直接添加到链表的尾部 def add(heroNode: HeroNode): Unit = { //因为头结点不能动, 因此我们需要哟有一个临时结点，作为辅助 var temp = head //找到链表的最后 breakable { while (true) { if (temp.next == null) { //说明temp已经是链表最后 break() } //如果没有到最后 temp = temp.next } } //当退出while循环后，temp就是链表的最后 temp.next = heroNode } ? //第二种方式在添加英雄时，根据排名将英雄插入到指定位置 //如果有这个排名，则添加失败，并给出提示 //编号从小到大排序 //思路 def add2(heroNode: HeroNode): Unit = { //因为头结点不能动, 因此我们需要哟有一个临时结点，作为辅助 //注意，我们在找这个添加位置时，是将这个节点加入到temp的后面 //因此，在比较时，是将当前的heroNode 和 temp.next 比较 var temp = head var flag = false // flag 是用于判断是否该英雄的编号已经存在, 默认为false breakable { while (true) { if (temp.next == null) { //说明temp已经是链表最后 break() } if (temp.next.no > heroNode.no) { //位置找到，当前这个节点，应当加入到temp后 break() } else if (temp.next.no == heroNode.no) { //已经有这个节点 flag = true break() } temp = temp.next // 注意 } } if (flag) { // 不可以加入 printf("待插入的英雄编号 %d 已经有了，不能加入\n", heroNode.no) } else { //加入，注意顺序 heroNode.next = temp.next temp.next = heroNode } } ? ? //遍历单向链表 def list(): Unit = { ? //判断当前链表是否为空 if (head.next == null) { println("链表为空!!") return } //因为头结点不能动, 因此我们需要哟有一个临时结点，作为辅助 //因为head 结点数据，我们不关心，因此这里 temp=head.next var temp = head.next breakable { while (true) { //判断是否到最后 if (temp == null) { break() } printf("结点信息 no=%d name=%s nickname=%s\n", temp.no, temp.name, temp.nickname) temp = temp.next } } } ? } ? //先创建HeroNode class HeroNode(hNo: Int, hName: String, hNickname: String) { var no: Int = hNo var name: String = hName var nickname: String = hNickname var next: HeroNode = null //next 默认为null } ?

   ?

   ?

   1. 双向链表的应用实例

   使用带head头的双向链表实现 –水浒英雄排行榜

   管理单向链表的缺点分析:

4. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
5. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp的下一个节点来删除的(认真体会).
6. 示意图帮助理解删除

   

7. 将前面的单向链表改成双向链表

   package com.atguigu.chapter18.linkedlist ? import scala.util.control.Breaks.{break, breakable} ? object DoubleLinkedListDemo { def main(args: Array[String]): Unit = { ? //测试单向链表的添加和遍历 val hero1 = new HeroNode2(1, "宋江", "及时雨") val hero2 = new HeroNode2(3, "宋江3", "及时雨3") val hero3 = new HeroNode2(4, "宋江4", "及时雨4") val hero4 = new HeroNode2(2, "宋江2", "及时雨2") //创建一个单向链表 val doubleLinkedList = new DoubleLinkedList doubleLinkedList.add(hero1) doubleLinkedList.add(hero2) doubleLinkedList.add(hero3) doubleLinkedList.add(hero4) ? doubleLinkedList.list() ? val hero5 = new HeroNode2(2, "卢俊义", "玉麒麟") doubleLinkedList.update(hero5) println("--------------------------") doubleLinkedList.list() ? //删除测试 doubleLinkedList.del(2) doubleLinkedList.del(3) doubleLinkedList.del(4) println("删除后") doubleLinkedList.list() //加入 doubleLinkedList.add(hero2) println("~~~~~~~~~~~~") doubleLinkedList.list() } } ? ? class DoubleLinkedList { //先初始化一个头结点, 头结点一般不会动 val head = new HeroNode2(0, "", "") ? //添加-遍历-修改-删除 //编写添加方法 //第一种方法在添加英雄时，直接添加到链表的尾部 def add(heroNode: HeroNode2): Unit = { //因为头结点不能动, 因此我们需要哟有一个临时结点，作为辅助 var temp = head //找到链表的最后 breakable { while (true) { if (temp.next == null) { //说明temp已经是链表最后 break() } //如果没有到最后 temp = temp.next } } //当退出while循环后，temp就是链表的最后 temp.next = heroNode heroNode.pre = temp ? } ? //遍历方法一样, 不用 def list(): Unit = { ? //判断当前链表是否为空 if (head.next == null) { println("链表为空!!") return } //因为头结点不能动, 因此我们需要哟有一个临时结点，作为辅助 //因为head 结点数据，我们不关心，因此这里 temp=head.next var temp = head.next breakable { while (true) { //判断是否到最后 if (temp == null) { break() } printf("结点信息 no=%d name=%s nickname=%s\n", temp.no, temp.name, temp.nickname) temp = temp.next } } } ? //修改节点的值, 根据no编号为前提修改, 即no不能改 //课后思考题： 如果将这个节点替换，如何实现 def update(newHeroNode: HeroNode2): Unit = { if (head.next == null) { println("链表为空") return } //先找到节点 var temp = head.next var flag = false breakable { while (true) { if (temp == null) { break() } if (temp.no == newHeroNode.no) { //找到. flag = true break() } temp = temp.next // } } //判断是否找到 if (flag) { temp.name = newHeroNode.name temp.nickname = newHeroNode.nickname } else { printf("没有找到 编号为%d 节点，不能修改\n", newHeroNode.no) } ? } ? //删除 //思路，因为双向链表可以实现自我删除 def del(no: Int): Unit = { ? //判断当前链表是否为空 if (head.next == null) { println("链表空") return } ? var temp = head.next var flag = false // 标志变量用于确定是否有要删除的节点 breakable { while (true) { if (temp == null) { break() } if (temp.no == no) { //找到了 flag = true break() } temp = temp.next //temp后移 } } ? if (flag) { //可以删除 //temp.next = temp.next.next temp.pre.next = temp.next //思考 if (temp.next != null) { temp.next.pre = temp.pre } ? ? } else { printf("要删除的no=%d 不存在\n" , no) } } ? } ? //先创建HeroNode class HeroNode2(hNo: Int, hName: String, hNickname: String) { var no: Int = hNo var name: String = hName var nickname: String = hNickname var pre: HeroNode2 = null // pre 默认为null var next: HeroNode2 = null //next 默认为null }

   ?

   1. 单向环形链表的应用场景

   Josephu 问题

   Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

   ?

   提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

   ?

   1. 环形单向链表的应用实例

   使用环形单向链表来解决, Josephu问题

   代码和分析

   

   

   代码实现:

   package com.atguigu.chapter18.linkedlist ? import util.control.Breaks._ ? object Josephu { def main(args: Array[String]): Unit = { //创建BoyGame val boyGame = new BoyGame boyGame.addBoy(70) boyGame.showBoy() //测试countBoy方法 boyGame.countBoy(41, 30, 70) } } ? //定义Boy类 class Boy(bNo: Int) { val no: Int = bNo var next: Boy = null } ? //编写核心类BoyGame class BoyGame { //定义一个初始的头结点, var first: Boy = new Boy(-1) ? //添加小孩【形成一个单向环形的链表】 //nums ： 表示共有几个小孩 def addBoy(nums: Int): Unit = { ? if (nums < 1) { println("nums的值不正确") return } //在形成环形链表时，需要一个辅助指针 var curBoy: Boy = null ? for (no <- 1 to nums) { //更加编号创建小孩对象 val boy = new Boy(no) //如果是第一个小孩 if (no == 1) { first = boy first.next = first // 形成一个环形的链表 curBoy = first } else { curBoy.next = boy boy.next = first curBoy = boy } } ? } ? //编写方法countBoy, 完成游戏 //startNo 从第几个人开始数 //countNum 数几下 //nums: 一共多少人 def countBoy(startNo: Int, countNum: Int, nums: Int): Unit = { //对参数进行判断 if (first.next == null || startNo < 1 || startNo > nums) { println("参数有误，重新输入!") return } //完成游戏的思路 /* 完成游戏的思路分析->实现代码 ? 1) 在first 前面 设计一个辅助指针（helper） , 即将helper 指针定位到 first 前面 2) 将first 指针移动到 startNo 这个小孩(helper 对应移动) 3) 开始数 countNum 个数[first 和 helper 会对应的移动] 4) 删除first 指向的这个小孩节点 5) 思路 ? */ var helper = first //1)即将helper 指针定位到 first 前面 breakable { while (true) { if (helper.next == first) { break() } helper = helper.next } } //2)将first 指针移动到 startNo 这个小孩(helper 对应移动) for (i <- 0 until startNo - 1) { first = first.next helper = helper.next } ? // 开始数数，按照给定的值，每数到一个小孩就出圈, 直到环形链表只有一个节点 breakable { while (true) { if (helper == first) { //只有一个人 break() } //3) 开始数 countNum 个数[first 和 helper 会对应的移动] for (i <- 0 until countNum - 1) { // 3 first = first.next helper = helper.next } //输出出圈的人的信息 printf("小孩%d出圈\n", first.no) //将first 指向的节点删除 first = first.next helper.next = first } } //当while结束后, 只有一个人 printf("最后留在圈的人是 小孩编号为 %d\n", first.no) ? ? } ? //遍历单向的环形链表 def showBoy(): Unit = { if (first.next == null) { println("没有任何小孩~") return } //因为first不能动，还是借助一个辅助指针完成遍历 var curBoy = first ? breakable { while (true) { printf("小孩编号 %d\n", curBoy.no) if (curBoy.next == first) { break() } curBoy = curBoy.next //curBoy后移 } } } }

   ?

链表(Linked List)

原文：https://www.cnblogs.com/shuzhiwei/p/11210112.html