博客主页: 小扳_-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 的方法进行了升级。参数为 Consumer
代码如下:
//遍历方式:实现forEach,由于跟以下的代码有冲突,先改名为 myForEach。
public void myForEach(Consumer
for (Node p = hand; p != null;p = p.next){
consumer.accept(p.data);
}
}
具体调用该方法的使用:
singleLists.myForEach(new Consumer
@Override
public void accept(Integer integer) {
System.out.println(integer);
}
});
这样对外获取的数据可以自由支配使用,不仅仅打印输出了。
2.2.3 实现迭代器的方法
需要实现接口 Iterable
代码如下:
//遍历方式:使用迭代器循环
@Override
public Iterator
return new Iterator
Node p = hand;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public 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 Iterable
//头节点
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(Consumer
for (Node p = hand; p != null;p = p.next){
consumer.accept(p.data);
}
}
//遍历方式:使用迭代器循环
@Override
public Iterator
return new Iterator
Node p = hand;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public 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 Iterable
//头节点
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(Consumer
for (Node p = hand.next; p != null;p = p.next){
consumer.accept(p.data);
}
}
//遍历方式:使用迭代器循环
@Override
public Iterator
return new Iterator
Node p = hand.next;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public 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;
}
}
需要注意的是,哨兵节点并不是必需的,可以根据具体的需求来决定是否使用哨兵节点。在某些情况下,如果链表的操作较为简单,不涉及插入和删除等复杂操作,可以不使用哨兵节点来简化代码。
好文推荐
发表评论