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

java实现单链表的增删改查_java 单链表 讲解 增删查改

作者：寸_铁 | 2024-07-14 04:07:25

赞

踩

java 单链表 讲解 增删查改

单链表：单链表中的每个节点不仅包含储存的数据，还包含指向下一个节点的链接。


定义节点：

  1. //定义节点
  2. class Node {
  3.     public Node next;//指向下一个新的节点
  4.     int val;
  5.  
  6.     public Node(int val) {//通过构造函数赋值
  7.         this.val = val;
  8.     }
  9. }

一、增加节点

1.1、新创建一个节点


1.2、将cur的next指向pre的next

1.3、将pre的next指向cur

  1.     //按照顺序插入元素
  2.     public void addOrder(Node node) {
  3.         Node temp = head;
  4.         //寻找插入的位置
  5.         while (true) {
  6.             //1、链表为空、直接在链表尾部插入
  7.             if (temp.next == null) {
  8.                 temp.next = node;
  9.                 return;
  10.             }
  11.             //2、需要找到插入点的前一个节点，
  12.             if (temp.next.val >= node.val) {
  13.                 node.next = temp.next;
  14.                 temp.next = node;
  15.                 return;
  16.             }
  17.             temp = temp.next;
  18.  
  19.         }
  20.  
  21.     }

直接在链表尾部添加节点：只需要遍历到链表的最后，将next指向新的节点就可。
代码实现

  1.     //在链表尾增加节点
  2.     public void add(Node node) {
  3.         //1、设置辅助节点
  4.         Node temp = head;
  5.         //2、找到链表的最后
  6.         while (true) {
  7.             if (temp.next != null) {
  8.                 temp = temp.next;
  9.             } else {
  10.                 break;
  11.             }
  12.         }
  13.         //3、找到最后，插入
  14.         temp.next = node;
  15.  
  16.     }


二、删除一个节点

2.1、找到待删除元素的上一个节点以及下一个节点

2.2、通过遍历找到待删除元素的前一个节点，通过将前一个节点的指向指向当前节点的下一个节点

代码实现

  1.  //删除某一个节点
  2.     public void deleteLinkList(int num) {
  3.         Node temp = head;
  4.         boolean flag = false;//标志位
  5.  
  6.         while (!flag) {
  7.             if (temp.next == null) {
  8.                 System.out.println("链表中不存在待删除元素0");
  9.                 return;
  10.             }
  11.             if (temp.next.val == num) {
  12.                 System.out.println("找到了待删除数据：" + temp.next.val);
  13.                 flag = true;
  14.                 break;
  15.             }
  16.             temp = temp.next;
  17.  
  18.         }
  19.         if (flag) {
  20.             temp.next = temp.next.next;
  21.         }
  22.         
  23.     }


三、修改某一个节点

通过遍历找到需要修改的节点，修改数据

  1.  //修改节点
  2.     public void updateLinkList(int data, int num) {
  3.         Node temp = head;//辅助数组
  4.  
  5.         while (true) {
  6.             if (temp.next == null) {
  7.                 System.out.println("链表为空");
  8.                 return;
  9.             }
  10.             if (temp.next.val == data) {
  11.                 //修改新元素
  12.                 temp.next.val = num;
  13.               return;
  14.             }
  15.             temp = temp.next;
  16.  
  17.         }
  18.  
  19.  
  20.     }
  21.


四、查询某一个节点

和修改节点相似

  1.    //取得某一个节点
  2.     public void getLinkList(int num) {
  3.         Node temp = head;
  4.  
  5.         while (true) {
  6.             if (temp.next == null) {
  7.                 System.out.println("链表中不存在该元素");
  8.                 return;
  9.             }
  10.             if (temp.next.val == num) {
  11.                 System.out.println("找到了该元素：" + temp.next.val);
  12.                 break;
  13.             }
  14.             temp = temp.next;
  15.  
  16.         }
  17.         
  18.     }

五、遍历单链表

