数据结构与算法 —— Java 实现（链表）

Gorit

发布于 2021-12-08 21:51:59

2.1K0

发布于 2021-12-08 21:51:59

文章被收录于专栏：Gorit 带你学全栈系列Gorit 带你学全栈系列

数据结构与算法 —— Java 实现（链表）

一、单链表

不知大家是否还记得自己刚接触数据结构的时候，是怎么过来的吗，那时候学习数据结构是使用 c语言实现，那时候会充满各种疑问？这个 * 啥意思，那个 & 又是啥意思，为啥结构体里面，有个和结构体名一样的东西，是不是像极了当初学数据结构的你呢？

1.1 链表的定义

链表实际上是一个二元组，它的每一个节点都分别存有数据和 下一个节点的地址，这样我们就可以抽象出链表中具有的基本属性

定义节点为 Node
每个节点中都有数据 data
和指向下一个地址引用（指针，java 中没有指针的概念）

// 定义一个单链表
public class Node {
	private int data; // 这里我默认存储的数据都是整数
	private Node next; // 存放下一个地址的引用
	
	// 编写构造方法
	public Node(int data) {
		this.data = data;
	}

    // 获取下一个节点的方法
    public Node next() {
        return this.next;
    }

    // 获取节点中的数据
    public int getData() {
        return this.data;
    }

}

1.2 链表添加一个新的节点

实现思路： 如果我要在链表中插入一个节点，但是我只知道头结点，所以我需要一个节点一个节点的查找，直至找那个下一个节点为空的节点停止，然后将该节点的地址指向一个我们要插入的节点，即可完成插入操作。不懂？没关系，看下面的动图展示

下面就来实现一下：

这一步的核心就是找到最后一个节点

    // 为节点追加节点 （解决不断增加的问题）
    public Node append(Node node) {
        // 获得当前节点
        Node currentNode = this;
        // 循环向后找，找到下一个节点为空的最后一个节点
        while (true) {
            // 取出下一个节点
            Node nextNode = currentNode.next;
            // 如果下一个节点为 Null, 当前节点已经是最后一个节点
            if (nextNode == null) {
                break;
            }
            // 赋值给当前节点
            currentNode = nextNode;

        }
        // 把需要追加的节点追加到当前找到的当前节点
        currentNode.next = node;
        return this;
    }

1.3 判断当前节点是否为最后一个节点（isLast）

只要判断当前节点的引用是否为空即可

    // 当前节点是否为最后一个节点
    public boolean islast() {
        return this.next == null;
    }

1.4 删除下一节点（removeNext）

我们要删除一个节点

需要将他的指向的节点变成指向为空
将指向该节点的指针指向下下一个节点我们看动画

	// 这个就很简单啦，只需要把引用改一下，就完成了
    // 删除下一个节点
    public void removeNext() {
        // 取出下下一个节点
        Node newNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = newNext;
    }

1.5 显示节点信息（show）

使用循环打印出链表中的每个节点对应的值

    // 显示所有节点的信息
    public void show() {
        Node currentNode = this;
        while (true) {
            System.out.print(currentNode.data+" ");
            // 取出下一个节点
            currentNode = currentNode.next;
            // 如果是最后一个节点
            if (currentNode == null) {
                System.out.println();// 换行处理
                break;
            }
        }
    }

1.6 插入一个节点（after）

往当前节点的位置插入一个节点，使其变成当前节点的下一个节点

    // 插入一个节点，作为当前节点的下一个节点，这就可以类比为 交换两个数字的值
    public void after(Node node) {
        // 取出下一个节点，作为下下一个节点
        Node nextNext = next;
        // 把新节点插入为当前节点的下一个节点
        this.next = node;
        // 把下下一个节点作为新节点的下一个节点
        node.next = nextNext;
    }

1.7 编写测试类（TestNode）

import Array.util.Node;

public class TestNode {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        // 追加节点
        n1.append(n2).append(n3).append(new Node(4));

        // 显示所有节点内容
        n1.show();

        // 去除下一个节点
//        n1.next().removeNext(); // 删除3
//        n1.show();

        // 插入一个新节点
        Node node = new Node(5);
        n1.next().after(node);
        n1.show();

        System.out.println(n1.next().getData());
        System.out.println(n2.next().getData());
        System.out.println(n3.getData());
        System.out.println(n3.islast());
    }
}

二、循环单链表

循环链表，就是把链表的尾部和头部相连

2.1 循环单链表定义

public class LoopNode {
    // 节点内容
    private int data;
    // 下一个节点
    private LoopNode next = this;
    public LoopNode(int data) {
        this.data = data;
    }
}

2.2 获取下一个节点及数据

 // 获取下一个节点的方法
    public LoopNode next() {
        return this.next;
    }

    // 获取节点中的数据
    public int getData() {
        return this.data;
    }

2.3 插入节点

    // 插入一个节点，作为当前节点的下一个节点
    public void after(LoopNode node) {
        // 取出下一个节点，作为下下一个节点
        LoopNode nextNext = next;
        // 把新节点插入为当前节点的下一个节点
        this.next = node;
        // 把下下一个节点作为新节点的下一个节点
        node.next = nextNext;
    }

2.4 删除节点

    // 删除下一个节点
    public void removeNext() {
        // 取出下下一个节点
        LoopNode newNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = newNext;
    }

2.5 循环遍历每一个节点

    // 显示所有节点的信息
    public void show() {
        LoopNode currentNode = this;
        while (true) {
            System.out.print(currentNode.data+" ");
            // 取出下一个节点
            currentNode = currentNode.next;
            // 如果是最后一个节点
            if (currentNode == null) {
                System.out.println();
                break;
            }
        }
    }

三、循环双链表

循环双链表，是指头和尾部相连，同时又具有前节点和后节点的引用

3.1 双向循环链表的定义

// 双向链表实现
public class DoubleLoop {
    // 上一个节点
    private DoubleLoop pre;
    // 下一个节点
    private DoubleLoop next = this;
    // 节点的数据
    private int data;

    public DoubleLoop(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }
}

3.2 获取上（下）一个节点

    // 下一个节点
    public DoubleLoop next() {
        return this.next;
    }

    // 上一个节点
    public DoubleLoop pre() {
        return this.pre;
    }

3.3 增加节点

    // 增加节点
    public void after(DoubleLoop node) {
        // 原来的下一个节点
        DoubleLoop nextNext = next;
        // 新节点作为当前节点的下一个节点
        this.next = node;
        // 当前节点作为新节点的前一个节点
        node.pre = this;
        // 原来的下一个节点作为新节点的下一个节点
        node.next = nextNext;
        // 让原来的下一个节点的上一个节点为当前新节点
        nextNext.pre = node;
    }

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-04-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

数据结构

网站

本文分享自作者个人站点/博客?前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

编程算法

数据结构

网站

登录后参与评论

0 条评论

热度