LinkedList与ArrayList的比较

2024-01-03 10:47:06

1.LinkedList

  1. 基于双向链表,无需连续内存

  2. 随机访问慢(要沿着链表遍历)

  3. 头尾插入删除性能高

  4. 占用内存多

2.ArrayList

  1. 基于数组,需要连续内存

  2. 随机访问快(指根据下标访问)

  3. 尾部插入、删除性能可以,其它部分插入、删除都会移动数据,因此性能会低

  4. 可以利用 cpu 缓存,局部性原理

3.查询比较

? ? ? ? 在图上可以看到,ArrayList是内存地址是连续的,而LinkedList不是连续的,通过当前节点保存的下一个节点的位置(LinkedList底层是基于双向链表实现的)。所以,ArrayList 的随机读取速度快,而LinkedList需要一个一个的向后遍历知道遍历到所需元素。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

????????可以发现,ArrayList实现了RandomAccess接口,代表了ArrayList支持随机访问。这个接口的作用仅仅是一个标记,当使用到ArrayList时,Java的底层类库发现了RandomAccess接口,就说明可以支持根据索引随机访问存储,否则就只能使用迭代器进行遍历。

为什么要使用可序列化

这里有一个小知识点,也就是我们经常可以看到一些类中实现了可序列化接口Serializable

序列化:将 Java 对象转换成字节流的过程。

反序列化:将字节流转换成 Java 对象的过程。

当 Java 对象需要在网络上传输 或者 持久化存储到文件中时,就需要对 Java 对象进行序列化处理。

序列化的实现:类实现 Serializable 接口,这个接口没有需要实现的方法。实现 Serializable 接口是为了告诉 jvm 这个类的对象可以被序列化。

注意事项:

某个类可以被序列化,则其子类也可以被序列化
声明为 static 和 transient 的成员变量,不能被序列化。static 成员变量是描述类级别的属性,transient 表示临时数据
反序列化读取序列化对象的顺序要保持一致

4.增删比较

? ? ? ? 我们通常说ArrayList增删慢、查询快,LinkedList增删快、查询慢。其实这种说法仅仅是在初学的时候加强记忆用的,并不是完全准确的。我们说查询,是根据元素的内容去查找元素的位置,如果是使用从头往后遍历的话,ArrayList和LinkedList的时间复杂度是相同的。

? ? ? ? ArrayList在中间位置添加新元素时,会把当前位置和位置后边的所有元素复制一份,然后向后移动一位,再将新元素插入进去。越靠近头部插入,需要移动的元素越多,也就越影响性能。

  • 在头部插入时,ArrayList比LinkedList慢(ArrayList需要复制元素
  • 在尾部插入时,ArrayList比LinkedList快(差不多,略快
  • 在中间插入时,ArrayList比LinkedList快的多!!!

? ? ? ? 这个时候我们会想,在中间插入的时候,链表不应该比数组插入快的多吗?为什么会出现这样的情况。因为在中间部分插入时,首先要寻找到这个地方。而ArrayList是支持随机访问的!LinkedList则只能一个一个遍历到中间位置所以消耗的时间也就越多。

? ? ? ? 所以我们一般使用ArrayList而LinkedList使用的较少。

5.空间占用

? ? ? ? ArrayList可以利用 cpu 缓存,局部性原理来加快计算效率,而LinkedList因为不是一片连续的内存,所以不能使用,而且LinkedList占用的内存多(其中每个节点需要存储前后节点的位置)。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

文章来源:https://blog.csdn.net/g877835148/article/details/135354303
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。