顺序表ArrayList_arraylist顺序

ArrayList

基本概念：

1. 顺序表的底层是顺序存储结构， 也就是数组
2. 顺序表的最直观理解是变长数组，动态数组
3. 顺序表充分体现了封装与抽象之美

java 语言实现

ArrayList 需要实现下面的接口

/**顺序表的增删改查*/
public interface List<T>
{
    /** 第一个位置插入 */
    void addFirst(T data);

    /** 在最后一个位置插入 */
    void addLast(T data);

    /** 删除index对应位置的节点， 并返回该节点的数据 */
    T delete(int index);

    /** 在index 对应位置加入数据 */
    void add(int index, T data);

    /** 更改index对应位置的数据为data */
    void set(int index, T data);

    /** 查询index对应位置的数据 */
    T get(int index);

    /** 获取data元素第一次出现时候的index  */
    int getIndex(T data);

    /**遍历顺序表*/
    void traverse();
    
    /**获取顺序表大小*/
    int size();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

成员变量与构造函数

ArrayList 底层维护着一个数组对象， 它的最大容量是capacity, size 用来表示ArrayList 插入元素的数目

package com.weinijuan;

public class ArrayList<T> implements List<T>
{
    private int size;
    private int capacity = 16;
    private T[] ar;
    public ArrayList()
    {
        ar = (T[]) new Object[capacity];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

实现addLast

这是ArrayList 类用的最多的方法， 乍一看貌似会数组下标访问越界， 实则不然， capacity才是数组真正的容量， size 是当前对象最后一个元素下标（index - 1）的后面一个位置的下标。

因为插入了一个元素， 所以size需要加一。

这段代码虽然简单，但几乎是ArrayList 最重要的方法

@Override
public void addLast(T data)
{
    ar[size] = data;
    size++;
}
1
2
3
4
5
6

实现扩容机制

上面的缺陷就是最多只能有16个元素，可以在size == capacity 的时候进行扩容.

扩容原理：

1. 新创建一个更大容量的数组
2. 将原先数组的内容拷贝到 新创建的数组中
   （System.arraycopy方法，第一个参数是被拷贝的数组， 第二个是开始拷贝的位置，
   第三个是被拷入的数组， 第四个是开始拷入的位置， 第五个是拷贝的个数 ）
3. 更新ar, 令ar 指向新数组
4. 更新capacity

System.arraycopy 经常出现在ArrayList 中，需要掌握

private void resize(int newCapacity)
{
    T[] temp = (T[]) new Object[newCapacity];
    System.arraycopy(ar, 0, temp, 0, size);
    ar = temp;
    capacity = newCapacity;
}

@Override
public void addLast(T data)
{
    if (size == capacity)
    {
        resize(2*capacity);
    }
    ar[size] = data;
    size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

删除最后一个元素和缩小容量

1. 一旦size < capacity/4, 就缩小容量为二分之一， 从而保证ArrayList 的利用率大于等于百分之五十。这个参数可以自己调
2. 取得返回数据
3. 逻辑大小减一
4. 将原先位置的最后一个元素置为null ， 从而防止对象游离， 对于原始数据类型这一步可以省略
5. 返回数据

对象游离： 因为通过数组可以访问到最后一个本应该被删除的对象， 所以垃圾回收器不会回收这个对象， 导致对象游离

public T deleteLast(int index)
{
    if (size < capacity/4)
    {
        resize(capacity/2);
    }
    T retData = ar[size - 1];
    size--;
    ar[size] = null;
    return retData;
}
1
2
3
4
5
6
7
8
9
10
11

上面的几个方法非常简单，非常重要，后面的几个方法可能复杂，但是实际中并不是经常使用

实现add(index, data)

1. 数组边界检查， 声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/715442