专做商铺中介网站,网站建设有什么服务,北京互联网公司50强,能够免费换友链的平台#x1f525;博客主页#xff1a; 小扳_-CSDN博客 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 单链表的说明 2.0 单链表的创建 2.1 单链表 - 头插节点 2.2 单链表 - 遍历 2.2.1 使用简单的 for/while 循环 2.2.2 实现 forEach 方法 2.2.3 实现迭代器的方法 2.… 博客主页 小扳_-CSDN博客 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 单链表的说明 2.0 单链表的创建 2.1 单链表 - 头插节点 2.2 单链表 - 遍历 2.2.1 使用简单的 for/while 循环 2.2.2 实现 forEach 方法 2.2.3 实现迭代器的方法 2.3 单链表 - 尾插节点 2.4 单链表 - 通过索引获取数据 2.5 单链表 - 通过索引插入数据 2.6 单链表 - 头删节点 2.7 单链表 - 根据节点来删除数据 3.0 实现单链表的完整代码 4.0 实现加 哨兵 的单链表 1.0 单链表的说明 单链表是一种数据结构。数据结构是指数据的组织、管理和存储的方式而单链表是一种常见的线性数据结构用于存储一系列具有相同类型的元素。它由一系列节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。单链表可以通过指针的方式实现元素的插入、删除和查找等操作。 2.0 单链表的创建 把单链表封装成一个类面向对象编程的思路。类中需要的成员变量为头节点、节点又可以把节点封装成一个类为更好把节点类封装起来将其设置为静态内部类。
代码如下 public class SingleLists{//头节点private Node hand null;//节点private static class Node {//数据private int data;//指向下一个节点private Node next;public Node() {}} 注意的是这些成员都不会对外访问的所以需要把成员变为私有成员。 2.1 单链表 - 头插节点 顾名思义就是在头节点处插入新的节点使其成为新的头节点。需要考虑两种情况第一种情况头节点为 null 时直接就可以将创建出来的对象被 hand 引用了。第二种情况头节点不为 null 时需要将创建的对象的 next 引用指向 hand 的引用而当前创建的对象就要被 hand 引用。
代码如下 //实现头插节点public void addFirst(int data) {
/* if (hand null){hand new Node(data,null);}else {hand new Node(data,hand);}*///对以上代码进行简化得以下代码hand new Node(data,hand);} 需要注意的时该 API 是对外访问。 2.2 单链表 - 遍历 实现遍历的方式有三种 第一种方式使用简单的 for/while 循环。 第二种方式实现 forEach 方法。 第三种方式实现迭代器的方法。 2.2.1 使用简单的 for/while 循环 一般 hand 是不会去移动或者去改变其引用则需要临时的变量 p 来指向 hand 的对象。循环的条件为 p ! null每一次循环结束都需要 p 去移动到下一个节点处p p.next 。
代码如下 //遍历方式打印方式public void myPrint(){if (hand null){throw new RuntimeException(hand is null);}//第一种
/* Node p hand;//用while来实现while (p ! null){System.out.println(p.data);p p.next;}*///第二种//用for来实现for (Node p hand;p !null;p p.next){System.out.println(p.data);}}还需要注意for 与 while 这两种的实现逻辑是一样的假如 hand 的引用为空则没必要去循环了直接去抛出错误。 2.2.2 实现 forEach 方法 对于 for/while 的遍历方法直接把 “方法写死了”forEeach 方法是对 for/while 的方法进行了升级。参数为 ConsumerInteger 内部类再重写 accept 方法。
代码如下 //遍历方式:实现forEach由于跟以下的代码有冲突先改名为 myForEach。public void myForEach(ConsumerInteger consumer){for (Node p hand; p ! null;p p.next){consumer.accept(p.data);}} 具体调用该方法的使用 singleLists.myForEach(new ConsumerInteger() {Overridepublic void accept(Integer integer) {System.out.println(integer);}}); 这样对外获取的数据可以自由支配使用不仅仅打印输出了。 2.2.3 实现迭代器的方法 需要实现接口 IterableInteger 该接口支持泛型目前先实现整数类型的单链表。重写 hasNext() 与 next() 方法。
代码如下 //遍历方式使用迭代器循环Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p hand;Overridepublic boolean hasNext() {return p ! null;}Overridepublic Integer next() {int k p.data;p p.next;return k;}};重写完的 hasNext() 这个方法的作用是判断当前 p 是否为 null 如果是就停止遍历结束了。反之继续遍历下去。 重写之后的 next() 方法的作用做了两个动作第一个动作就是获取当前的数据第二个动作就是将 p 移向下一个节点。 具体调用该方法的使用 for (Integer value:singleLists) {System.out.println(value);} 同理这个方式不仅仅只有打印输出了自由支配使用。 2.3 单链表 - 尾插节点 找最后的节点后面插入新的节点如果只有头节点需要不断的遍历直到最后一个节点。遍历的条件为 p.next ! null跟以上的条件需要区别开来这里需要得到最后的节点可不能 p !null 一直下去这样就会找不到最后的节点。
代码如下 //尾插节点public void addLast(int data) {if (hand null) {addFirst(data);return;}Node p hand;while (p.next ! null){p p.next;}p.next new Node(data,null);} 需要注意的是单独分开当 hand 为 null 时因为 hand.next null 了但是对于hand 为 null 时也可以插入节点呀所以 当 hand 为 null 时可以调用头插节点的方法。 2.4 单链表 - 通过索引获取数据 单链表是不连续的不用直接通过索引来访问节点去读取数据因此先独立设置一个方法需设置一个 i 记数点每一个遍历完 i ,直到 i index 时先返回该节点。再独立另一个方法通过该节点来读取该数据。
代码如下 //根据索引获取某个节点private Node findNode(int index) {int i 0;for (Node p hand ; p ! null ; p p.next,i){if (i index) {return p;}}return null;}//根据索引得到对应的数据public int get(int index) {Node p findNode(index);if (p null){throw new RuntimeException(找不到该索引!!!);}return p.data;} 对于找不到的节点需要抛出异常需要注意的是findNode 方法是不对外访问的需要封装起来。 2.5 单链表 - 通过索引插入数据 先获取插入位置的前一个 prev 节点然后 prev.next 去指向插入的节点的对象插入节点的 next 去引用原先 prev.next 的对象。
代码如下 //根据索引插入数据public void insert(int index , int data){if (index 0){addFirst(data);}Node prev findNode(index - 1);if (prev null){throw new RuntimeException(index is illegal);}prev.next new Node(data,prev.next);} 需要注意的是先判断插入点是否为头节点如果是头节点则调用头插的方法。再去判断其他情况通过 findNode() 方法是否得到 null如果是需要抛出异常。 2.6 单链表 - 头删节点 顾名思义直接删除头节点思路为 hand 这个引用需要指向 hand.next 这就是删除了第一个节点没用引用的对象在 Java 中回自动回收的不会占内存这也就是删除了。 代码如下 //头删节点public void removeFirst() {if (hand null){throw new RuntimeException(There are no nodes anymore);}hand hand.next;} 需要注意删除前先判断 hand 是否为 null 。 2.7 单链表 - 根据节点来删除数据 先找到要删除节点的前一个 prev 节点然后再去找到 要删除的节点 move prev.next 接着将 prev.next move.next 即可。
代码如下 //根据索引来删除节点public void remove(int index) {if (index 0) {removeFirst();return;}Node prev findNode(index - 1);if (prev null){throw new RuntimeException(There are no nodes anymore);}Node move prev.next;if (move null) {throw new RuntimeException(There are no nodes anymore);}prev.next move.next;} 在删除节点的时候需要先判断 index 是否为 0如果是则调用头删的方法再通过 findNode() 方法来找到删除节点的前一个节点如果得到的节点为 null则需要抛出异常同样的如果得到的需要删除的节点为 null 则需要抛出异常。 3.0 实现单链表的完整代码 import java.util.Iterator;
import java.util.function.Consumer;//整体
public class SingleLists implements IterableInteger{//头节点private Node hand null;//节点private static class Node {//数据private int data;//指向下一个节点private Node next;public Node() {}public Node(int data, Node next) {this.data data;this.next next;}}//实现头插节点public void addFirst(int data) {
/* if (hand null){hand new Node(data,null);}else {hand new Node(data,hand);}*///对以上代码进行简化得以下代码hand new Node(data,hand);}//遍历方式打印方式public void myPrint(){if (hand null){throw new RuntimeException(hand is null);}//第一种
/* Node p hand;//用while来实现while (p ! null){System.out.println(p.data);p p.next;}*///第二种//用for来实现for (Node p hand;p !null;p p.next){System.out.println(p.data);}}//遍历方式:实现forEach由于跟以下的代码有冲突先改名为 myForEach。public void myForEach(ConsumerInteger consumer){for (Node p hand; p ! null;p p.next){consumer.accept(p.data);}}//遍历方式使用迭代器循环Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p hand;Overridepublic boolean hasNext() {return p ! null;}Overridepublic Integer next() {int k p.data;p p.next;return k;}};}//尾插节点public void addLast(int data) {if (hand null) {addFirst(data);return;}Node p hand;while (p.next ! null){p p.next;}p.next new Node(data,null);}//根据索引获取某个节点private Node findNode(int index) {int i 0;for (Node p hand ; p ! null ; p p.next,i){if (i index) {return p;}}return null;}//根据索引得到对应的数据public int get(int index) {Node p findNode(index);if (p null){throw new RuntimeException(找不到该索引!!!);}return p.data;}//根据索引插入数据public void insert(int index , int data){if (index 0){addFirst(data);}Node prev findNode(index - 1);if (prev null){throw new RuntimeException(index is illegal);}prev.next new Node(data,prev.next);}//头删节点public void removeFirst() {if (hand null){throw new RuntimeException(There are no nodes anymore);}hand hand.next;}//根据索引来删除节点public void remove(int index) {if (index 0) {removeFirst();return;}Node prev findNode(index - 1);if (prev null){throw new RuntimeException(There are no nodes anymore);}Node move prev.next;if (move null) {throw new RuntimeException(There are no nodes anymore);}prev.next move.next;}} 4.0 实现加 哨兵 的单链表 哨兵是单链表中的一个特殊节点它不在乎存储什么数据元素只用于标记链表的开始或结束。在单链表中通常有一个头节点作为链表的起始位置。而哨兵节点是在头节点之前或尾节点之后的一个额外节点用于简化链表的操作。简单来说就是 hand 不在为 null ,始终有节点这么一来就会节省了考虑 hand null 的情况发生了写出来的代码更加简洁了。
加 哨兵 的代码如下 import java.util.Iterator;
import java.util.function.Consumer;//整体
public class SingleLists implements IterableInteger{//头节点private final Node hand new Node(0,null);//节点private static class Node {//数据private int data;//指向下一个节点private Node next;public Node() {}public Node(int data, Node next) {this.data data;this.next next;}}//实现头插节点public void addFirst(int data) {//对以上代码进行简化得以下代码//hand.next new Node(data,hand.next);insert(0,data);}//遍历方式打印方式public void myPrint(){for (Node p hand.next;p !null;p p.next){System.out.println(p.data);}}//遍历方式:实现forEach由于跟以下的代码有冲突先改名为 myForEach。public void myForEach(ConsumerInteger consumer){for (Node p hand.next; p ! null;p p.next){consumer.accept(p.data);}}//遍历方式使用迭代器循环Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p hand.next;Overridepublic boolean hasNext() {return p ! null;}Overridepublic Integer next() {int k p.data;p p.next;return k;}};}//尾插节点public void addLast(int data) {Node p hand;while (p.next ! null){p p.next;}p.next new Node(data,null);}//根据索引获取某个节点private Node findNode(int index) {int i -1;for (Node p hand ; p ! null ; p p.next,i){if (i index) {return p;}}return null;}//根据索引得到对应的数据public int get(int index) {Node p findNode(index);if (p null){throw new RuntimeException(找不到该索引!!!);}return p.data;}//根据索引插入数据public void insert(int index , int data){Node prev findNode(index - 1);if (prev null){throw new RuntimeException(index is illegal);}prev.next new Node(data,prev.next);}//头删节点public void removeFirst() {//hand hand.next;remove(0);}//根据索引来删除节点public void remove(int index) {Node prev findNode(index - 1);if (prev null){throw new RuntimeException(There are no nodes anymore);}Node move prev.next;if (move null) {throw new RuntimeException(There are no nodes anymore);}prev.next move.next;}
} 需要注意的是哨兵节点并不是必需的可以根据具体的需求来决定是否使用哨兵节点。在某些情况下如果链表的操作较为简单不涉及插入和删除等复杂操作可以不使用哨兵节点来简化代码。
