当前位置:   article > 正文

顺序表ArrayList_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
推荐阅读
相关标签