通过辅助数组，遍历到每一个节点，打印链表存储的数值

  1.    //遍历节点
  2.     public void show() {
  3.         Node temp = head.next;
  4.         if (head.next == null) {
  5.             return;
  6.         }
  7.         System.out.print("单链表为：[ ");
  8.         while (true) {
  9.             if (temp == null) {
  10.                 break;
  11.             }
  12.             System.out.print(temp.val + "、");
  13.             temp = temp.next;
  14.         }
  15.         System.out.println(" ]");
  16.  
  17.     }
  18.  
  19. }


举例：头节点设定为链表的开始，所有的节点连接在后边

  1. package com.zheng.demo1;
  2.  
  3. public class MySingleLinkList {
  4.     public static void main(String[] args) {
  5.         //创建节点
  6.         Node node1 = new Node(1);
  7.         Node node2 = new Node(2);
  8.         Node node3 = new Node(3);
  9.         Node node4 = new Node(4);
  10.         Node node5 = new Node(8);
  11.  
  12.         //创建链表
  13.         SingleLinkList singleLinkList = new SingleLinkList();
  14.         singleLinkList.add(node1);
  15.         singleLinkList.add(node2);
  16.         singleLinkList.add(node3);
  17.         singleLinkList.add(node4);
  18.         singleLinkList.add(node5);
  19.         System.out.println("添加数据后的节点：");
  20.         singleLinkList.show();
  21.  
  22.         singleLinkList.getLinkList(3);//查找
  23.         singleLinkList.deleteLinkList(4);
  24.         System.out.println("删除数据4后的链表：");
  25.         singleLinkList.show();
  26.         //修改
  27.         System.out.println("将数据为2的节点的值修改为22");
  28.         singleLinkList.upDateLinkList(2, 22);
  29.         System.out.println("修改后的节点信息：");
  30.         singleLinkList.show();
  31.  
  32. //        //创建链表2
  33. //        System.out.println("==================");
  34. //        SingleLinkList singleLinkList1 = new SingleLinkList();
  35. //        singleLinkList1.addOrder(node4);
  36. //        singleLinkList1.addOrder(node3);
  37. //        singleLinkList1.addOrder(node1);
  38. //        singleLinkList1.addOrder(node2);
  39. //        singleLinkList1.addOrder(node5);
  40. //        singleLinkList1.show();
  41.  
  42.     }
  43.  
  44. }
  45.  
  46. class SingleLinkList {
  47.     //构造一个头节点
  48.     private Node head = new Node(0);
  49.  
  50.     //增加节点
  51.     public void add(Node node) {
  52.         //1、设置辅助节点
  53.         Node temp = head;
  54.         //2、找到链表的最后
  55.         while (true) {
  56.             if (temp.next != null) {
  57.                 temp = temp.next;
  58.             } else {
  59.                 break;
  60.             }
  61.         }
  62.         //3、找到最后，插入
  63.         temp.next = node;
  64.  
  65.     }
  66.  
  67.     //删除某一个节点
  68.     public void deleteLinkList(int num) {
  69.         Node temp = head;
  70.         boolean flag = false;//标志位
  71.  
  72.         while (!flag) {
  73.             if (temp.next == null) {
  74.                 System.out.println("链表中不存在待删除元素0");
  75.                 return;
  76.             }
  77.             if (temp.next.val == num) {
  78.                 System.out.println("找到了待删除数据：" + temp.next.val);
  79.                 flag = true;
  80.                 break;
  81.             }
  82.             temp = temp.next;
  83.  
  84.         }
  85.         if (flag) {
  86.             temp.next = temp.next.next;
  87.         }
  88.  
  89.     }
  90.  
  91.     //取得某一个节点
  92.     public void getLinkList(int num) {
  93.         Node temp = head;
  94.  
  95.         while (true) {
  96.             if (temp.next == null) {
  97.                 System.out.println("链表中不存在该元素");
  98.                 return;
  99.             }
  100.             if (temp.next.val == num) {
  101.                 System.out.println("找到了该元素：" + temp.next.val);
  102.                 break;
  103.             }
  104.             temp = temp.next;
  105.  
  106.         }
  107.  
  108.     }
  109.  
  110.     //修改节点
  111.     public void upDateLinkList(int data, int num) {
  112.         Node temp = head;//辅助数组
  113.  
  114.         while (true) {
  115.             if (temp.next == null) {
  116.                 System.out.println("链表为空");
  117.                 return;
  118.             }
  119.             if (temp.next.val == data) {
  120.                 //修改新元素
  121.                 temp.next.val = num;
  122.               return;
  123.             }
  124.             temp = temp.next;
  125.  
  126.         }
  127.  
  128.  
  129.     }
  130.  
  131.     //按照顺序插入元素
  132.     public void addOrder(Node node) {
  133.         Node temp = head;
  134.         //寻找插入的位置
  135.         while (true) {
  136.             //1、链表为空、直接在链表尾部插入
  137.             if (temp.next == null) {
  138.                 temp.next = node;
  139.                 return;
  140.             }
  141.             //2、需要找到插入点的前一个节点，
  142.             if (temp.next.val >= node.val) {
  143.                 node.next = temp.next;
  144.                 temp.next = node;
  145.                 return;
  146.             }
  147.             temp = temp.next;
  148.  
  149.         }
  150.  
  151.     }
  152.  
  153.     //遍历节点
  154.     public void show() {
  155.         Node temp = head.next;
  156.         if (head.next == null) {
  157.             return;
  158.         }
  159.         System.out.print("单链表为：[ ");
  160.         while (true) {
  161.             if (temp == null) {
  162.                 break;
  163.             }
  164.             System.out.print(temp.val + "、");
  165.             temp = temp.next;
  166.         }
  167.         System.out.println(" ]");
  168.  
  169.     }
  170.  
  171. }
  172.  
  173.  
  174. //定义节点
  175. class Node {
  176.     public Node next;//指向下一个新的节点
  177.     int val;
  178.  
  179.     public Node(int val) {//通过构造函数赋值
  180.         this.val = val;
  181.     }
  182.  
  183.  
  184. }
  185.

