ArrayList、LinkedList的特点、实现、优缺点比较

原创

堕落飞鸟

发布于 2023-04-04 07:10:40

4290

发布于 2023-04-04 07:10:40

文章被收录于专栏：飞鸟的专栏

ArrayList和LinkedList都是Java中的集合框架中的列表（List）接口的实现类。它们都实现了相同的接口，但是它们的内部实现和使用场景有所不同。

ArrayList

ArrayList是基于数组的列表实现。它可以动态地增加和缩小列表的大小，可以快速地访问列表中的元素，但是插入和删除元素的效率较低。

a) 特点：

内部使用数组实现，数组的大小会动态地增加或缩小，以适应列表的大小。
ArrayList的get和set操作的时间复杂度为O(1)，可以快速访问列表中的元素。
插入和删除元素的效率较低，需要移动其他元素，时间复杂度为O(n)。
ArrayList支持随机访问，但不支持快速随机访问。

b) 示例代码：

import java.util.ArrayList;

public class ArrayListExample {
  public static void main(String[] args) {
    // 创建一个ArrayList对象
    ArrayList<String> list = new ArrayList<>();

    // 向列表中添加元素
    list.add("apple");
    list.add("banana");
    list.add("orange");

    // 访问列表中的元素
    System.out.println(list.get(0)); // 输出：apple

    // 删除列表中的元素
    list.remove(1);

    // 遍历列表中的元素
    for (String s : list) {
      System.out.println(s);
    }
  }
}

LinkedList

LinkedList是基于链表的列表实现。它可以高效地插入和删除元素，但是访问元素的效率较低。

a) 特点：

内部使用链表实现，每个节点都存储了元素的值和指向下一个节点的指针。
LinkedList的插入和删除操作的时间复杂度为O(1)，可以高效地插入和删除元素。
LinkedList的get和set操作的时间复杂度为O(n)，因为需要遍历整个列表才能访问元素。
LinkedList不支持随机访问，但支持快速随机访问。

b) 示例代码：

import java.util.LinkedList;

public class LinkedListExample {
  public static void main(String[] args) {
    // 创建一个LinkedList对象
    LinkedList<String> list = new LinkedList<>();

    // 向列表中添加元素
    list.add("apple");
    list.add("banana");
    list.add("orange");

    // 访问列表中的元素
    System.out.println(list.get(0)); // 输出：apple

    // 删除列表中的元素
    list.remove(1);

    // 遍历列表中的元素
    for (String s : list) {
      System.out.println(s);
    }
  }
}

优缺点比较

ArrayList和LinkedList的优缺点如下所示：

ArrayList的优点：支持快速访问元素，可以通过下标直接访问元素；内存连续
ArrayList的缺点：插入和删除元素的效率较低，需要移动其他元素；当插入和删除操作频繁时，会导致内存碎片化。
LinkedList的优点：插入和删除元素的效率较高，因为只需要改变节点的指针即可；内存不连续，可以避免内存碎片化。
LinkedList的缺点：访问元素的效率较低，需要遍历整个列表才能访问元素；每个节点需要额外存储指向下一个节点的指针，会占用更多的内存空间。

综上所述，当需要高效地插入和删除元素时，应该选择LinkedList；当需要高效地访问元素时，应该选择ArrayList。如果不确定哪种列表更适合，可以考虑使用ArrayList，因为它在大多数情况下都能够满足需求。

示例代码：

import java.util.ArrayList;
import java.util.LinkedList;

public class ListExample {
  public static void main(String[] args) {
    ArrayList<String> arrayList = new ArrayList<>();
    LinkedList<String> linkedList = new LinkedList<>();

    // 向ArrayList和LinkedList中添加元素
    for (int i = 0; i < 10000; i++) {
      arrayList.add("element" + i);
      linkedList.add("element" + i);
    }

    // 访问ArrayList和LinkedList中的元素
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
      arrayList.get(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("ArrayList访问时间：" + (endTime - startTime) + "ms");

    startTime = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
      linkedList.get(i);
    }
    endTime = System.currentTimeMillis();
    System.out.println("LinkedList访问时间：" + (endTime - startTime) + "ms");

    // 删除ArrayList和LinkedList中的元素
    startTime = System.currentTimeMillis();
    for (int i = 9999; i >= 0; i--) {
      arrayList.remove(i);
    }
    endTime = System.currentTimeMillis();
    System.out.println("ArrayList删除时间：" + (endTime - startTime) + "ms");

    startTime = System.currentTimeMillis();
    for (int i = 9999; i >= 0; i--) {
      linkedList.remove(i);
    }
    endTime = System.currentTimeMillis();
    System.out.println("LinkedList删除时间：" + (endTime - startTime) + "ms");
  }
}

在以上示例中，我们创建了一个包含10000个元素的ArrayList和LinkedList，并分别访问了它们中的每个元素，然后删除了它们中的所有元素，并测量了访问和删除操作的时间。运行示例代码后，可以发现访问ArrayList的时间要比访问LinkedList的时间短很多，但删除LinkedList的时间要比删除ArrayList的时间短很多。这进一步证明了ArrayList和LinkedList的不同特点和适用场景。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

登录后参与评论

0 条评论

热度