1.Java动态数组的用法详解

     Java动态数组是一种可以任意伸缩数组长度的对象，在Java中比较常用的是ArrayList，ArrayList是javaAPI中自带的java.util.ArrayList。下面介绍一下ArrayList作为Java动态数组的用法。

 语法：add()是添加一个新的元素,remove()删除一个元素,size()获得ArrayList的长度。ArrayList的下标是从0开始。

import java.util.ArrayList;
 
public class JavaArrayList {
	public static void main(String[] args) {
		// Java动态数组的初始化
		ArrayList al = new ArrayList();
		// 向Java动态数组中添加数据
		al.add("a");
		al.add("b");
		al.add("c");
		// 输出Java动态数组
		for (int i = 0; i < al.size(); i++) {
			String alEach = (String) al.get(i);
			System.out.println(alEach);
		}
		// 删除数组中的某个元素,删除第二个元素
		al.remove(1);
		// 修改Java动态数组，把新的元素放到第二个位置
		al.add(1, "2");
		// //输出Java动态数组
		for (int i = 0; i < al.size(); i++) {
			String alEach = (String) al.get(i);
			System.out.println(alEach);
		}
	}
}

2.动态数组实现(ArrayList原理)

2.1 什么是数组

        同类数据元素的集合，在计算机中以连续的地址存储，编译时确定长度，无法改变。

2.2 什么是动态数组

       数据结构中顺序表的物理实现，同类数据元素的集合，在计算机中以连续的地址存储，大小在创建时决定，但是可以改变。

2.3 为什么使用动态数组

       支持随机访问,查询速度快。但是插入和删除都需要移动元素，比起链表开销较大。如：java集合类中的ArrayList Vector等

2.4 动态数组实现代码(ArrayList原理)

/**
 * 顺序表的实现
 * @author chengh
 * @param 
 */
public class ArrayList<E> {
    private Object[] data = null; // data: 用来保存此线性表数据的数组
    private int capacity; // capacity： 线性表的容量
    private int current; // current： 当前数据的下标
    /**
     * 初始化为声明大小，则设置为10。
     */
    ArrayList() {
        this(10);
    }
    /**
     * 初始化线性表，声明保存数据的数组大小。
     * @param initialSize 顺序表的初始化大小
     */
    ArrayList(int initialSize) {
        if (initialSize >= 0) {
            this.capacity = initialSize;
            data = new Object[initialSize];
            current = 0;
        } else {
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }
    /**
     * 在线性表的末尾添加元素，添加之前确认线性表是否已满
     * @param e 待加入的元素
     * @return
     */
    public boolean AddElement(E e) {
        ensureCapacity();
        data[current] = e;
        ++current;
        return true;
    }
    /**
     * 检查存储数据的数组容量，如果数组已经满，则扩充容量；否则不操作。
     */
    private void ensureCapacity() {
        int index;
        if (current == capacity) {
            capacity *= 2;
            Object[] newData = new Object[capacity];
            for(index = 0; index < current; ++index) {
                newData[index] = data[index];
            }
            data = newData;
        }
    }
    /**
     * 返回下标为index的元素
     * @param index 欲取得元素的下标
     * @return
     */
    public E get(int index) {
        validateIndex(index);
        return (E) data[index];
    }
    /**
     * 
     * @param index 待插入的位置
     * @param e 待插入的元素
     * @return
     */
    public boolean set(int index, E e) {
        validateIndex(index);
        data[index] = e;
        return true;
    }
    /**
     * 验证下标值是否合法，非法时抛出异常
     * @param index 待验证的下标值
     */
    private void validateIndex(int index) {
        if (index < 0 || index > current) {
            throw new RuntimeException("无效的下标：" + index);
        }
    }
    /**
     * 返回当前顺序表的大小
     * @return
     */
    public int size() {
        return current;
    }
    /**
     * 在指定位置插入指定元素
     * @param index 待插入的位置
     * @param e 待插入的元素
     * @return
     */
    public boolean insert(int index, E e) {
        validateIndex(index);
        ensureCapacity();
        for (int temp = current; temp > index; --temp) {
            data[temp] = data[temp - 1];
        }
        data[index] = e;
        return true;
    }
    /**
     * 删除下标为index元素
     * @param index 待删除元素的下标
     * @return
     */
    public boolean delete(int index) {
        validateIndex(index);
        for ( ; index < current - 1; ++index) {
            data[index] = data[index + 1];
        }
        data[current - 1] = null;
        --current;
        return true;
    }
    @Override
    public String toString() {
        String str = "[ ";
        for (Object o : data) {
            if (o != null) {
                str += o + " ";
            }
        }
        str += "]";
        return str;
    }
} 

前言:
基于Java提供的静态数组,自定义实现的动态数组
代码如下:

/**
 * @ClassName Array
 * @Description  基于java数组进行二次封装
 * @Author lilei
 * @Date 16/06/2019 11:09
 * @Version 1.0
 **/

public class Array<E> {

    private E[] data;
    private int size;

    public Array(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }

    public Array(){
        this(10);
    }

    public int getCapacity() {
        return data.length;
    }


    public int getSize() {
        return size;
    }

    // 判断是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 增加一个元素
    public void addLast(E e){
        if (size == data.length)
            resize(2 * data.length);
        data[size++] = e;
    }

    //指定索引增加元素
    public void add(int index, E e){
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index < size.");
        }

        if (size == data.length){
            resize(2 * data.length);
        }

