java中链表的数据结构的理解

在 Java 中，链表是一种常见的数据结构，可以通过类的方式实现自定义链表。以下是关于 Java 中链表的数据结构和实现方式的详细介绍。

---

1. 自定义链表结构

Java 中链表通常由一个节点类 (ListNode) 和可能的链表操作类构成。

节点类 (ListNode)

这是链表的基本组成部分，每个节点包含数据域和指向下一个节点的引用。

class ListNode {int val; // 数据域ListNode next; // 指向下一个节点的引用// 构造函数ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

---

2. 单链表 (Singly Linked List)

单链表中，每个节点只指向下一个节点。

基本操作实现

class SinglyLinkedList {private ListNode head; // 头节点// 添加节点到链表末尾public void add(int val) {ListNode newNode = new ListNode(val);if (head == null) {head = newNode;} else {ListNode current = head;while (current.next != null) {current = current.next;}current.next = newNode;}}// 删除指定值的节点public void delete(int val) {if (head == null) return;if (head.val == val) {head = head.next;return;}ListNode current = head;while (current.next != null && current.next.val != val) {current = current.next;}if (current.next != null) {current.next = current.next.next;}}// 打印链表public void printList() {ListNode current = head;while (current != null) {System.out.print(current.val + " -> ");current = current.next;}System.out.println("null");}
}

---

3. 双链表 (Doubly Linked List)

双链表的每个节点有两个引用，一个指向前一个节点，另一个指向后一个节点。

节点类

class DoublyListNode {int val;DoublyListNode prev; // 指向前一个节点DoublyListNode next; // 指向下一个节点DoublyListNode(int val) { this.val = val; }
}

双链表操作

class DoublyLinkedList {private DoublyListNode head; // 头节点private DoublyListNode tail; // 尾节点// 添加到链表末尾public void add(int val) {DoublyListNode newNode = new DoublyListNode(val);if (head == null) {head = tail = newNode;} else {tail.next = newNode;newNode.prev = tail;tail = newNode;}}// 删除指定值的节点public void delete(int val) {DoublyListNode current = head;while (current != null && current.val != val) {current = current.next;}if (current == null) return; // 未找到if (current.prev != null) {current.prev.next = current.next;} else {head = current.next; // 删除头节点}if (current.next != null) {current.next.prev = current.prev;} else {tail = current.prev; // 删除尾节点}}// 打印链表public void printList() {DoublyListNode current = head;while (current != null) {System.out.print(current.val + " <-> ");current = current.next;}System.out.println("null");}
}

---

4. 使用 Java 标准库的链表

Java 提供了标准库中的 LinkedList 类，可以直接使用，不需要手动实现。

使用 LinkedList

import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();// 添加元素list.add(1);list.add(2);list.add(3);// 删除元素list.remove(Integer.valueOf(2));// 打印链表System.out.println(list); // 输出: [1, 3]}
}

特点

• LinkedList 是双向链表，提供头尾操作支持。
• 它实现了 List 接口和 Deque 接口，可用作队列和栈。

---

总结

1. 自定义链表：适用于需要实现特定链表功能的场景。
   • 单链表：每个节点只有 next 引用。
   • 双链表：每个节点有 next 和 prev 引用，操作更加灵活。
2. Java 标准库 LinkedList：提供开箱即用的链表操作，适合一般用途。