java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?

简介: java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?


基本介绍

还记得我们的java集合框架吗, 我们来复习一下, 如图:

        可以看出来 ArrayList和LinkedList 都是具体类, 他们都是接口List的实现类.

但是他们底层的逻辑是不同的, 相信学过这个的应该大概有个映像吧, 如下图:

       可以看出来, ArrayList是向内存申请一块连续的数组空间进行存储, 在数组的存储形式的基础上进行链表的增删改查, 而LinkedList则是每次添加元素的时候就向系统申请一块内存, 不用就直接释放, 他们虽然在内存上不是连续的, 但是在逻辑上他们是连在一起的.

有什么不同??

  • 底层实现不同, ArrayList是基于动态数组的数据结构, 而LInkedLIst是基于双向链表的数据结构
  • 随机访问的性能不同, Arraylist的随机访问性能是由于LinkedList的, 因为ArrayList可以根据下标来直接访问, 类似于数组, 时间复杂度为O(1), 但是LinkedList的随机访问时间复杂度为O(n), 因为他需要遍历整个链表才能找到指定的元素
  • 插入和删除不同, 对于插入和删除, LInkedList要明显由于ArrayList, 因为LInkedList的掺入和删除操作时间复杂度为O(1), 例如插入, 我们可以直接在链表的头部进行插入或者是通过一个元素来记录最后一个结点的位置, 然后直接在最后一个结点进行尾插, 删除是相同的操作, 因此时间复杂度为O(1), 但是对于ArrayList就不同了, ArrayList的插入和删除需要移动插入位置的元素的后面的所有元素, 最坏的情况需要移动ArrayList的所有元素, 因此时间复杂度为O(n)

但是需要注意的是, 其实他们插入的平均时间复杂度是一样的, 接下来我们来探讨一下, 他们两个的平均时间复杂度:

  • 对于ArrayList的插入的平均时间复杂度, 它想要插入一个数字, 虽然是直接指定插入的地方, 也就是他的一个随机插入的性质, 但是它还需要对后面的元素进行一个挪动, 运气不好的话, 就需要挪动整个数组, 时间复杂度最坏的情况下是O(n), 最坏的情况下是O(1), 平均下来就是O(n/2), 我们去掉系数, 也就是O(n)
  • 对于LinkedList来说, 他进行插入, 需要遍历链表,从头到尾遍历, 好的情况就是在头的时候就便利到了, 时间复杂度为O(1), 坏的情况下需要遍历完整个链表, 时间复杂度最坏的情况就是O(n),平均下来就是O(n/2) ,去掉系数就是O(n)

   所以对于我们真是运用链表的场景, 没有说他们两个哪个时间复杂度, 或者是性能更好, 只能是在不同的情况下适应不同的场景.

小结:

       ArrayList 和 LinkedList 都是 List 接口的实现类,但它们的底层实现(结构)不同、随机访问的性能和添加/删除的效率不同。如果是随机访问比较多的业务场景可以选择使用 ArrayList,如果添加和删除比较多的业务场景可以选择使用 LinkedList。

       ArrayList适用于需要快速随机访问元素的场景,因为它的底层是基于数组实现的,可以通过下标直接访问元素。但是,当需要频繁插入或删除元素时,由于需要移动元素,效率较低。

       LinkedList适用于需要频繁插入或删除元素的场景,因为它的底层是基于链表实现的,插入或删除元素只需要改变指针指向,效率较高。但是,当需要随机访问元素时,由于需要遍历链表,效率较低。

       因此,根据具体的场景需求,选择合适的集合类可以提高程序的效率。

ArrayList的扩容机制

我们首先创建一个ArrayList如图:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class Test  {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>(); // 第0步:创建基于链表的List
        arrayList.add(1);  // 1 添加元素
        arrayList.add(2);  // 2 添加元素
        arrayList.add(3);  // 3 添加元素
        arrayList.add(4);  // 4 添加元素
        arrayList.add(5);  // 5 添加元素
        arrayList.add(6);  // 6 添加元素
        arrayList.add(7);  // 7 添加元素
        arrayList.add(8);  // 8 添加元素
        arrayList.add(9);  // 9 添加元素
        System.out.println("hello");  // 打印
 
    }
}

