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 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中，继续遍历