数据结构与算法_双向链表

package chapter02
import util.control.Breaks._
object test05 {
  def main(args:Array[String]):Unit={

    val DoubleLinkedList = new DoubleLinkedList()


    DoubleLinkedList.add(new HeroNode2(1,"宋江","及时雨"))
    DoubleLinkedList.add(new HeroNode2(2,"卢俊义","玉麒麟"))
    DoubleLinkedList.add(new HeroNode2(3,"吴用","智多星"))
    DoubleLinkedList.add(new HeroNode2(4,"张飞","亿得"))
    println("修改前")
    DoubleLinkedList.list()

    DoubleLinkedList.update(new HeroNode2(4,"公松胜","入云龙"))
    println("修改后")
    DoubleLinkedList.list()


    println("删除后的链表的情况")
    DoubleLinkedList.delete(1)
    DoubleLinkedList.delete(2)
    DoubleLinkedList.delete(3)
    DoubleLinkedList.delete(4)
    DoubleLinkedList.list()
//    DoubleLinkedList.delete(5)

  }

}




class DoubleLinkedList {
  //头节点：指向该链表的头节点
  val head = new HeroNode2(-1, "", "")

  //判断链表是否为空
  def isEmpty():Boolean={
    head.next == null
  }

  //添加英雄人物到链表的最后
  def add(heroNode: HeroNode2):Unit={
    //找到最后节点，最后节点指向需要添加的节点
    //因为head不能动，需要辅助指针完成定位
    var temp=head
    breakable {
      while (true) {
        if (temp.next == null) {
          //已经到链表的最后
          break()
        }
        temp = temp.next //temp 后移
      }
    }//退出循环时，temp指向最后
    temp.next=heroNode
    heroNode.pre=temp
  }

  //遍历单向列表
  def list(): Unit = {
    if (isEmpty()) {
      println("链表为空")
      return
    }
    var temp = head.next //有效数据不在head
    breakable{
      while (true) {
        println(temp.no, temp.name, temp.nickname)
        if (temp.next == null) { //已经是最后节点
          break()
        }
        temp = temp.next //后移
      }
    }

  }


  //修改节点信息
  def update(heroNode: HeroNode2):Unit={
    if(isEmpty()){
      println("链表为空，无法修改")
    }

    //定位到需要修改的节点
    //定义一个变量，标识是否找到该节点
    var temp=head.next
    var flag= false
    breakable {
      while (true) {
        if (temp.no == heroNode.no) { //找到了
          flag = true
          break()
        }
        //继续判断temp是否到最后
        if (temp.next == null) { //最后
          break()
        }
        temp = temp.next

      }
    }
    if(flag){
      //找到
      temp.name = heroNode.name
      temp.nickname = heroNode.nickname
    }else{
      println("没找到")
    }

  }


  //删除一个节点
  def delete(no: Int):Unit={
    if(isEmpty()){
      println("链表为空，无法删除")
      return
    }
    var flag=false
    var temp = head.next
    breakable {
      while (true) {
        if (temp.no == no) { //找到了
          flag = true
          break()
        }
        //继续判断temp是否到最后
        if (temp.next == null) { //最后
          break()
        }
        temp = temp.next
      }
    }
    if(flag){
      temp.pre.next=temp.next
      if (temp.next!=null){
        temp.next.pre=temp.pre
      }


    }else{
      println("不存在要删除的节点")
    }
  }


}




class HeroNode2(hNo:Int,hname:String,hnikename:String){
  val no = hNo
  var name = hname
  var nickname = hnikename
  var next:HeroNode2 = null
  var pre:HeroNode2 = null
}