Java的LinkedList、HashSet与TreeSet

一、LinkedList

LinkedList是Java集合框架中的一个重要类，它实现了List接口。与ArrayList不同，
（1）LinkedList是基于双向链表的数据结构，因此它在进行插入、删除操作时通常比ArrayList更快，但在随机访问元素时可能会比较慢。
（2）LinkedList 不是线程安全的。如果需要在多线程环境中使用，可以使用 Collections.synchronizedList 方法来创建一个同步的列表。
添加元素：
add(E e): 在链表末尾添加元素。
add(int index, E element): 在指定位置插入元素。
addFirst(E e): 在链表开头添加元素。
addLast(E e): 在链表末尾添加元素（与 add(E e) 等效）。
删除元素：
remove(): 删除并返回链表的第一个元素。
remove(int index): 删除指定位置的元素。
remove(Object o): 删除链表中第一个出现的指定元素。
removeFirst(): 删除并返回链表的第一个元素。
removeLast(): 删除并返回链表的最后一个元素。
获取元素：
get(int index): 获取指定位置的元素。
getFirst(): 获取链表的第一个元素。
getLast(): 获取链表的最后一个元素。
检查元素：
contains(Object o): 检查链表中是否包含指定的元素。
indexOf(Object o): 返回链表中第一次出现的指定元素的索引。
lastIndexOf(Object o): 返回链表中最后一次出现的指定元素的索引。
其他操作：
size(): 返回链表中元素的数量。
isEmpty(): 检查链表是否为空。
clear(): 移除链表中的所有元素。
poll(): 获取并移除链表的第一个元素，如果链表为空则返回 null。
peek(): 获取链表的第一个元素但不移除它，如果链表为空则返回 null。
使用上与ArrayList类似：

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // 添加元素
        list.add("Apple");
        list.addFirst("Banana");
        list.addLast("Cherry");

        // 获取元素
        System.out.println("First element: " + list.getFirst());
        System.out.println("Element at index 1: " + list.get(1));
        System.out.println("Last element: " + list.getLast());

        // 删除元素
        list.removeFirst();
        list.remove("Cherry");

        // 遍历链表
        for (String fruit : list) {
            System.out.println(fruit);
        }

        // 检查元素
        System.out.println("Contains 'Apple': " + list.contains("Apple"));

        // 获取链表大小
        System.out.println("Size of list: " + list.size());
    }
}

输出结果如下：

First element: Banana
Element at index 1: Apple
Last element: Cherry
Apple
Size of list: 1
Contains 'Apple': true
Size of list: 0

补充ArrayList

（1）ArrayList 是基于动态数组的数据结构。当创建 ArrayList 实例时，它会在内部创建一个固定大小的数组。如果数组满了，ArrayList 会自动创建一个更大的数组，并将现有元素复制到新数组中。这种动态扩容机制使得 ArrayList 在添加和删除元素时（特别是在数组中间位置）可能需要移动大量的元素。
（2）ArrayList 和 LinkedList 都不是线程安全的。如果需要在多线程环境中使用，应该使用同步机制（如 Collections.synchronizedList）或选择线程安全的替代方案（如 CopyOnWriteArrayList 或 ConcurrentLinkedQueue）。

二、HashSet

（1）HashSet是Set接口的一个实现，其底层实际上使用了HashMap来存储元素。
（2）HashSet不是线程安全的，如果多个线程同时访问和修改同一个HashSet实例，可能会导致不确定的结果。
示例：使用HashSet去重

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class HashSetExample {
    public static void main(String[] args) {
        List<String> listWithDuplicates = new ArrayList<>();
        listWithDuplicates.add("Apple");
        listWithDuplicates.add("Banana");
        listWithDuplicates.add("Apple"); // 重复项
        listWithDuplicates.add("Cherry");

        // 使用HashSet去除重复项
        Set<String> uniqueSet = new HashSet<>(listWithDuplicates);

        // 将去重后的结果转换回List（如果需要）
        List<String> uniqueList = new ArrayList<>(uniqueSet);

        // 输出结果
        System.out.println("Original list: " + listWithDuplicates);
        System.out.println("Unique list: " + uniqueList);
    }
}

补充HashMap

（1）HashMap是一种基于哈希表实现的Map接口的。HashMap的内部是一个数组加链表（或红黑树）的结构。数组中的每个位置称为一个桶（Bucket），每个桶中可能包含一个链表或红黑树，用来处理哈希冲突。

三、TreeSet

TreeSet 是 Java 集合框架中的一个类，它实现了 NavigableSet 接口，并且基于 TreeMap 实现。TreeSet 中的元素是唯一的，并且会根据元素的自然顺序（或者通过提供的比较器进行排序）进行排序。