java怎么创建单链表

Java中创建单链表，需要先定义节点类，再通过一系列操作构建链表,以下是详细的步骤和示例代码：

定义节点类（Node）

节点是单链表的基本组成单位，每个节点包含数据域和指向下一个节点的指针域,可以使用内部类或独立类来定义节点。

使用内部类定义节点

public class LinkedList {
    // 内部类Node，表示链表的节点
    static class Node {
        int data; // 数据域，存储节点的值
        Node next; // 指针域，指向下一个节点
        // 构造函数，初始化节点的数据和指针
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    // 链表的头节点，初始为null
    private Node head;
    // 构造函数，初始化空链表
    public LinkedList() {
        this.head = null;
    }
    // 其他链表操作方法（如添加、删除等）将在后续步骤中实现
}

使用独立类定义节点

// 独立的节点类
class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// 链表类，包含对链表的操作
public class LinkedList {
    private Node head;
    public LinkedList() {
        this.head = null;
    }
    // 其他链表操作方法（如添加、删除等）将在后续步骤中实现
}

创建单链表并添加节点

创建单链表的过程通常是从头节点开始，逐步添加节点到链表中,以下是几种常见的添加节点的方式：

在链表末尾添加节点

public void append(int data) {
    // 创建新节点
    Node newNode = new Node(data);
    // 如果链表为空，新节点成为头节点
    if (head == null) {
        head = newNode;
        return;
    }
    // 遍历到链表的最后一个节点
    Node last = head;
    while (last.next != null) {
        last = last.next;
    }
    // 将新节点添加到链表末尾
    last.next = newNode;
}

在链表头部添加节点

public void addFirst(int data) {
    // 创建新节点
    Node newNode = new Node(data);
    // 将新节点的next指向当前的头节点
    newNode.next = head;
    // 更新头节点为新节点
    head = newNode;
}

在指定位置添加节点

public void addAtIndex(int index, int data) {
    // 创建新节点
    Node newNode = new Node(data);
    // 如果索引为0，相当于在头部添加节点
    if (index == 0) {
        addFirst(data);
        return;
    }
    // 找到索引位置的前一个节点
    Node current = head;
    int i = 0;
    while (i < index 1 && current != null) {
        current = current.next;
        i++;
    }
    // 如果当前节点为null，说明索引超出范围，不执行操作
    if (current == null) {
        return;
    }
    // 将新节点插入到指定位置
    newNode.next = current.next;
    current.next = newNode;
}

遍历和打印单链表

为了查看单链表中的元素,可以遍历链表并打印每个节点的数据。

public void printList() {
    Node current = head; // 从头节点开始遍历
    while (current != null) {
        System.out.print(current.data + " -> "); // 打印当前节点的数据
        current = current.next; // 移动到下一个节点
    }
    System.out.println("null"); // 链表结束，打印null
}

完整示例代码

以下是一个完整的单链表实现示例，包含节点定义、添加节点、遍历打印等功能：

public class LinkedList {
    // 内部类Node，表示链表的节点
    static class Node {
        int data; // 数据域，存储节点的值
        Node next; // 指针域，指向下一个节点
        // 构造函数，初始化节点的数据和指针
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    // 链表的头节点，初始为null
    private Node head;
    // 构造函数，初始化空链表
    public LinkedList() {
        this.head = null;
    }
    // 在链表末尾添加节点
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }
    // 在链表头部添加节点
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
    // 在指定位置添加节点
    public void addAtIndex(int index, int data) {
        Node newNode = new Node(data);
        if (index == 0) {
            addFirst(data);
            return;
        }
        Node current = head;
        int i = 0;
        while (i < index 1 && current != null) {
            current = current.next;
            i++;
        }
        if (current == null) {
            return;
        }
        newNode.next = current.next;
        current.next = newNode;
    }
    // 遍历并打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
    // 测试代码
    public static void main(String[] args) {
        LinkedList list = new LinkedList(); // 创建空链表
        list.append(1); // 在末尾添加节点1
        list.append(2); // 在末尾添加节点2
        list.addFirst(0); // 在头部添加节点0
        list.addAtIndex(2, 1.5); // 在索引2的位置添加节点1.5
        list.printList(); // 打印链表，输出：0 -> 1 -> 1.5 -> 2 -> null
    }
}

单链表的特点和适用场景

单链表是一种动态数据结构,具有以下特点：

• 优点：
  • 插入和删除操作高效，时间复杂度为O(1)，只需改变指针的指向,无需移动大量元素。
  • 动态大小，可以根据需要动态扩展或收缩,不会像数组一样浪费空间。
• 缺点：
  • 无法随机访问元素，必须从头节点开始逐个遍历，访问时间复杂度为O(n)。
  • 每个节点需要额外的空间存储指针,增加了存储开销。

单链表适用于频繁进行插入和删除操作的场景，例如任务调度、动态内存分配等,以下是一个简单的对比表格：

FAQs

如何在单链表的中间插入一个节点？

要在单链表的中间插入一个节点，需要先找到插入位置的前一个节点，然后调整指针,具体步骤如下：

• 创建新节点。
• 遍历链表,找到插入位置的前一个节点。
• 将新节点的next指向前一个节点的next。
• 将前一个节点的next指向新节点。

如何删除单链表中的重复元素？

删除单链表中的重复元素需要遍历链表，并使用辅助数据结构（如HashSet）来记录已出现的元素,具体步骤如下：

• 创建一个HashSet来存储已出现的元素。
• 遍历链表,检查当前节点的值是否已在HashSet中。
• 如果已存在，则删除当前节点（需要调整前一个节点的next）。
• 如果不存在，则将当前节点的值添加到HashSet中，继续遍历