        if (size == data.length/2)
            resize(data.length/2);

        for (int i = size -1; i >= index ; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    // 在数组开头增加元素
    public void addFirst(E e){
        add(0, e);
    }

    // 获得指定索引元素
    public E get(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal");
        return data[index];
    }

    // 查找数组中是否有元素e
    public boolean contains(E e){
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))
                return true;
        }
        return false;
    }

    // 查找元素e所在索引
    public int find(E e){
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal");
        E ret = data[index];
        for (int i = index +1 ; i < size ; i++)
            data[i-1] = data[i];
        size--;
        data[size] = null; // loitering objects != memory leak
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素
    public E removeLast(){
        return remove(size-1);
    }

    // 删除指定元素
    public void removeElement(E e){
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    // 修改指定索引元素
    public void set(int index, E e){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal");
        data[index] = e;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size -1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }

}

使用Java中的数组

int[] arr=new int[10];
for(int i=0;i<arr.length;i++)
    arr[i]=i;
int[] scores =new int[]{100,99,66};
for (int i=0;i<scores.length;i++)
    System.out.println(scores[i]);
for(int score:scores)
    System.out.println(score);
scores[0]=98;
for(int score:scores)
    System.out.println(score);

自己实现的动态数据

public class Array<E> {
    private E[] data;
    private int size;

    /**
     *构造函数，传入数组的容量capacity构造Array
     */
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size=0;
    }

    /**
     * 无参数的构造函数，默认数组的容量capacity=10
     */
    public Array(){
        this(10);
    }

    //获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    // 返回数组是否为空
    public boolean isEmpty(){
        return  size==0;
    }

    // 向所有元素后添加一个新元素,O(1)
    public void addLast(E e){
//        if(size==data.length)
//            throw new IllegalArgumentException("AddLast failed!");
//        data[size]=e;
//        size++;
     add(size,e);
    }

    // 在所有元素前添加一个新元素,O(1)
    public void addFirst(E e){
        add(0, e);
    }

    //在第index个位置插入一个新元素e,O(n/2)=O(n)
    public void add(int index,E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed!,Require index >= 0 and index <= size.");

        if (size == data.length)
            resize(2*data.length);

        for(int i = size-1;i>=index;i--)
            data[i+1]=data[i];
        data[index]=e;
        size++;
    }

    //获取index索引位置的元素,O(1)
    public E get(int index){
        if(index<0 || index>=size)
            throw new IllegalArgumentException("Get failed.Index is illegal.");
        return data[index];
    }

    //修改index索引位置的元素为e,O(1)
    void set(int index,E e){
        if(index<0 || index>=size)
            throw new IllegalArgumentException("Set failed.Index is illegal.");
        data[index]=e;
    }

    //查找数组中是否有元素e,O(n)
    public boolean contains(E e){
        for (int i =0 ; i<size;i++){
            if(data[i].equals(e))
                return true;
        }
        return false;
    }

    // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1,O(n)
    public int find(E e){
        for (int i =0 ; i<size;i++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素, 返回删除的元素,O(n)
    public E remove(int index){
        if(index<0 || index>=size)
            throw new IllegalArgumentException("Remove failed.Index is illegal.");
        E ret=data[index];
        for(int i = index+1;i<size;i++)
            data[i-1]=data[i];
        size--;
        data[size]=null;//loitering objects != memory leak

        if(size == data.length / 2)
            resize(data.length / 2);
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

     从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size-1);
    }

    // 从数组中删除元素e
    public void removeElement(E e){
        int index=find(e);
        if(index!=-1)
            remove(index);
    }

    @Override
    public String toString(){
        StringBuilder res=new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for(int i =0;i<size;i++){
            res.append(data[i]);
            if(i!=size-1)
                res.append(",");
        }
        res.append(']');
        return res.toString();
    }

    // 将数组空间的容量变成newCapacity大小
    private void resize(int newCapacity){
        E[] newData=(E[])new Object[newCapacity];
        for(int i=0;i<size;i++)
            newData[i]=data[i];
        data=newData;
    }

}

验证自己实现的动态数组

public class Main {
    public static void main(String[] args) {

//        int[] arr=new int[10];
//        for(int i=0;i<arr.length;i++)
//            arr[i]=i;
//        int[] scores =new int[]{100,99,66};
//        for (int i=0;i<scores.length;i++)
//            System.out.println(scores[i]);
//        for(int score:scores)
//            System.out.println(score);
//        scores[0]=98;
//        for(int score:scores)
//            System.out.println(score);


           Array<Integer> arr=new Array<>();
           for (int i=0;i<10;i++)
               arr.addLast(i);
           System.out.println(arr);

           arr.add(1,100);
           System.out.println(arr);

           arr.addFirst(-1);
           System.out.println(arr);

           arr.remove(2);
           System.out.println(arr);

           arr.removeElement(4);
        System.out.println(arr);

        arr.removeFirst();
        System.out.println(arr);

    }
}

自己定义一个Student类，来验证刚才实现的动态数组

public class Student {

    private String name;
    private int score;

    public Student(String studentname,int studentScore){
        name =studentname;
        score=studentScore;
    }

    @Override
    public String toString(){
        return String.format("Student(name: %s,score: %d)",name,score);
    }

    public static void main(String[] args) {
        Array<Student> arr=new Array<>();
        arr.addLast(new Student("Alice",100));
        arr.addLast(new Student("Bob",66));
        arr.addLast(new Student("David",88));
        System.out.println(arr);
    }
}