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

一、什么是链表

        链表由一系列节点组成，每个节点都包含一个 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;}@Overridepublic String toString() {return "Node{" +"id=" + id +", name='" + name +'}';}
}

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

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

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

public void add(Node node) {// 因为 head 节点不能动，所以需要一个辅助节点 tempNode 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 + " 的节点");}
}

---

（水）

【完】