devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之链表（单链表，双链表）知识汇总（包含面试题）_单链表和双链表

作者：IT小白 | 2024-05-27 06:02:17

赞

踩

单链表和双链表

一.链表总体介绍：

1.单链表：（single linked list）

每个链表有一个next指针指向下一个节点，还有一个成员用来存储数值

2.双链表：（Douuble Linked List）

在单链表基础之上，还有一个prev指针指向前一个节点。

 3.小结：

（1）链表是以节点的方式来存储

（2）每个节点包含data域，next域：指向下一个节点

（3）链表的每个节点都不是连续存储的

（4）链表分有头节点的和不带头节点的，根据实际需求来定

 第一个节点的data域为null，尾节点的next域为null

二.单链表

（1）添加（创建）

   <1>先创建一个head头节点，作用是表示单链表的头

   <2>后面每添加一个节点，就直接加到链表的最后

   

 

 

  1. //先创建节点
  2.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  3.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  4.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  5.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  6.  
  7.         //创建要给链表
  8.         SingleLinkList singleLinkList = new SingleLinkList();
  9.         //加入
  10.         /**singleLinkList.add(hero1);
  11.         singleLinkList.add(hero2);
  12.         singleLinkList.add(hero3);
  13.         singleLinkList.add(hero4);
  14.          */
  15.  
  16.         //第二种加入方式（按照编号的顺序加入）
  17.         singleLinkList.addByOrder(hero4) ;
  18.         singleLinkList.addByOrder(hero2) ;
  19.         singleLinkList.addByOrder(hero3) ;
  20.         singleLinkList.addByOrder(hero1) ;

（2）遍历链表