实例二、单链表存储学生的信息

  1. package com.zheng.demo2;
  2.  
  3. public class MyTest {
  4.     public static void main(String[] args) {
  5.  
  6.         //定义节点
  7.         Student student1 = new Student(1, "小明", "男");
  8.         Student student2 = new Student(2, "小红", "女");
  9.         Student student3 = new Student(3, "小黑", "男");
  10.         Student student4 = new Student(4, "小青", "女");
  11.  
  12.         //2、初始化链表
  13.         LinkList linkList = new LinkList();
  14.         linkList.addStudent(student1);
  15.         linkList.addStudent(student2);
  16.         linkList.addStudent(student3);
  17.         linkList.addStudent(student4);
  18.  
  19.         //遍历
  20.         linkList.queryLinkList();
  21.  
  22.     }
  23.  
  24. }
  25.  
  26. class LinkList {
  27.     //定义链表的开始位置
  28.     private Student head = new Student(0, "", "");
  29.  
  30.     //增加节点，从尾部
  31.     public void addStudent(Student student) {
  32.         Student temp = head;//辅助数组
  33.         boolean flag = false;
  34.  
  35.         while (true) {
  36.             if (temp.next == null) {
  37.                 flag = true;
  38.                 break;
  39.             } else {
  40.                 temp = temp.next;
  41.             }
  42.  
  43.         }
  44.         if (flag) {
  45.             temp.next = student;
  46.         }
  47.     }
  48.  
  49.     //遍历
  50.     public void queryLinkList() {
  51.         Student temp = head;
  52.         if (head.next == null) {
  53.             System.out.println("链表为空");
  54.             return;
  55.         }
  56.  
  57.         while (true) {
  58.             if (temp.next == null) {
  59.                 return;
  60.             }
  61.             System.out.println(temp.next);
  62.             temp = temp.next;
  63.         }
  64.     }
  65.  
  66.  
  67. }
  68.  
  69. //定义一个学生信息的节点类
  70. class Student {
  71.     int id;//学号
  72.     String name;//姓名
  73.     String sex;//性别
  74.     Student next;//下一个学生的节点
  75.  
  76.     public Student(int id, String name, String sex) {
  77.         this.id = id;
  78.         this.name = name;
  79.         this.sex = sex;
  80.     }
  81.  
  82.     @Override
  83.     public String toString() {
  84.         return "Student{" +
  85.                 "id=" + id +
  86.                 ", name='" + name + '\'' +
  87.                 ", sex='" + sex + '\'' +
  88.                 '}';
  89.     }
  90. }

