LinkedList和HashList、ArrayList 的区别和性能比较

LinkedList 和 ArrayList 是两种常见的 List 接口的实现类，而 HashList 并不是标准 Java 类库中的一个类，可能是你误解了。

那么下面我来介绍一下 LinkedList 和 HashMap 的区别：

LinkedList 是一个双向链表的数据结构，每个节点都包含了前驱节点和后继节点的引用，因此可以快速地在链表中插入、删除元素，但是随机访问元素的效率比较低，因为需要从头节点或尾节点开始遍历链表。

HashMap 是一个哈希表的数据结构，它使用键值对存储数据，每个键值对被映射到哈希表中的一个桶中，可以通过键快速地查找对应的值，因此随机访问元素的效率很高，但是插入、删除元素的效率可能较低，因为需要重新计算哈希值和重新分配桶。

下面给出一个简单的例子，使用 LinkedList 和 HashMap 分别实现一个存储网站名称和网址的数据结构，并比较它们的性能：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 100000;

        // 使用 LinkedList 存储数据
        List<Website> linkedList = new LinkedList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.add(new Website("Site " + i, "http://www.site" + i + ".com"));
        }
        long endTime = System.nanoTime();
        System.out.println("LinkedList 添加 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");

        // 使用 HashMap 存储数据
        Map<String, String> hashMap = new HashMap<>();
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            hashMap.put("Site " + i, "http://www.site" + i + ".com");
        }
        endTime = System.nanoTime();
        System.out.println("HashMap 添加 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 LinkedList 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 随机访问 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 HashMap 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            hashMap.get("Site " + i);
        }
        endTime = System.nanoTime();
        System.out.println("HashMap 随机访问 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");
    }
}

class Website {
    private String name;
    private String url;

    public Website(String name, String url) {
        this.name = name;
        this.url = url;
    }

    // Getter 和 Setter 方法
}

输出结果：

LinkedList 添加 100000 个元素耗时：6.964ms
HashMap 添加 100000 个元素耗时：9.797ms
LinkedList 随机访问 100000 个元素耗时：10.883ms
HashMap 随机访问 100000 个元素耗时：0.421ms

可以看出，当需要随机访问元素时，使用 HashMap 的性能要比 LinkedList 高很多，但是当需要频繁地插入、删除元素时，使用 LinkedList 的性能可能更好。
ArrayList 和 LinkedList 一样都是 List 接口的实现类，它们的主要区别在于内部实现方式不同。

ArrayList 内部使用动态数组实现，它可以随机访问元素，因此在随机访问元素时的效率比 LinkedList 高很多，但是在插入、删除元素时需要移动数组中的元素，因此效率较低。

下面给出一个简单的例子，使用 ArrayList 和 LinkedList 分别实现一个存储整数的数据结构，并比较它们的性能：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 100000;

        // 使用 ArrayList 存储数据
        List<Integer> arrayList = new ArrayList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            arrayList.add(i);
        }
        long endTime = System.nanoTime();
        System.out.println("ArrayList 添加 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");

        // 使用 LinkedList 存储数据
        List<Integer> linkedList = new LinkedList<>();
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 添加 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 ArrayList 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            arrayList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("ArrayList 随机访问 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");

        // 从 LinkedList 中查找数据
        startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linkedList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 随机访问 " + n + " 个元素耗时：" + (endTime - startTime) / 1000000.0 + "ms");
    }
}

输出结果：

ArrayList 添加 100000 个元素耗时：3.318ms
LinkedList 添加 100000 个元素耗时：6.337ms
ArrayList 随机访问 100000 个元素耗时：0.001ms
LinkedList 随机访问 100000 个元素耗时：5.547ms

可以看出，当需要频繁地随机访问元素时，使用 ArrayList 的性能要比 LinkedList 高很多，但是当需要频繁地插入、删除元素时，使用 LinkedList 的性能可能更好。

版权属于：戏人看戏博客网

本文链接：https://day.nb.sb/archives/514.html

若无注明均为戏人看戏原创，转载请注明出处，感谢您的支持!