手记

线性表数据结构解读(一)顺序存储结构ArrayList

线性表

线性表:零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度。

A=(a1,a2,……ai-1,ai,ai+1,……,an);

A代表一个线性表
ai(1<=i<=n)成为线性表的元素,i为元素的下标,表示该元素在线性表中的位置
线性表中n为表长,其中n>=0
长度等于零时称为空表,通常记为:L=( )
将元素ai-1成为元素ai的直前驱,将元素ai+1成为元素ai的直接后继。

理解线性表的定义有以下要点

⑴ 序列——顺序性:元素具有线性顺序,第一个元素无前驱,最后一个元素无后继,其他每个元素有且仅有一个前驱和一个后继。
⑵ 有限——有限性:元素个数有限,在计算机中处理的对象都是有限的。
⑶ 相同类型——相同性:元素取自于同一个数据对象,这意味着每个元素占用相同数量的存储单元。
⑷ 元素类型不确定——抽象性:数据元素的类型是抽象的、不具体的,需要根据具体问题确定。

线性表的操作

建表(初始化)、求表长、查找、插入、删除

线性表的存储结构

包括顺序存储结构和链式存储结构两种,因此可以将线性表分为顺序表和链表两大类

本篇博文我们来一起学习下顺序存储结构。

顺序存储结构

定义:线性表在顺序存储形式下构成的表。

线性表的顺序存储结构具有两个基本特点

① 线性表中所有元素所占的存储空间是连续的;
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

假设线性表中的第一个数据元素的存储地址(即首地址)为 ADR(a1),每一个数据元素占k个字节,则线性表中第i个元素ai在计算机存储空间中的存储地址为:ADR(ai)=ADR(a1)+(i-1)k

例如:长度为n的线性表在计算机中的顺序存储结构

在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储空间。数组需要根据情况预设足够的大小,同时还需要一个变量指出线性表在数组中的当前状况,如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺序表,可将它们封装在一起。

顺序存储结构的优缺点

优点:查询很快
缺点:插入和删除效率慢

在Java中,我们常见具有代表性的顺序存储结构有很多,这里我们以ArrayList为例,进行分析,看看它内部是如何实现顺序存储结构的,由于源码过长,这里我们重点分析增删改查和迭代器方法。

构造方法

ArrayList提供了三个构造方法,可以构造一个默认初始容量为12的空列表和构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表,这些元素按照该集合的迭代器返回它们的顺序排列。

public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
    /**
     * 最小容量值,Java中为10,android中为12
     */
    private static final int MIN_CAPACITY_INCREMENT = 12;

    /**
     * 数组元素的长度
     */
    int size;

    /**
     * ArrayList是基于数组的方式实现的
     */
    transient Object[] array;

    /**
     * 创建一个指定带容量大小的ArrayList
     */
    public ArrayList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity < 0: " + capacity);
        }
        array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
    }

    /**
     * 创建一个无参构造的ArrayList
     */
    public ArrayList() {
        array = EmptyArray.OBJECT;
    }

    /**
     * 创建一个包含collection的ArrayList
     */
    public ArrayList(Collection<? extends E> collection) {// java的多态性
        if (collection == null) {
            throw new NullPointerException("collection == null");
        }

        Object[] a = collection.toArray();
        if (a.getClass() != Object[].class) {
            Object[] newArray = new Object[a.length];
            System.arraycopy(a, 0, newArray, 0, a.length);
            a = newArray;
        }
        array = a;
        size = a.length;
    }