第0步, 初始化:

ArrayList的构造方法如下:

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
 
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
 
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
 

里面有三个重载的构造方法, 简单来说就是:

  1. 无参构造: Obeject数组elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  2. 给定初始容量: ①当 传入的初始容量initialCapacity > 0为真时,创建一个大小为initialCapacity的空数组,并将引用赋给elementData;
    ②当 传入的初始容量initialCapacity = 0为真时,将空数组EMPTY_ELEMENTDATA赋给elementData;
    ③当 传入的初始容量initialCapacity < 0为真时,直接抛出IllegalArgumentException异常。

此处我们传入的initialCapacity为空, 也就是无参构造方法, 如下:

transient Object[] elementData;
 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

        在构造方法中,它将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData,这个DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的Object数组,而elementData就是ArrayList实际存储数据的容器

第1步, 添加元素1:

触发:

   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

ensureCapacityInternal为确认初始化容量:

进入ensureCapacityInternal:

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

随后进入calculateCapacity计算最低所需容量:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

       此处的minCapacity为 size + 1, 翻译过来也就是最低所需的容量, 研究发现, 如果是空数组(刚开始使用无参构造方法的时候)就返回DEFAULT_CAPACITY, 值为10.

       当elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的时候, 直接返回minCapacity.

       随后进入ensureExplicitCapacity(int minCapacity)方法:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

modCount++,这是用来记录数组被修改次数的变量,我们先不管它. minCapacity为计算出来的最小所需容量, elementData.length为当前容量,如果最小所需容量大于当前容量, 就需要扩容, 然后进入grow方法:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

       老的容量为当前容量,新的容量为老的容量的1.5倍,如果新的容量–最小所需容量<О那么新的容量就等于最小所需容量,如果新的容量-当前数组最大的容量限制>0,那么就进入hugeCapacity方法,然后使用copyOf方法进行数据迁移.将老的数据迁移到新的容量的数组中

总结一下:

       我们使用无参构造方法的时候, 就会创建一个底层为空的数组的链表, 此时size 为0, 然后向里面添加元素的时候, 此时的minCapacity为 size + 1 = 1, 在calculateCapacity方法中返回了DEFAULT_CAPACITY(10), 然后进入ensureExplicitCapacity(10), 此时的minCapacity = 10 > 当前容量 = 0, 所以进行初始扩容(elementData = Arrays.copyOf(elementData, newCapacity)), 将容量扩充到10, 也就是elementData/length == 10, 随后的插入, 只要没有超过10, 那就可以直接插入, 如果容量满了, 那么就进行1.5倍扩容.

ArrayLIst的基本使用

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class Test  {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>(); // 第0步:创建基于链表的List
        // add(int x) 直接向元素末尾位置添加x
       arrayList.add(1);
 
       // get(int index) 方法, 返回下标为index的元素
       int a = arrayList.get(0);
        System.out.println(a);
 
        // add(int index, int element); 向指定位置插入元素
        arrayList.add(1,3);
 
        // size(); 获取当前元素的个数
        int size = arrayList.size();
 
        // remove(int index); 删除下标为index 的元素
        arrayList.remove(0);
 
        // 判断arrList是否为空, 如果为空就返回true, 否则返回false;
        arrayList.isEmpty();
 
        // set(int index, int element); 将index 下标的元素设置为 element
        arrayList.set(0,5);
 
    }
}

LInkedList与之类似

ArrayList和Vector

       ArrayList和Vector都实现了List接口. 代码演示如图:

import java.util.ArrayList;
import java.util.Vector;
 
public class Main {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        Vector<String> vector = new Vector<>();
 
        // 添加元素
        arrayList.add("Java");
        arrayList.add("Python");
        arrayList.add("C++");
 
        vector.add("Java");
        vector.add("Python");
        vector.add("C++");
 
