java数据结构

一.链表

链表（LinkedList）是Java集合框架（Java Collections Framework）中的一部分，它实现了List接口和Deque接口，允许元素为空。LinkedList是一个双向链表，每个节点都保存了其前一个和后一个元素的引用。这使得在链表的任何位置进行插入和删除操作都相对高效。

以下是LinkedList的一些常见用法和示例代码：

LinkedList

1. 创建链表

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个空的链表
        LinkedList<String> list = new LinkedList<>();
        
        // 向链表中添加元素
        list.add("A");
        list.add("B");
        list.add("C");
        
        // 打印链表的内容
        System.out.println(list); // 输出: [A, B, C]
    }
}

2. 插入元素

LinkedList提供了在链表头部和尾部以及指定位置插入元素的方法。

// 在链表的头部插入元素
list.addFirst("First"); // 等同于 offerFirst("First")
// 在链表的尾部插入元素
list.addLast("Last"); // 等同于 offerLast("Last")
// 在指定位置插入元素
list.add(1, "Inserted"); // 在索引1的位置插入"Inserted"

3. 删除元素

可以从链表中删除头部、尾部或指定位置的元素。

// 删除链表的头部元素并返回它
String head = list.removeFirst(); // 等同于 pollFirst()
// 删除链表的尾部元素并返回它
String tail = list.removeLast(); // 等同于 pollLast()
// 删除指定位置的元素并返回它
String removedElement = list.remove(1); // 删除索引1的元素

4. 访问元素

可以使用索引来访问链表中的元素，但这并不是链表的优势所在，因为需要从头或尾开始遍历。

// 获取指定位置的元素（不删除）
String element = list.get(1); // 获取索引1的元素，不删除它

5. 检查元素是否存在

// 检查链表是否包含某个元素
boolean contains = list.contains("A"); // 如果链表包含"A"，则返回true

6. 遍历链表

可以使用迭代器或增强型for循环来遍历链表。

// 使用迭代器遍历链表
for (String item : list) {
    System.out.println(item); // 打印每个元素
}
// 或者使用迭代器显式地遍历链表
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next()); // 打印每个元素
}

7. 其他常见操作

LinkedList还提供了一些其他有用的方法，如获取链表的大小、清空链表等。

// 获取链表的大小（元素数量）
int size = list.size(); // 返回链表中的元素数量
// 清空链表中的所有元素
list.clear(); // 移除链表中的所有元素，使其变为空链表

这些示例代码涵盖了LinkedList类中大多数常见方法的用法。请注意，LinkedList是一个线程不安全的类，如果需要在多线程环境中使用，应该考虑使用外部同步或其他并发集合类。

ListNode

ListNode 通常是在实现链表数据结构时自定义的一个类，尤其在算法和数据结构的课程或面试准备中很常见。在Java中，一个基本的 ListNode 类可以定义如下：

public class ListNode {
    int val;           // 存储节点的值
    ListNode next;     // 指向下一个节点的指针

    // 构造函数
    public ListNode(int value) {
        this.val = value;
        this.next = null;
    }
}

在这个定义中，ListNode 类有两个成员变量：一个 int 类型的 val 用于存储节点的值，另一个 ListNode 类型的 next 用于指向链表中的下一个节点。这个 next 变量实际上就是链表中的“指针”，尽管在Java中并没有真正的指针，但这个引用起到了指针的作用。

以下是如何使用 ListNode 来创建一个简单链表的示例：

public class LinkedListDemo {
    public static void main(String[] args) {
        // 创建链表 1 -> 2 -> 3
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        
        // 打印链表的值
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
    }
}

在这个示例中，我们首先创建了一个头节点 head，然后通过设置每个节点的 next 属性来连接其他节点，从而形成一个链表。然后，我们遍历这个链表并打印出每个节点的值。输出将会是 1 2 3。