测试结果

单链表插入节点共有三种方式，除了我们常见的头插法和尾插法，还多加入了指定顺序插入节点。 

头插法

就是在链表的头部一直插入节点。

  1.  //判断单链表是否为null
  2.     //单链表头插法
  3.     public void addHead(Node node) {
  4.         //如果链表为null，则把传入的第一个元素赋给head.next
  5.         if (head.next == null){
  6.             head.next = node;
  7.             return;
  8.         }
  9.         //如果链表不为null，就定义一个temp来辅助插入节点
  10.         Node temp = head.next;
  11.         //把传入的节点插入单链表，注意两个步骤
  12.         //1、head.next  指向    传入的节点
  13.         //2、传入的节点.next  指向  temp
  14.         head.next = node;
  15.         node.next = temp;
  16.     }

尾插法

就是从链表的尾部插入节点。

  1.  //尾插法
  2.     //不管什么插入法，都需要把要插入的节点传入方法中
  3.     public void addLast(Node node){
  4.         //定义辅助变量来插入数据
  5.         Node temp = head;
  6.         //退出循环
  7.         while (temp.next != null) {
  8.             //遍历到单链表的尾部
  9.             temp = temp.next;
  10.         }
  11.         //退出循环表示找到链表的最后一个节点，就在该节点插入传入的节点
  12.         temp.next = node;
  13.     }

头插法和尾插法的测试：

  1.  /**
  2.  * 单链表使用头插法和尾插法插入节点
  3.  */
  4. public class InsertLinked {
  5.     public static void main(String[] args) {
  6.  
  7.         Node node1 = new Node("head");
  8.         Node node2 = new Node("middle");
  9.         Node node3 = new Node("last");
  10.         Node node4 = new Node("lastOne");
  11.  
  12.         SingleNode singleNode = new SingleNode();
  13.         /*
  14.         singleNode.addLast(node1);
  15.         singleNode.addLast(node2);
  16.         singleNode.addLast(node3);
  17.         singleNode.addLast(node4);
  18.         singleNode.show();
  19.         */
  20.         singleNode.addHead(node1);
  21.         singleNode.addHead(node2);
  22.         singleNode.addHead(node3);
  23.         singleNode.addHead(node4);
  24.         singleNode.show();
  25.     }
  26. }
  27.  
  28. class SingleNode{
  29.  
  30.     //初始化头节点，不放任何数据
  31.     private  Node head = new Node("");
  32.  
  33.     //尾插法
  34.     //不管什么插入法，都需要把要插入的节点传入方法中
  35.     public void addLast(Node node){
  36.         //定义辅助变量来插入数据
  37.         Node temp = head;
  38.         //退出循环
  39.         while (temp.next != null) {
  40.             //遍历到单链表的尾部
  41.             temp = temp.next;
  42.         }
  43.         //退出循环表示找到链表的最后一个节点，就在该节点插入传入的节点
  44.         temp.next = node;
  45.     }
  46.  
  47.     //判断单链表是否为null
  48.     //单链表头插法
  49.     public void addHead(Node node) {
  50.         //如果链表为null，则把传入的第一个元素赋给head.next
  51.         if (head.next == null){
  52.             head.next = node;
  53.             return;
  54.         }
  55.         //如果链表不为null，就定义一个temp来辅助插入节点
  56.         Node temp = head.next;
  57.         //把传入的节点插入单链表，注意两个步骤
  58.         //1、head.next  指向    传入的节点
  59.         //2、传入的节点.next  指向  temp
  60.         head.next = node;
  61.         node.next = temp;
  62.     }
  63.  
  64.     //遍历链表，输出链表
  65.     public void show(){
  66.         //判断链表为null
  67.         if (head.next == null) {
  68.             System.out.println("链表为null");
  69.             return;
  70.         }
  71.         //注意这里的链表是不存放节点的，所以和add的方法的遍历有所不同
  72.         Node temp = head.next;
  73.         while (temp != null) {
  74.             System.out.println(temp);
  75.             temp = temp.next;
  76.         }
  77.     }
  78. }
  79.  
  80. class Node{
  81.     //存放数据
  82.     public String data;
  83.     
  84.     //指向当前节点的下一个节点，默认为null
  85.     public Node next;
  86.  
  87.     public Node(String name) {
  88.         this.data = name;
  89.     }
  90.  
  91.     @Override
  92.     public String toString() {
  93.         return "Node{" +
  94.                 "name='" + data + '\'' +
  95.                 '}';
  96.     }
  97. }

