什么是单向链表（SLL）？

简介

链表和数组在特性上较为相似，因为它们都用于存储同一类型的数据集合。数据类型可以是简单的原始类型（如整数），也可以是某个类的复杂对象。然而，链表的结构与数组有显著区别。

应用场景

链表的一些重要应用场景包括：

• 实现哈希表、文件系统和邻接表
• 动态内存分配：使用空闲块组成的链表
• 对长整数执行算术运算
• 维护姓名目录

链表的结构

链表由相互连接的节点组成，形如链条。每个节点包含数据以及指向链表中下一个节点的指针。单向链表（SLL）是最常见的链表类型，其中每个节点仅有一个指针，用于存储指向下一个节点的引用。下图展示了一个单向链表的结构。

要实现一个链表，我们需要以下两个类：

• 节点类（Node）
• 链表类（LinkedList）

节点类（Node）

Node 类用于存储单个节点中的数据。它可以保存原始数据类型（如整数、字符串），也可以保存具有多个属性的复杂对象。除了数据外，它还包含一个指向链表中下一个节点的指针，用于将各个节点像链条一样连接起来。以下是 Node 类的一个典型定义：

1// 定义泛型节点类 <T>
2public class Node<T> {
3  public T data; // 存储的数据（可以是整数、字符串、对象等）
4  public Node nextNode; // 指向链表中下一个节点的指针
5}

说明：上述代码定义了 Node 类的基本结构，包含两个成员变量：一个用于存储数据，另一个用于存储指向下一节点的引用。该类使用 Java 泛型实现，因此 data 变量可以存储任意指定类型的值。

链表类（LinkedList）

如前所述，单向链表由多个节点链接而成。为了访问这个链条，我们需要一个指针来记录链表的第一个元素。只要知道第一个节点的位置，就可以遍历整个链表，而无需记忆各个节点的具体存储位置。

单向链表包含一个 head 节点——即指向链表首个元素的指针。每次需要遍历链表时，都可以从这个头节点开始。以下是单向链表类的基本结构：

1public class SinglyLinkedList<T> {
2    // 单向链表的内部节点类
3    public class Node{
4        public T data; // 存储的数据（可以是整数、字符串、对象等）
5        public Node nextNode; // 指向下一个节点的指针
6    }
7
8    public Node headNode; // 链表的头节点
9    public int size;      // 链表的大小
10
11    // 构造函数
12    public SinglyLinkedList() {
13        headNode = null;
14        size = 0;
15    }
16}

说明：在上述类中，headNode 是一个 Node 类型的变量，指向链表的起始位置（即链表头部）。构造函数中将其初始化为 null，表示链表初始为空。当头节点为空（NULL）时，表示链表为空链表。如上图所示，头节点指向第一个元素，最后一个节点的指针指向 NULL，以标识链表的结束。