        // 获取元素
        System.out.println(arrayList.get(0));
        System.out.println(vector.get(0));
 
        // 删除元素
        arrayList.remove(0);
        vector.remove(0);
 
        // 获取元素个数
        System.out.println(arrayList.size());
        System.out.println(vector.size());
    }
}

但它们有以下区别:

  1. 线程安全性:Vector 是线程安全的,而 ArrayList 不是。所以在多线程环境下,应该使用 Vector
  2. 性能:由于 Vector 是线程安全的,所以它的性能通常比 ArrayList 差。在单线程环境下,ArrayList 比 Vector 快
  3. 初始容量增长方式:当容量不足时,ArrayList 默认会增加 50% 的容量,而 Vector 会将容量翻倍。这意味着在添加元素时,ArrayList 需要更频繁地进行扩容操作,而 Vector 则更适合于存储大量数据。 Vector的grow方法

       综上所述,如果不需要考虑线程安全问题,并且需要高效的存取操作,则 ArrayList 是更好的选择;如果需要考虑线程安全以及更好的数据存储能力,则应该选择 Vector。

目录
相关文章
|
2天前
|
存储 安全 Java
滚雪球学Java(60):深入解析Java中的Vector集合类!
【6月更文挑战第14天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
137 59
滚雪球学Java(60):深入解析Java中的Vector集合类!
|
3天前
|
Java
Java基础7-一文搞懂抽象类和接口,从基础到面试题,揭秘其本质区别(二)
Java基础7-一文搞懂抽象类和接口,从基础到面试题,揭秘其本质区别(二)
9 0
|
3天前
|
设计模式 Java 内存技术
Java基础7-一文搞懂抽象类和接口,从基础到面试题,揭秘其本质区别(一)
Java基础7-一文搞懂抽象类和接口,从基础到面试题,揭秘其本质区别(一)
12 0
|
5天前
|
存储 安全 Java
Java集合详解:Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素,如ArrayList(适合读取)和LinkedList(适合插入删除)。Set不允许重复,有HashSet(无序)和TreeSet(排序)。Map存储键值对,HashMap(无序)和TreeMap(排序)。Vector是线程安全的ArrayList替代品,但在多线程环境下使用。选择集合类型应根据应用场景,如有序、无序、键值对需求及线程安全考虑。
|
8天前
|
消息中间件 存储 缓存
面试题--HashMap和TreeMap的区别和应用场景有啥区别?
然后底层调用key的hashCode()方法得出hash值; 过哈希表哈希算法,将hash值转换成数组的下标(注1),下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有值。此时,就会拿着key和链表上每个节点的key进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖,如果最终长度大于8就会转成红黑树,红黑树插入;
12 3
|
11天前
|
存储 算法 Java
JAVA后端开发面试题库
JAVA后端开发面试题库
19 1
|
15天前
|
缓存 安全 Java
【Java面试——并发基础、并发关键字】
随着硬件指令集的发展,我们可以使用基于冲突检测的乐观并发策略: 先进行操作,如果没有其它线程争用共享数据,那操作就成功了,否则采取补偿措施(不断地重试,直到成功为止)。这种乐观的并发策略的许多实现都不需要将线程阻塞,因此这种同步操作称为非阻塞同步。 乐观锁需要操作和冲突检测这两个步骤具备原子性,这里就不能再使用互斥同步来保证了,只能靠硬件来完成。硬件支持的原子性操作最典型的是: 比较并交换(Compare-and-Swap,CAS)。CAS 指令需要有 3 个操作数,分别是内存地址 V、旧的预期值 A 和新值 B。当执行操作时,只有当 V 的值等于 A,才将 V 的值更新为 B。
|
23天前
|
SQL 存储 Java
致远互联java实习生面试
致远互联java实习生面试
34 0
|
24天前
|
Java
java面试基础 -- 普通类 & 抽象类 & 接口
java面试基础 -- 普通类 & 抽象类 & 接口
26 0
|
Java
LinkedList源码解读—Java8版本(下)
LinkedList源码解读—Java8版本(下)
116 0