还有一种指定插入，但是需要在Node节点类再定义一个编号 属性，通过比较编号的大小来确定指定节点的插入顺序。即使插入的顺序不按照规律，但是最后遍历出来的节点还是会按照编号顺序来输出节点。

  1.  
  2.     //按照指定顺序插入节点
  3.     public void addByOrder(Node1 node){
  4.         //定义一个辅助变量temp
  5.         Node1 temp = head;
  6.         //定义一个标记，用来寻找 节点 要 插入的位置
  7.         boolean flag = false;
  8.         //遍历链表
  9.         while (true) {
  10.             //如果链表为null就退出循环
  11.             if (temp.next == null) {
  12.                 //符合条件 退出循环
  13.                 break;
  14.             }
  15.             //比如我插入的节点的编号为4 (node.no==4)，原来temp的后一个节点编号为5 (temp.next.no==5)
  16.             //所以temp后一个节点的就不再指向编号为5的节点，而是指向编号为4的节点（也就是我当前插入的节点）
  17.             //  5 > 4
  18.             if (temp.next.no > node.no){
  19.                 //符合条件 退出循环
  20.                 break;
  21.             }else if ( temp.next.no == node.no){
  22.                 flag = true;   //说明编号已存在 ，不需要插入
  23.                 //继续循环遍历，直到找到合适的位置
  24.             }
  25.             temp = temp.next;  //后移，相当于遍历当前链表
  26.         }
  27.         //判断flag的值
  28.         //可以写成flag == true
  29.         if (flag) {  //不能插入
  30.             System.out.println("该节点已存在");
  31.         }else {
  32.             //插入当前节点
  33.             node.next = temp.next;
  34.             temp.next = node;
  35.         }
  36.     }

