【数据结构与算法】单向链表

一、什么是链表

        链表由一系列节点组成，每个节点都包含一个 data 域（存放数据）和一个 next 域（指向下一节点）。链表中的节点可以按照任意顺序存放在内存中，它们之间并不连续。每个节点都记录了下一个节点的地址，这样可以通过遍历节点的方式遍历整个链表。链表有多种类型，如单向链表、双向链表和循环链表等。

        这里主要了解单向列表的实现与使用。

---

二、在 Java 中实现链表

        首先，我们需要定义一个节点类，假设其用于保存个人信息（id、name），其中 next 用于指向下一个节点（Node）。其还有构造方法同时重写了 toString 方法（不输出 next 的信息）。

class Node {
    public int id;
    public String name;
    public Node next;
    //构造器
    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name +
                '}';
    }
}

        接着，我们初始化一个头结点，其不存储任何数据，仅用于表示单链表的头部。

private Node head = new Node(0, "");

        想要向链表中添加节点，可以在 SingleLinkedList 类中定义一个 add 方法，其内通过辅助节点(next)遍历链表到尾部，再将要添加的节点添加到尾部。

public void add(Node node) {
     // 因为 head 节点不能动，所以需要一个辅助节点 temp
    Node temp = head;
    while (true){
        if (temp.next == null){
            break;
        }
        temp = temp.next;
    }
    temp.next = node;
}

        想要查看链表的所有数据，可以定义一个 list 方法，创建一个辅助节点遍历链表并在 next 为空时输出错误信息后停止遍历，不为空时输出节点的内容。

public void list(){
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }
    Node temp = head.next;
    while(true){
        if (temp == null){
            break;
        }
        System.out.println(temp);
        temp = temp.next;
    }
}

最终效果如下所示

---

        而要是想要实现添加时的 id 顺序随机 ，但会在链表中排序后添加到对应位置的功能，我们可以创建一个排序添加的方法 addByOrder，通过比较加入的节点与链表中原有节点中的 id 的大小来添加到链表的相应位置。

public void addByOrder(Node node){
    Node temp = head;
    boolean flag = false;
    while(true){
        if (temp.next == null){
            break;
        }
        if (temp.next.id > node.id){
            break;
        } else if (temp.next.id == node.id){
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag){
        System.out.println("准备插入的人的编号已经存在:" + node.id);
    } else {
        node.next = temp.next;
        temp.next = node;
    }
}

        方法中先声明了一个辅助节点 temp 和一个用于记录 id 是否已存在的 flag。其先遍历链表，如果 temp 的下一个节点为 null 则表示到达链表的尾部，直接退出循环；之后判断是否存在 id 在新加入的节点的 id 之后的，如果有则退出循环，此时 temp 代表需要插入位置之前的节点处，而 temp.next 则代表需要插入位置之后的节点处。（如下图所示）

        而循环外可以将 ① node 的 next 设为 temp 的next ② temp 的 next 设为 node。（如下图所示）

        最后如果遍历到 id 相同的节点，则将 flag 设为 true 后退出循环，并在循环外输出错误信息。

最终效果如下所示

---

        其余的基础操作也是类似的想法去实现，如删除操作，也是传入 id 后遍历链表找到相同的 id 后将其从链表中断开（temp.next = temp.next.next）。更新和删除操作对应代码如下：

public void update(Node newNode){
    if (head.next == null){
        System.out.println("链表为空");
        return;
    }
    Node temp = head.next;
    boolean flag = false;
    while(true){
        if (temp == null){
            break;
        }
        if (temp.id == newNode.id){
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag){
        temp.name = newNode.name;
    } else {
        System.out.println("没有找到编号 " + newNode.id + " 的节点");
    }
}

public void del(int id){
    Node temp = head;
    boolean flag = false;
    while (true){
        if (temp.next == null){
            break;
        }
        if (temp.next.id == id){
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag){
        temp.next = temp.next.next;
    } else {
        System.out.println("没有找到编号 " + id + " 的节点");
    }
}

---

（水）

【完】

原文地址：https://blog.csdn.net/t46464949/article/details/144791985

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！