添加方法

    /**
     * 添加方法,添加到列表的尾部
     */
    @Override public boolean add(E object) {
        Object[] a = array;// 将array赋值给一个局部数组
        int s = size;// 用局部的s获取长度
        if (s == a.length) {// 如果现在的长度等于数组array的长度,那么空间满了,需要声明一个新数组
            Object[] newArray = new Object[s +
                    (s < (MIN_CAPACITY_INCREMENT / 2) ?
                     MIN_CAPACITY_INCREMENT : s >> 1)];// s<6?12:6
            System.arraycopy(a, 0, newArray, 0, s);// 把原来的数组拷贝到新的数组中来
            array = a = newArray;
        }
        a[s] = object;// 把元素添加进来
        size = s + 1;// 长度+1
        modCount++;// 计量器,只要数组中元素动一下,它就+1
        return true;
    }

    /**
     * 添加方法,添加到指定位置
     *
     * @param index the index at which to insert the object.
     * @param object the object to add.
     * @throws IndexOutOfBoundsException
     *             when {@code location < 0 || location > size()}
     */
    @Override public void add(int index, E object) {
        Object[] a = array;
        int s = size;
        if (index > s || index < 0) {
            throwIndexOutOfBoundsException(index, s);
        }
        // 当数组长度容量足够时,执行System.arraycopy方法实现数组的复制
        if (s < a.length) {
            System.arraycopy(a, index, a, index + 1, s - index);
        } else {// 当数组容量不足时,进行扩容
            // assert s == a.length;
            // 创建新数组
            Object[] newArray = new Object[newCapacity(s)];
            // 将数据拷贝到新数组中,并移动位置
            System.arraycopy(a, 0, newArray, 0, index);
            System.arraycopy(a, index, newArray, index + 1, s - index);
            array = a = newArray;
        }
        a[index] = object;
        size = s + 1;
        modCount++;
    }
    /**
     * 添加方法,将容器中所有元素添加到此列表的尾部
     * Adds the objects in the specified collection to this {@code ArrayList}.
     * @param collection the collection of objects.
     * @return {@code true} if this {@code ArrayList} is modified, {@code false}
     *         otherwise.
     */
    @Override public boolean addAll(Collection<? extends E> collection) {
        Object[] newPart = collection.toArray();
        int newPartSize = newPart.length;
        if (newPartSize == 0) {
            return false;
        }
        Object[] a = array;
        int s = size;
        int newSize = s + newPartSize; // If add overflows, arraycopy will fail
        if (newSize > a.length) {
            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }
        System.arraycopy(newPart, 0, a, s, newPartSize);
        size = newSize;
        modCount++;
        return true;
    }