这是指定顺序插入的测试代码

  1.  
  2. public class InsertLinked {
  3.     public static void main(String[] args) {
  4.  
  5.  
  6.         //创建节点类对象
  7.         Node1 node1 = new Node1("head", 1);
  8.         Node1 node2 = new Node1("middle", 2);
  9.         Node1 node3 = new Node1("last", 3);
  10.         Node1 node4 = new Node1("lastOne", 4);
  11.  
  12.         //创建单链表对象
  13.         SingleNode singleNode = new SingleNode();
  14.         /*  尾插法
  15.         singleNode.addLast(node1);
  16.         singleNode.addLast(node2);
  17.         singleNode.addLast(node3);
  18.         singleNode.addLast(node4);
  19.         singleNode.show();
  20.         */
  21.         /* 头插法
  22.         singleNode.addHead(node1);
  23.         singleNode.addHead(node2);
  24.         singleNode.addHead(node3);
  25.         singleNode.addHead(node4);*/
  26.  
  27.         //指定顺序插入节点
  28.         Node1 order1 = new Node1("head1", 1);
  29.         Node1 order2 = new Node1("middle2", 2);
  30.         Node1 order3 = new Node1("last3", 3);
  31.         Node1 order4 = new Node1("lastOne4", 4);
  32.  
  33.         singleNode.addByOrder(order4);
  34.         singleNode.addByOrder(order2);
  35.         singleNode.addByOrder(order3);
  36.         singleNode.addByOrder(order1);
  37.  
  38.         singleNode.show();
  39.     }
  40. }
  41.  
  42. class SingleNode{
  43.  
  44.     //初始化头节点，不放任何数据
  45.     private  Node1 head = new Node1("",0);
  46.  
  47.     //尾插法
  48.     //不管什么插入法，都需要把要插入的节点传入方法中
  49.     public void addLast(Node1 node){
  50.         //定义辅助变量来插入数据
  51.         Node1 temp = head;
  52.         //退出循环
  53.         while (temp.next != null) {
  54.             //遍历到单链表的尾部
  55.             temp = temp.next;
  56.         }
  57.         //退出循环表示找到链表的最后一个节点，就在该节点插入传入的节点
  58.         temp.next = node;
  59.     }
  60.  
  61.     //判断单链表是否为null
  62.     //单链表头插法
  63.     public void addHead(Node1 node) {
  64.         //如果链表为null，则把传入的第一个元素赋给head.next
  65.         if (head.next == null){
  66.             head.next = node;
  67.             return;
  68.         }
  69.         //如果链表不为null，就定义一个temp来辅助插入节点
  70.         Node1 temp = head.next;
  71.         //把传入的节点插入单链表，注意两个步骤
  72.         //1、head.next  指向    传入的节点
  73.         //2、传入的节点.next  指向  temp
  74.         head.next = node;
  75.         node.next = temp;
  76.     }
  77.  
  78.     //按照指定顺序插入节点
  79.     public void addByOrder(Node1 node){
  80.         //定义一个辅助变量temp
  81.         Node1 temp = head;
  82.         //定义一个标记，用来寻找 节点 要 插入的位置
  83.         boolean flag = false;
  84.         //遍历链表
  85.         while (true) {
  86.             //如果链表为null就退出循环
  87.             if (temp.next == null) {
  88.                 //符合条件 退出循环
  89.                 break;
  90.             }
  91.             //比如我插入的节点的编号为4 (node.no==4)，原来temp的后一个节点编号为5 (temp.next.no==5)
  92.             //所以temp后一个节点的就不再指向编号为5的节点，而是指向编号为4的节点（也就是我当前插入的节点）
  93.             //  5 > 4
  94.             if (temp.next.no > node.no){
  95.                 //符合条件 退出循环
  96.                 break;
  97.             }else if ( temp.next.no == node.no){
  98.                 flag = true;   //说明编号已存在 ，不需要插入
  99.                 //继续循环遍历，直到找到合适的位置
  100.             }
  101.             temp = temp.next;  //后移，相当于遍历当前链表
  102.         }
  103.         //判断flag的值
  104.         //可以写成flag == true
  105.         if (flag) {  //不能插入
  106.             System.out.println("该节点已存在");
  107.         }else {
  108.             //插入当前节点
  109.             node.next = temp.next;
  110.             temp.next = node;
  111.         }
  112.     }
  113.  
  114.     //遍历链表，输出链表
  115.     public void show(){
  116.         //判断链表为null
  117.         if (head.next == null) {
  118.             System.out.println("链表为null");
  119.             return;
  120.         }
  121.         //注意这里的链表是不存放节点的，所以和add的方法的遍历有所不同
  122.         Node1 temp = head.next;
  123.         while (temp != null) {
  124.             System.out.println(temp);
  125.             temp = temp.next;
  126.         }
  127.     }
  128. }
  129.  
  130. class Node1{
  131.     //存放数据
  132.     public String data;
  133.     public int no;
  134.  
  135.  
  136.     //指向当前节点的下一个节点，默认为null
  137.     public Node1 next;
  138.  
  139.     public Node1(String data,int no) {
  140.         this.data = data;
  141.         this.no = no;
  142.     }
  143.  
  144.     @Override
  145.     public String toString() {
  146.         return "Node{" +
  147.                 "name='" + data + '\'' +
  148.                 '}';
  149.     }
  150. }

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

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

  

闽ICP备14008679号