当前位置:   article > 正文

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

java 单链表 讲解 增删查改

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


定义节点:

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

一、增加节点

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. }

直接在链表尾部添加节点:只需要遍历到链表的最后,将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. }


二、删除一个节点

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

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

代码实现

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


三、修改某一个节点

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

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


四、查询某一个节点

和修改节点相似

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

五、遍历单链表

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

  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. }


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

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

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

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

测试结果


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

头插法

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

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

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

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

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

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

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

闽ICP备14008679号