删除方法

    /**
     * 删除列表中指定位置上的元素
     * @param index the index of the object to remove.
     * @return the removed object.
     * @throws IndexOutOfBoundsException
     *             when {@code location < 0 || location >= size()}
     */
    @Override public E remove(int index) {
        Object[] a = array;
        int s = size;
        if (index >= s) {
            throwIndexOutOfBoundsException(index, s);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        // 将删除位置之后的元素向前挪动一个位置
        System.arraycopy(a, index + 1, a, index, --s - index);
        // 将数组末尾置空
        a[s] = null;  
        size = s;
        modCount++;
        return result;
    }
    // 删除列表中首次出现的指定元素(如果存在)
    @Override public boolean remove(Object object) {
        Object[] a = array;
        int s = size;
        if (object != null) {
            for (int i = 0; i < s; i++) {
                if (object.equals(a[i])) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        } else {
            for (int i = 0; i < s; i++) {
                if (a[i] == null) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        }
        return false;
    }

修改方法

    /**
     * 修改方法
     *
     * @param index the index at which to put the specified object.
     * @param object the object to add.
     * @return the previous element at the index.
     * @throws IndexOutOfBoundsException
     *             when {@code location < 0 || location >= size()}
     */
    @Override public E set(int index, E object) {
        Object[] a = array;// 给一个下标index,用object修改
        if (index >= size) {
            throwIndexOutOfBoundsException(index, size);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        a[index] = object;
        return result;
    }

查找方法

     /**
     * 查找是否包含某个元素
     *
     * @param object the object to search for.
     * @return {@code true} if {@code object} is an element of this
     *         {@code ArrayList}, {@code false} otherwise
     */
    @Override public boolean contains(Object object) {
        Object[] a = array;// 声明一个Object数组
        int s = size;
        if (object != null) {
            for (int i = 0; i < s; i++) {// 全部遍历一遍,找到元素返回true
                if (object.equals(a[i])) {
                    return true;
                }
            }
        } else {// 没找到返回false
            for (int i = 0; i < s; i++) {
                if (a[i] == null) {
                    return true;
                }
            }
        }
        return false;
    }

迭代器

    /**
     * 每个List都会有一个迭代器,里面包含hasNext方法,remove方法,
     */
    private class ArrayListIterator implements Iterator<E> {
        /** Number of elements remaining in this iteration */
        private int remaining = size;// 剩下来的数量,用全局变量数组的长度赋值

        /** Index of element that remove() would remove, or -1 if no such elt */
        private int removalIndex = -1;

        /** The expected modCount value */
        private int expectedModCount = modCount;

        public boolean hasNext() {// 下面是否还有元素
            return remaining != 0;
        }

        @SuppressWarnings("unchecked") public E next() {
            ArrayList<E> ourList = ArrayList.this;
            int rem = remaining;
            if (ourList.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (rem == 0) {// 没有元素可以遍历了
                throw new NoSuchElementException();
            }
            remaining = rem - 1;
            return (E) ourList.array[removalIndex = ourList.size - rem];
        }

        public void remove() {// 用迭代器进行删除,实际上创建一个新数组,删除然后进行copy
            Object[] a = array;
            int removalIdx = removalIndex;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (removalIdx < 0) {
                throw new IllegalStateException();
            }
            System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
            a[--size] = null;  // Prevent memory leak
            removalIndex = -1;
            expectedModCount = ++modCount;
        }
    }

    @Override public int hashCode() {
        Object[] a = array;
        int hashCode = 1;
        for (int i = 0, s = size; i < s; i++) {
            Object e = a[i];
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }
    // 判断两个对象是否相等
    @Override public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (!(o instanceof List)) {
            return false;
        }
        List<?> that = (List<?>) o;
        int s = size;
        if (that.size() != s) {
            return false;
        }
        Object[] a = array;
        if (that instanceof RandomAccess) {
            for (int i = 0; i < s; i++) {
                Object eThis = a[i];
                Object ethat = that.get(i);
                if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
                    return false;
                }
            }
        } else {  // Argument list is not random access; use its iterator
            Iterator<?> it = that.iterator();
            for (int i = 0; i < s; i++) {
                Object eThis = a[i];
                Object eThat = it.next();
                if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
                    return false;
                }
            }
        }
        return true;
    }

其他方法

    /**
     * 清空ArrayList集合中所有元素,使用Arrays.fill方法,将其填充为null
     * @see #isEmpty
     * @see #size
     */
    @Override public void clear() {
        if (size != 0) {
            Arrays.fill(array, 0, size, null);
            size = 0;
            modCount++;
        }
    }

    /**
     * 克隆方法,由于ArrayList实现了Cloneable接口,所以能被克隆
     *
     * @return a shallow copy of this {@code ArrayList}
     * @see java.lang.Cloneable
     */
    @Override public Object clone() {
        try {
            ArrayList<?> result = (ArrayList<?>) super.clone();
            result.array = array.clone();
            return result;
        } catch (CloneNotSupportedException e) {
           throw new AssertionError();
        }
    }
    /**
     * 创建一个新的Object数组,把array中的元素拷贝到数组中,然后返回
     * @return an array of the elements from this {@code ArrayList}
     */
    @Override public Object[] toArray() {
        int s = size;
        Object[] result = new Object[s];
        System.arraycopy(array, 0, result, 0, s);
        return result;
    }

通过源码分析,我们可以看出ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长;我们可以通过下标索引直接查找到指定位置的元素,因此查找效率高,但每次插入或删除元素,就要大量地移动元素,因此插入删除元素的效率低。

2人推荐
随时随地看视频
慕课网APP