List有关知识与ArrayList的实现

• 1.可以看出List接口继承自Collection接口, Collection接口又继承自Iterable接口,即实现了迭代器的功能(遍历方式可用)
• 2.ArrayList和linkedList都继承自AbstractList, 并且实现了List接口
  所以现在我们来看一下ArrayList的常用方法

首先我们来看一下ArrayList的具体框架图

• 1 实现了RandomAccess
  RandomAccess 是一个标记接口，用于标明实现该接口的List支持快速随机访问，主要目的是使算法能够在随机和顺序访问的list中表现的更加高效。
• 2 实现了Cloneable接口
  实现Cloneable接口表示该对象能被克隆
  克隆分为浅拷贝和深拷贝两种,，浅拷贝是指拷贝对象时仅仅copy对象本身和对象中的基本变量，而不拷贝对象包含的引用指向的对象。深拷贝则拷贝引用中指向的对象
• 3 实现了Serializable接口
  代表序列化,此处不多讲,若有兴趣可以自己查
• 4 实现了List接口
  这样就可以使用List接口中定义的方法

List al = new ArrayList<>();

1.public boolean add(E e)
在ArrayList对象中尾插一个元素进入,E e 代表泛型
2. public void add(int index, E element)
在指定位置插入一个元素,注意index必须介于[0, size)间
3.public boolean addAll(Collection c)
泛型写法: 可以将包含继承自E的对象的集合放入来添加
4.public E remove(int index)
删除 index 位置元素
5.public boolean remove(Object o)
删除遇到的第一个 o
6.public E get(int index)
获取下标为index位置的元素
7.public E set(int index, E element)
将下标 index 位置元素设置为 element
8.public boolean contains(Object o)
判断 o 是否在线性表中
9.public int indexOf(Object o)
返回第一个 o 所在下标
10public int lastIndexOf(Object o)
返回最后一个 o 的下标
11 public List subList(int fromIndex, int toIndex)
截取部分List作为返回

具体使用

public static void main(String[] args) {
 List list = new ArrayList<>();
 list.add("JavaSE");
 list.add("JavaWeb");
 list.add("JavaEE");
 list.add("JVM");
 list.add("测试课程");
 System.out.println(list);
 
 // 获取list中有效元素个数
 System.out.println(list.size());
 
 // 获取和设置index位置上的元素，注意index必须介于[0, size)间
 System.out.println(list.get(1));
 list.set(1, "JavaWEB");
 System.out.println(list.get(1));
 
 // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
 list.add(1, "Java数据结构");
 System.out.println(list);
 // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
 list.remove("JVM");
 System.out.println(list);
 // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
 list.remove(list.size()-1);
 System.out.println(list);
 // 检测list中是否包含指定元素，包含返回true，否则返回false
 if(list.contains("测试课程")){
 list.add("测试课程");
 }
 // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
 list.add("JavaSE");
 System.out.println(list.indexOf("JavaSE"));
 System.out.println(list.lastIndexOf("JavaSE"));
 
 // 使用list中[0, 3)之间的元素构成一个新的ArrayList返回
 List ret = list.subList(0, 3);
 System.out.println(ret);
 
 list.clear();
 System.out.println(list.size());
}

package day20211015;

import java.util.Arrays;

public class MyArrayList {
    private E[] elements;
    private int size;
    // 默认容量 10
    private static final int DEFAULT_CAPACITY = 10;
    // 构造方法
    public MyArrayList() {
        elements = (E []) new Object[DEFAULT_CAPACITY];
    }
    public MyArrayList(int capacity) {
        if (capacity <= 0) {
            capacity = DEFAULT_CAPACITY;
        }
        elements = (E [])new Object[capacity];
    }

    public int size() {
        return size;
    }

    public boolean add(E e) {
        // 考虑扩容问题
        //elements[size++] = e;
        //return true;
        add(size, e);
        return true;
    }

    public void add(int index, E e) {
        checkRange(index);
        // 考虑扩容问题
        ensureCapacity(size);
        for (int i = size-1; i >= index ; i--) {
            elements[i+1] = elements[i];
        }
        elements[index] = e;
        size++;
    }
    // ArrayList当中的扩容方式 :
    // 1. 先按照1.5倍的方式来计算newCapacity
    // 2. 如果newCapacity > MAX_ARRAY_SIZE 按照MAX_ARRAY_SIZE 来扩容 没有超过就按照1.5倍来
    public void ensureCapacity(int size) {
        int oldCapacity = elements.length;
        if (size > oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            elements = Arrays.copyOf(elements, newCapacity);
        }
    }

    public int indexOf(E e) {
        for (int i = 0; i < size; i++) {
            // 引用类型需要使用equals方法
            if (e.equals(elements[i])) {
                return i;
            }
        }
        return -1;
    }

    public int lastIndexOf(E e) {
        for (int i = size-1; i >= 0 ; i--) {
            if (e.equals(elements[i])) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        return Arrays.toString(elements);

    }

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("remove 下标越界");
        }
        E e = elements[index];
        for (int i = index+1; i < size; i++) {
            elements[i-1] = elements[i];
        }
        elements[size-1] = null;
        size--;
        return e;
    }

    public boolean remove(E e) {
        int index = indexOf(e);
        if (-1 == index) {
            return false;
        }
        remove(index);
        return true;
    }

    private void checkRange(int index) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("index 越界");
        }
    }

    public E get(int index) {
        checkRange(index);
        return elements[index];
    }

    public void set(int index, E e){
        checkRange(index);
        elements[index] = e;
    }

    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    public boolean contains(E e) {
        return -1 != indexOf(e);
    }

    public MyArrayList subList(int from, int to) {
        if (from > to) {
            throw new IllegalArgumentException("from > to");
        }else if (from < -1 || to > size) {
            throw new IllegalArgumentException("from需要大于0, to需要小于size");
        }
        int newSize = to - from;
        MyArrayList list = new MyArrayList<>(newSize);
        while(from < to) {
            list.add(elements[from]);
            from++;
        }
        return list;
    }    
}