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

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对象
    ArrayListString>
     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对象
    LinkedListString>
     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) {
    
    ArrayListString>
     arrayList = new ArrayList>
    ();
    
    LinkedListString>
     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的不同特点和适用场景。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！