【数据结构】线性表 ( 线性表概念简介 | 顺序存储结构 / 链式存储结构 | 顺序存储结构 - 顺序表 List | 顺序表 ArrayList 源码分析 )

韩曙亮

发布于 2023-10-11 16:48:47

2200

发布于 2023-10-11 16:48:47

文章被收录于专栏：韩曙亮的移动开发专栏

一、线性表概念简介

线性表是一组按照顺序排列的元素组成的数据集合 ;

线性表有两种存储结构 :

顺序存储结构 : 在内存中存储的数据是连续的 , 如 : 数组 ;
链式存储结构 : 在内存中存储的数据是不连续的 , 如 : 链表 ;

线性表中

除第一个元素外 , 每个元素都有一个唯一的前驱元素 ;
除最后一个元素外 , 每个元素都有一个唯一的后继元素 ;

所有的元素形成了一条线性的结构。

二、顺序存储结构 - 顺序表 List

顺序存储结构就是顺序表 List ;

顺序存储结构：

内存连续 : 顺序存储结构在内存中使用连续的内存空间来存储线性表中的元素。
索引访问 : 在顺序存储结构中，数据元素按照特定顺序依次存放在内存中的连续地址空间中，可以通过索引来访问元素。索引就是内存地址 ;
顺序存储结构 ( 顺序表 ) 示例 :
- 数组
- ArrayList , 其内部也是数组实现的 ;

顺序表优点：

随机访问： 通过索引下标可以直接访问内存中指定位置的元素 , 时间复杂度为 O(1) ;
存储效率高： 不需消耗额外空间定义指针指向其它元素存，只需要元素本身的存储空间。

顺序表缺点：

插入和删除效率低： 顺序存储结构中，插入和删除操作需要整体移动所有元素，时间复杂度为 O(n) ;
固定存储空间： 数组在创建时需要指定固定的大小，创建后该大小不可改变 ;

顺序表代码示例 : 顺序表直接存储在数组中 ;

class Students {
	Student[20];
	int size;
}

三、顺序表 ArrayList 源码分析

在 Java 中的 ArrayList 就是顺序表 , 下面分析其源码 ;

ArrayList 源代码地址 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/ArrayList.java

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初始容量。
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 用于默认大小的空实例的共享空数组实例。我们
     * 将其与EMPTY_ELEMENTDATA区分开来，以了解何时膨胀多少
     * 添加第一个元素。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区。
     * ArrayList的容量就是这个数组缓冲区的长度。任何
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * 将在添加第一个元素时扩展为DEFAULT_CAPACITY。
     */
    transient Object[] elementData; // 非私有以简化嵌套类访问

    /**
     * 数组列表的大小(包含的元素数量)。
     *
     * @serial
     */
    private int size;
}

默认的 ArrayList 的初始容量为 int DEFAULT_CAPACITY = 10 , 如果调用不含任何参数的构造函数 , 则默认的初始容量就是 10 ;

    /**
     * 构造一个初始容量为10的空列表。
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

在 ArrayList # add 方法中 , 调用了 ensureCapacityInternal 函数处理数组的大小是否够用 ;

调用 elementData[size++] = e 代码 , 向数组末尾添加元素 e ;

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在 ensureCapacityInternal 函数中 , 调用了 ensureExplicitCapacity 函数 ,

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

在 ensureExplicitCapacity 函数中 , 调用了 grow 函数 , 就是增加 ArrayList 容量的函数 ;

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

在 grow 函数中 , 创建了新的数组 , 并将原来数组中的数据拷贝到新数组中 ;

    /**
     * 增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
     *
     * @param minCapacity 所需的最小容量
     */
    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 ;

如果要向指定位置插入元素 , 要先将当前数组前 index 个元素进行拷贝 , 然后拷贝要插入的元素 , 最后将原数组中 index 后的元素进行拷贝 ;

其中涉及到了两次拷贝 , 操作的过程很烦碎 ;

    /**
     * 将指定元素插入此列表中的指定位置。
     * 将当前在该位置的元素(如果有的话)和任何后续元素向右移动(在它们的索引上加1)。
     *
     * @param index 要插入指定元素的索引
     * @param element 要插入的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

下面代码的作用是将 elementData 源数组 , 从 index 位置开始的元素 , 拷贝到 elementData 目的数组的 index + 1 位置 , 拷贝 size - index 个元素 , 相当于将 elementData 数组从 index 开始的元素都向后挪动了一个位置 ;

        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);

System.arraycopy 函数原型 :

    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

调用 ArrayList # remove 函数 , 删除某个元素 , 是将 index 后的元素都向前移动一个位置 ;

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

下面代码的作用是将 elementData 源数组 , 从 index + 1 位置开始的元素 , 拷贝到 elementData 目的数组的 index 位置 , 拷贝 numMoved 个元素 , 相当于将 elementData 数组从 index 开始的元素都向前挪动了一个位置 ;

            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-10-11，如有侵权请联系 cloudcommunity@tencent.com 删除

存储

本文分享自作者个人站点/博客前往查看

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

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度