因为头节点，不能动，因此我们需要一个辅助变量来遍历

  1. public void list() {
  2.         //判断链表是否为空
  3.         if (head.next == null) {
  4.             System.out.println("链表为空");
  5.             return;
  6.         }
  7.         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
  8.         HeroNode temp = head.next;
  9.         while(true){
  10.             //判断是否到链表最后
  11.             if( temp == null){
  12.             break;
  13.             }
  14.             //输出节点的信息（说明已经到最后了）
  15.             System.out.println(temp);
  16.             //将temp后移，一定小心
  17.             temp = temp.next;

（3）删除节点

思路

1.head 不能动，因此我们需要一个temp 辅助变量来找到待删除节点的前一个节点

2.说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较

  1.   public void del(int no){
  2.            HeroNode temp = head;
  3.            boolean flag = false;//标志是否找到待删除的节点
  4.         while (true) {
  5.             if(temp.next == null){
  6.                 //已经到链表最后
  7.                 break;
  8.             }
  9.             if(temp.next.no == no){
  10.                 //找到的待删除节点的前一个节点temp
  11.                 flag = true;
  12.                 break;
  13.             }
  14.             temp = temp.next;//temp后移，遍历
  15.         }
  16.         //判断flag
  17.         if(flag){//找到
  18.             //可以删除
  19.             temp.next = temp.next.next;
  20.         }else{
  21.             System.out.println("要删除的" +no + "节点不存在！");
  22.         }
  23.     }

（4）修改节点的信息

根据no编号来修改，no编号不能动

  1. public void update (HeroNode newHeroNode){
  2.         //判断是否为空
  3.         if(head.next == null){
  4.             System.out.println("链表为空");
  5.             return;
  6.         }
  7.         //找到需要修改的编号，根据no编号
  8.         //定义一个辅助变量
  9.         HeroNode temp = head.next;
  10.         boolean flag = false;//表示是否找到该节点
  11.         while (true) {
  12.             if(temp==null){
  13.                 break;//已经遍历完该链表
  14.             }
  15.             if(temp.no == newHeroNode.no){
  16.                 //找到
  17.                 flag = true;
  18.                 break;
  19.             }
  20.             temp = temp.next;
  21.         }
  22.         //根据flag判断是否找到要修改的节点
  23.         if(flag){
  24.             temp.name = newHeroNode.name;
  25.             temp.nickname = newHeroNode.nickname;
  26.         }else{
  27.             //没有找到
  28.             System.out.println("没有找到该编号" + newHeroNode.no + "不能修改！");
  29.         }
  30.     }

（5）添加节点到单链表的两种方式

 

第一种

  1.     public void add(HeroNode heroNode) {
  2.         //因为head节点不能动，因此我们需要一个辅助遍历 temp
  3.         HeroNode temp = head;
  4.         //遍历单链表，找到最后
  5.         while (true) {
  6.             //找到链表的最后
  7.             if (temp.next == null) {
  8.                 break;
  9.             }
  10.             //如果没有找到最后，将会把temp后移
  11.             temp = temp.next;
  12.         }
  13.         //当退出while循环时，temp指向了链表的最后
  14.         //将最后的这个节点的next 指向新的节点
  15.         temp.next = heroNode;
  16.     }

第二种

  1. public void addByOrder(HeroNode heroNode){
  2.         //因为头节点不能动，所以我们仍然需要通过一个辅助指针（变量）来帮助找到添加的位置
  3.         //因为单链表，因为我们找的temp是位于添加辅助位置的前一个节点，否则插入不了
  4.         HeroNode temp = head;
  5.         boolean flag = false;
  6.         while(true){
  7.             if(temp.next == null){
  8.                 //说明temp已经到了链表的最后
  9.                 break;
  10.             }
  11.             if(temp.next.no > heroNode.no ){
  12.                 //位置找到了，就在temp的后面插入
  13.                 break;
  14.             }else if(temp.next.no == heroNode.no){
  15.                 //说明希望添加的heroNode的编号已将存在
  16.                 flag = true;//说明编号存在
  17.                 break;
  18.             }
  19.             temp = temp.next;//遍历，后移
  20.         }
  21.         //判断flag的值
  22.         if(flag){
  23.             //不能添加，说明编号存在
  24.             System.out.println("准备插入的英雄的编号" + heroNode.no + "已经存在了，不能加入了！");
  25.         }else{
  26.             //插入到链表中，temp的后面
  27.             heroNode.next  = temp.next;
  28.             temp.next = heroNode;
  29.         }
  30.     }

（6）初始化头节点

  1.  private HeroNode head = new HeroNode(0, "", "");
  2.  
  3.        //返回头节点
  4.        public HeroNode getHead() {
  5.             return head;
  6.        }

3.单链表面试题

（1）获取单链表的元素个数

方法：获取到单链表的节点的个数（如果是带头节点的链表，需求不统计头节点

head 链表的头节点 返回的就是有效节点的个数

  1.  public static int getLength(HeroNode head){
  2.         if(head.next == null){
  3.             //空链表
  4.             return 0;
  5.         }int length = 0;
  6.         //定义一个辅助变量
  7.         HeroNode cur = head.next;
  8.         while(cur != null){
  9.             length++;
  10.             cur = cur.next;//遍历
  11.         }
  12.         return length;
  13.     }

（2）查找单链表中倒数第k个元素（新浪）

思路： 1.编写一个方法，接收head节点，同时接收一个index

2.index 表示是倒数第k个节点

3.先把链表从头到尾遍历，得到链表的总长度getlength

4.得到size之后，我们从链表的第一个开始遍历（getlength - index）个，就可以得到

5.如果找到了，就返回该节点，否则返回null

  1.  public static HeroNode findLastIndexNode(HeroNode head,int index){
  2.         //判断如果链表为空，则返回null
  3.          if(head.next == null){
  4.              return null;//没有找到
  5.          }
  6.          //第一个遍历得到链表的长度（节点个数）
  7.          int size = getLength(head);
  8.          //第二次遍历 size - index 位置，就是我们倒数第k个节点啊
  9.          //先做一个index的校验
  10.          if(index <=0 || index > size){
  11.              return null;
  12.          }
  13.          //定义个辅助变量
  14.          HeroNode cur = head.next;
  15.          for (int i = 0; i < size - index; i++) {
  16.              cur = cur.next;
  17.          }
  18.          return cur;
  19.      }

（3）单链表的反转（腾讯）

  1.  public static void reversetList(HeroNode head){
  2.         //如果当前链表为空，或者只有一个节点，则无需反转，直接返回
  3.         if(head.next == null || head.next.next == null){
  4.             return ;
  5.         }
  6.         //定义一个辅助变量（指针），帮助我们遍历原来的链表
  7.         HeroNode cur = head.next;
  8.         HeroNode next = null;//指向当前节点[cur]
  9.         HeroNode reverseHead = new HeroNode(0,"","");
  10.         //遍历原来的链表，遍历每一个节点，就将其取出，并放在新的链表reversetList的最前端
  11.         //有难度
  12.         while(cur != null){
  13.             next = cur.next;//先暂时保存当前节点的下一个节点，因为后面要用到
  14.             cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端（将两个节点相连）
  15.             reverseHead.next = cur;//让新链表的头部与cur连接（接第一根线）
  16.             cur = next;//让cur后移
  17.         }
  18.         //
  19.         head.next = reverseHead.next;
  20.     }

（4）逆序打印单链表（百度）

可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出特性，就实现了单链表的逆序打印

  1. public static void reversePrint(HeroNode head){
  2.         if(head.next == null){
  3.             return;//空链表，不能打印
  4.         }
  5.         //创建要给一个栈，将各个节点压入栈
  6.         Stack<HeroNode>stack = new Stack<HeroNode>();
  7.         HeroNode cur = head.next;
  8.         //将链表的所有节点都压入栈
  9.         while(cur != null){
  10.             stack.push(cur);
  11.             cur = cur.next;//cur 后移这样就可以压入下一个节点了
  12.         }
  13.         //将栈中的节点进行打印，pop出栈
  14.         while(stack.size() > 0){
  15.             System.out.println(stack.pop());//stack的特点就是先进后出
  16.         }
  17.     }

4.单链表总体演示

  1. package LinkedList;
  2.  
  3. import java.util.Stack;
  4.  
  5. public class SingleLinkedListDemo {
  6.     public static void main(String[] args) {
  7.         //进行测试
  8.         //先创建节点
  9.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  10.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  11.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  12.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  13.  
  14.         //创建要给链表
  15.         SingleLinkList singleLinkList = new SingleLinkList();
  16.         //加入
  17.         /**singleLinkList.add(hero1);
  18.         singleLinkList.add(hero2);
  19.         singleLinkList.add(hero3);
  20.         singleLinkList.add(hero4);
  21.          */
  22.  
  23.         //第二种加入方式（按照编号的顺序加入）
  24.         singleLinkList.addByOrder(hero4) ;
  25.         singleLinkList.addByOrder(hero2) ;
  26.         singleLinkList.addByOrder(hero3) ;
  27.         singleLinkList.addByOrder(hero1) ;
  28.  
  29.         //测试修改的代码
  30.         System.out.println("--------------------");
  31.         HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟~~~");
  32.         singleLinkList.update(newHeroNode);
  33.         singleLinkList.list();
  34.         /**
  35.          * 有问题，在修改处
  36.          */
  37.  
  38.         //显示
  39.         System.out.println("-------------------");
  40.         singleLinkList.list();
  41.  
  42.         //删除一个节点
  43.         singleLinkList.del(1);
  44.         System.out.println("删除后的链表情况");
  45.         singleLinkList.list();
  46.  
  47.         System.out.println("-------单链表中有效节点的个数--------");
  48.         System.out.println(getLength(singleLinkList.getHead()));
  49.  
  50.         System.out.println("-----------得到倒数第k个节点------------");
  51.         HeroNode res = findLastIndexNode(singleLinkList.getHead(),2);
  52.         System.out.println(res);
  53.  
  54.         System.out.println("------------测试一下单链表的反转功能,结构改变了------------");
  55.         reversetList(singleLinkList.getHead());
  56.         singleLinkList.list();
  57.  
  58.         System.out.println("------------逆序打印单链表，不改变链表结构-------------");
  59.         reversePrint(singleLinkList.getHead());
  60.     }
  61.  
  62.     /**逆序打印单链表*/
  63.     //可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出特性，就实现了单链表的逆序打印
  64.     public static void reversePrint(HeroNode head){
  65.         if(head.next == null){
  66.             return;//空链表，不能打印
  67.         }
  68.         //创建要给一个栈，将各个节点压入栈
  69.         Stack<HeroNode>stack = new Stack<HeroNode>();
  70.         HeroNode cur = head.next;
  71.         //将链表的所有节点都压入栈
  72.         while(cur != null){
  73.             stack.push(cur);
  74.             cur = cur.next;//cur 后移这样就可以压入下一个节点了
  75.         }
  76.         //将栈中的节点进行打印，pop出栈
  77.         while(stack.size() > 0){
  78.             System.out.println(stack.pop());//stack的特点就是先进后出
  79.         }
  80.     }
  81.  
  82.     /**将单链表反转*/
  83.     public static void reversetList(HeroNode head){
  84.         //如果当前链表为空，或者只有一个节点，则无需反转，直接返回
  85.         if(head.next == null || head.next.next == null){
  86.             return ;
  87.         }
  88.         //定义一个辅助变量（指针），帮助我们遍历原来的链表
  89.         HeroNode cur = head.next;
  90.         HeroNode next = null;//指向当前节点[cur]
  91.         HeroNode reverseHead = new HeroNode(0,"","");
  92.         //遍历原来的链表，遍历每一个节点，就将其取出，并放在新的链表reversetList的最前端
  93.         //有难度
  94.         while(cur != null){
  95.             next = cur.next;//先暂时保存当前节点的下一个节点，因为后面要用到
  96.             cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端（将两个节点相连）
  97.             reverseHead.next = cur;//让新链表的头部与cur连接（接第一根线）
  98.             cur = next;//让cur后移
  99.         }
  100.         //
  101.         head.next = reverseHead.next;
  102.     }
  103.  
  104.     /**查找单链表中倒数第k个节点*/
  105.     //思路：
  106.     //1.编写一个方法，接收head节点，同时接收一个index
  107.     //2.index 表示是倒数第k个节点
  108.     //3.先把链表从头到尾遍历，得到链表的总长度getlength
  109.     //4.得到size之后，我们从链表的第一个开始遍历（getlength - index）个，就可以得到
  110.     //5.如果找到了，就返回该节点，否则返回null
  111.      public static HeroNode findLastIndexNode(HeroNode head,int index){
  112.         //判断如果链表为空，则返回null
  113.          if(head.next == null){
  114.              return null;//没有找到
  115.          }
  116.          //第一个遍历得到链表的长度（节点个数）
  117.          int size = getLength(head);
  118.          //第二次遍历 size - index 位置，就是我们倒数第k个节点啊
  119.          //先做一个index的校验
  120.          if(index <=0 || index > size){
  121.              return null;
  122.          }
  123.          //定义个辅助变量
  124.          HeroNode cur = head.next;
  125.          for (int i = 0; i < size - index; i++) {
  126.              cur = cur.next;
  127.          }
  128.          return cur;
  129.      }
  130.  
  131.     /**
  132.      *方法：获取到单链表的节点的个数（如果是带头节点的链表，需求不统计头节点）
  133.      * @param head 链表的头节点
  134.      * @return 返回的就是有效节点的个数
  135.      */
  136.     public static int getLength(HeroNode head){
  137.         if(head.next == null){
  138.             //空链表
  139.             return 0;
  140.         }int length = 0;
  141.         //定义一个辅助变量
  142.         HeroNode cur = head.next;
  143.         while(cur != null){
  144.             length++;
  145.             cur = cur.next;//遍历
  146.         }
  147.         return length;
  148.     }
  149. }
  150.  
  151. //定义SingleLinkedList 管理我们的英雄
  152. class SingleLinkList {
  153.     //先初始化一个头节点，头节点不动，不要放具体的数据（头节点要是改变了，那么整个单链表也会发生改变！）
  154.     private HeroNode head = new HeroNode(0, "", "");
  155.  
  156.        //返回头节点
  157.        public HeroNode getHead() {
  158.             return head;
  159.        }
  160.  
  161.  
  162.     /**添加节点到单链表中*/
  163.     //思路：不考虑编号顺序时
  164.     //1.找到当前链表的最后节点
  165.     //2.将最后这个节点的next指向新的节点
  166.     public void add(HeroNode heroNode) {
  167.         //因为head节点不能动，因此我们需要一个辅助遍历 temp
  168.         HeroNode temp = head;
  169.         //遍历单链表，找到最后
  170.         while (true) {
  171.             //找到链表的最后
  172.             if (temp.next == null) {
  173.                 break;
  174.             }
  175.             //如果没有找到最后，将会把temp后移
  176.             temp = temp.next;
  177.         }
  178.         //当退出while循环时，temp指向了链表的最后
  179.         //将最后的这个节点的next 指向新的节点
  180.         temp.next = heroNode;
  181.     }
  182.  
  183.     /**第二种方式在添加英雄时，根据排名将英雄插入到指定位置*/
  184.     // （如果有这个排名，则代表添加失败，并给出提示）
  185.     public void addByOrder(HeroNode heroNode){
  186.         //因为头节点不能动，所以我们仍然需要通过一个辅助指针（变量）来帮助找到添加的位置
  187.         //因为单链表，因为我们找的temp是位于添加辅助位置的前一个节点，否则插入不了
  188.         HeroNode temp = head;
  189.         boolean flag = false;
  190.         while(true){
  191.             if(temp.next == null){
  192.                 //说明temp已经到了链表的最后
  193.                 break;
  194.             }
  195.             if(temp.next.no > heroNode.no ){
  196.                 //位置找到了，就在temp的后面插入
  197.                 break;
  198.             }else if(temp.next.no == heroNode.no){
  199.                 //说明希望添加的heroNode的编号已将存在
  200.                 flag = true;//说明编号存在
  201.                 break;
  202.             }
  203.             temp = temp.next;//遍历，后移
  204.         }
  205.         //判断flag的值
  206.         if(flag){
  207.             //不能添加，说明编号存在
  208.             System.out.println("准备插入的英雄的编号" + heroNode.no + "已经存在了，不能加入了！");
  209.         }else{
  210.             //插入到链表中，temp的后面
  211.             heroNode.next  = temp.next;
  212.             temp.next = heroNode;
  213.         }
  214.     }
  215.  
  216.  
  217.     /**修改节点的信息，根据no编号来修改，及no编号不能改*/
  218.     //说明
  219.     //1.根据newHeroNode 的 no 来修改即可
  220.     public void update (HeroNode newHeroNode){
  221.         //判断是否为空
  222.         if(head.next == null){
  223.             System.out.println("链表为空");
  224.             return;
  225.         }
  226.         //找到需要修改的编号，根据no编号
  227.         //定义一个辅助变量
  228.         HeroNode temp = head.next;
  229.         boolean flag = false;//表示是否找到该节点
  230.         while (true) {
  231.             if(temp==null){
  232.                 break;//已经遍历完该链表
  233.             }
  234.             if(temp.no == newHeroNode.no){
  235.                 //找到
  236.                 flag = true;
  237.                 break;
  238.             }
  239.             temp = temp.next;
  240.         }
  241.         //根据flag判断是否找到要修改的节点
  242.         if(flag){
  243.             temp.name = newHeroNode.name;
  244.             temp.nickname = newHeroNode.nickname;
  245.         }else{
  246.             //没有找到
  247.             System.out.println("没有找到该编号" + newHeroNode.no + "不能修改！");
  248.         }
  249.     }
  250.  
  251.     /**删除节点*/
  252.     //思路
  253.     //1.head 不能动，因此我们需要一个temp 辅助变量来找到待删除节点的前一个节点
  254.     //2.说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
  255.     public void del(int no){
  256.            HeroNode temp = head;
  257.            boolean flag = false;//标志是否找到待删除的节点
  258.         while (true) {
  259.             if(temp.next == null){
  260.                 //已经到链表最后
  261.                 break;
  262.             }
  263.             if(temp.next.no == no){
  264.                 //找到的待删除节点的前一个节点temp
  265.                 flag = true;
  266.                 break;
  267.             }
  268.             temp = temp.next;//temp后移，遍历
  269.         }
  270.         //判断flag
  271.         if(flag){//找到
  272.             //可以删除
  273.             temp.next = temp.next.next;
  274.         }else{
  275.             System.out.println("要删除的" +no + "节点不存在！");
  276.         }
  277.     }
  278.  
  279.     /**显示链表[遍历]*/
  280.     public void list() {
  281.         //判断链表是否为空
  282.         if (head.next == null) {
  283.             System.out.println("链表为空");
  284.             return;
  285.         }
  286.         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
  287.         HeroNode temp = head.next;
  288.         while(true){
  289.             //判断是否到链表最后
  290.             if( temp == null){
  291.             break;
  292.             }
  293.             //输出节点的信息（说明已经到最后了）
  294.             System.out.println(temp);
  295.             //将temp后移，一定小心
  296.             temp = temp.next;
  297.         }
  298.     }
  299. }
  300.  
  301.  
  302. //定义HeroNode，每个HeroNode 对象就是一个节点
  303. class HeroNode{
  304.  
  305.     public int no;
  306.     public String name;
  307.     public String nickname;//昵称
  308.     public HeroNode next;//指向下一个节点
  309.  
  310.     //构造有参构造器
  311.     public HeroNode(int no, String name, String nickname) {
  312.         this.no = no;
  313.         this.name = name;
  314.         this.nickname = nickname;
  315.     }
  316.  
  317.     //为了显示方法，重写toString
  318.     @Override
  319.     public String toString() {
  320.         return "HeroNode{" +
  321.                 "no=" + no +
  322.                 ", name='" + name + '\'' +
  323.                 ", nickname='" + nickname +
  324.                 '}';
  325.     }
  326. }

三、双链表

 

 1.删除节点

说明

1.对于双向链表，我们可以直接找到要删除的这个节点

2.找到后，自我删除即可

  1. public void del(int no){
  2.         HeroNode2 temp = head.next;//辅助变量（指针）
  3.         boolean flag = false;//标志是否找到待删除的节点
  4.         while (true) {
  5.             if(temp == null){
  6.                 //已经到链表最后
  7.                 break;
  8.             }
  9.             if(temp.next.no == no){
  10.                 //找到的待删除节点的前一个节点temp
  11.                 flag = true;
  12.                 break;
  13.             }
  14.             temp = temp.next;//temp后移，遍历
  15.         }
  16.         //判断flag
  17.         if(flag){//找到
  18.             //可以删除
  19.             //temp.next = temp.next.next;[单向链表]
  20.             temp.pre.next = temp.next.next;
  21.             //如果是最后一个节点，就不需要执行下面这句话否则会出现空指针
  22.             if(temp.next != null){
  23.               temp.next.pre = temp.pre;
  24.             }
  25.         }else{
  26.             System.out.println("要删除的" +no + "节点不存在！");
  27.         }
  28.     }

2.修改一个节点

修改节点的信息，根据no编号来修改，及no编号不能改

说明 1.根据newHeroNode 的 no 来修改即可

  1. public void update (HeroNode2 newHeroNode){
  2.         //判断是否为空
  3.         if(head.next == null){
  4.             System.out.println("链表为空");
  5.             return;
  6.         }
  7.         //找到需要修改的编号，根据no编号
  8.         //定义一个辅助变量
  9.         HeroNode2 temp = head.next;
  10.         boolean flag = false;//表示是否找到该节点
  11.         while (true) {
  12.             if(temp==null){
  13.                 break;//已经遍历完该链表
  14.             }
  15.             if(temp.no == newHeroNode.no){
  16.                 //找到
  17.                 flag = true;
  18.                 break;
  19.             }
  20.             temp = temp.next;
  21.         }
  22.         //根据flag判断是否找到要修改的节点
  23.         if(flag){
  24.             temp.name = newHeroNode.name;
  25.             temp.nickname = newHeroNode.nickname;
  26.         }else{
  27.             //没有找到
  28.             System.out.println("没有找到该编号" + newHeroNode.no + "不能修改！");
  29.         }
  30.     }

3.添加节点到单双链表中

思路：不考虑编号顺序时

  1.找到当前链表的最后节点

  2.将最后这个节点的next指向新的节点

  添加一个节点到链表最后

  1.     public void add(HeroNode2 heroNode) {
  2.         //因为head节点不能动，因此我们需要一个辅助遍历 temp
  3.         HeroNode2 temp = head;
  4.         //遍历单链表，找到最后
  5.         while (true) {
  6.             //找到链表的最后
  7.             if (temp.next == null) {
  8.                 break;
  9.             }
  10.             //如果没有找到最后，将会把temp后移
  11.             temp = temp.next;
  12.         }
  13.         //当退出while循环时，temp指向了链表的最后
  14.         //形成一个双向链表
  15.         temp.next = heroNode;
  16.         heroNode.pre = temp;
  17.     }

4.遍历双链表

  1.  public void list() {
  2.         //判断链表是否为空
  3.         if (head.next == null) {
  4.             System.out.println("链表为空");
  5.             return;
  6.         }
  7.         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
  8.         HeroNode2 temp = head.next;
  9.         while(true){
  10.             //判断是否到链表最后
  11.             if( temp == null){
  12.                 break;
  13.             }
  14.             //输出节点的信息
  15.             System.out.println(temp);
  16.             //将temp后移，一定小心
  17.             temp = temp.next;
  18.         }
  19.     }

5.创建双链表

  1.  HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
  2.         HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
  3.         HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
  4.         HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
  5.  
  6.         //创建一个双向链表
  7.         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  8.         doubleLinkedList.add(hero1);
  9.         doubleLinkedList.add(hero2);
  10.         doubleLinkedList.add(hero3);
  11.         doubleLinkedList.add(hero4);
  12.  
  13.         doubleLinkedList.list();

6.双链表总体演示

  1. package LinkedList;
  2.  
  3. public class DoubleLinkedListDemo {
  4.     public static void main(String[] args) {
  5.         //测试
  6.         System.out.println("双向链表的测试");
  7.         //先创建节点
  8.         HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
  9.         HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
  10.         HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
  11.         HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
  12.  
  13.         //创建一个双向链表
  14.         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  15.         doubleLinkedList.add(hero1);
  16.         doubleLinkedList.add(hero2);
  17.         doubleLinkedList.add(hero3);
  18.         doubleLinkedList.add(hero4);
  19.  
  20.         doubleLinkedList.list();
  21.  
  22.         System.out.println("---------------测试修改后的链表-------------");
  23.         HeroNode2 newHeroNode = new HeroNode2(4,"公孙胜","入云龙");
  24.         doubleLinkedList.update(newHeroNode);
  25.         doubleLinkedList.list();
  26.  
  27.         System.out.println("--------------删除节点-----------");
  28.         doubleLinkedList.del(3);
  29.         doubleLinkedList.list();
  30.     }
  31. }
  32.  
  33. //创建一个双向链表的类
  34. class DoubleLinkedList{
  35.     //先初始化一个头节点，头节点不动，不要放具体的数据（头节点要是改变了，那么整个单链表也会发生改变！）
  36.     private HeroNode2 head = new HeroNode2(0, "", "");
  37.  
  38.     //返回头节点
  39.     public HeroNode2 getHead() {
  40.         return head;
  41.     }
  42.  
  43.     //显示链表[遍历]
  44.     public void list() {
  45.         //判断链表是否为空
  46.         if (head.next == null) {
  47.             System.out.println("链表为空");
  48.             return;
  49.         }
  50.         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
  51.         HeroNode2 temp = head.next;
  52.         while(true){
  53.             //判断是否到链表最后
  54.             if( temp == null){
  55.                 break;
  56.             }
  57.             //输出节点的信息
  58.             System.out.println(temp);
  59.             //将temp后移，一定小心
  60.             temp = temp.next;
  61.         }
  62.     }
  63.     //添加节点到单双链表中
  64.     //思路：不考虑编号顺序时
  65.     //1.找到当前链表的最后节点
  66.     //2.将最后这个节点的next指向新的节点
  67.     //添加一个节点到链表最后
  68.     public void add(HeroNode2 heroNode) {
  69.         //因为head节点不能动，因此我们需要一个辅助遍历 temp
  70.         HeroNode2 temp = head;
  71.         //遍历单链表，找到最后
  72.         while (true) {
  73.             //找到链表的最后
  74.             if (temp.next == null) {
  75.                 break;
  76.             }
  77.             //如果没有找到最后，将会把temp后移
  78.             temp = temp.next;
  79.         }
  80.         //当退出while循环时，temp指向了链表的最后
  81.         //形成一个双向链表
  82.         temp.next = heroNode;
  83.         heroNode.pre = temp;
  84.     }
  85.  
  86.     //修改一个节点的内容
  87.     //修改节点的信息，根据no编号来修改，及no编号不能改
  88.     //说明
  89.     //1.根据newHeroNode 的 no 来修改即可
  90.     public void update (HeroNode2 newHeroNode){
  91.         //判断是否为空
  92.         if(head.next == null){
  93.             System.out.println("链表为空");
  94.             return;
  95.         }
  96.         //找到需要修改的编号，根据no编号
  97.         //定义一个辅助变量
  98.         HeroNode2 temp = head.next;
  99.         boolean flag = false;//表示是否找到该节点
  100.         while (true) {
  101.             if(temp==null){
  102.                 break;//已经遍历完该链表
  103.             }
  104.             if(temp.no == newHeroNode.no){
  105.                 //找到
  106.                 flag = true;
  107.                 break;
  108.             }
  109.             temp = temp.next;
  110.         }
  111.         //根据flag判断是否找到要修改的节点
  112.         if(flag){
  113.             temp.name = newHeroNode.name;
  114.             temp.nickname = newHeroNode.nickname;
  115.         }else{
  116.             //没有找到
  117.             System.out.println("没有找到该编号" + newHeroNode.no + "不能修改！");
  118.         }
  119.     }
  120.     //从双向链表中删除一个节点
  121.     //说明
  122.     //1.对于双向链表，我们可以直接找到要删除的这个节点
  123.     //2.找到后，自我删除即可
  124.     public void del(int no){
  125.         HeroNode2 temp = head.next;//辅助变量（指针）
  126.         boolean flag = false;//标志是否找到待删除的节点
  127.         while (true) {
  128.             if(temp == null){
  129.                 //已经到链表最后
  130.                 break;
  131.             }
  132.             if(temp.next.no == no){
  133.                 //找到的待删除节点的前一个节点temp
  134.                 flag = true;
  135.                 break;
  136.             }
  137.             temp = temp.next;//temp后移，遍历
  138.         }
  139.         //判断flag
  140.         if(flag){//找到
  141.             //可以删除
  142.             //temp.next = temp.next.next;[单向链表]
  143.             temp.pre.next = temp.next.next;
  144.             //如果是最后一个节点，就不需要执行下面这句话否则会出现空指针
  145.             if(temp.next != null){
  146.               temp.next.pre = temp.pre;
  147.             }
  148.         }else{
  149.             System.out.println("要删除的" +no + "节点不存在！");
  150.         }
  151.     }
  152. }
  153.  
  154.  
  155. //定义HeroNode，每个HeroNode 对象就是一个节点
  156. class HeroNode2{
  157.     public HeroNode2 pre;
  158.     public int no;
  159.     public String name;
  160.     public String nickname;//昵称
  161.     public HeroNode2 next;//指向下一个节点，默认为null
  162.  
  163.     //构造有参构造器
  164.     public HeroNode2(int no, String name, String nickname) {
  165.         this.no = no;
  166.         this.name = name;
  167.         this.nickname = nickname;
  168.     }
  169.  
  170.     //为了显示方法，重写toString
  171.     @Override
  172.     public String toString() {
  173.         return "HeroNode2{" +
  174.                 "no=" + no +
  175.                 ", name='" + name + '\'' +
  176.                 ", nickname='" + nickname +
  177.                 '}';
  178.     }
  179. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/630202
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号