Java --- LIst ArrayList

自定义线性表顺序存储方式

package P2.线性结构;

import P1.接口.List;

import java.util.Comparator;
import java.util.Iterator;

//自定义线性表顺序存储方式
public class ArrayList implements List {
    //定义数组容器 data.length指的是当前数组容量
    private E[] data;
    //元素个数 size = 0 线性表尾空 ，size==data.length线性表满了
    //size 新元素默认尾部添加是要去掉角标
    private int size;
    //默认容量
    private  static  int DEFAULT_CAPACITY = 10;

    //默认构造函数,创建一个默认容量为10的线性表
    public ArrayList(){
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;

    }
//指定默认容量构造函数，创建一个指定容量函数的线性表
    public  ArrayList(int capacity){
        if(capacity <= 0  ){
            throw new IllegalArgumentException("参数异常 capacity must > 0");

        }
        DEFAULT_CAPACITY = capacity;
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    //指定数组的构造函数，传入一个数组，将该数组封装成一个线性表
    private ArrayList(E[] arr){
        if(arr == null || arr.length == 0){
            throw  new IllegalArgumentException("arr can not be null");

        }
        data = (E[]) new Object[DEFAULT_CAPACITY];
        for(int i = 0 ; i < arr.length ; i++){
            add(arr[i]);
        }
    }

    @Override
    public void add(E element) {
    add(size,element);
    }

    @Override
    public void add(int index, E element) {
    if(index < 0 || index > size){
        throw  new IllegalArgumentException("add index out of range");
    }
    //判断线性表是否是满状态
        if(size == data.length){
            resize(data.length * 2);
        }

    //向后移动元素
        for (int i = size - 1; i >= index; i--) {
            data[i + 1 ] = data[i];
        }
        //将新元素加入到指定位置
        data[index] = element;
        size++;
    }

    //扩容， 缩容 ，不向外界提供
    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        for (int i = 0; i < size; i++) {
            newData[i ] = data[i];
        }
        data = newData;
    }

    @Override
    public void remove(E element) {//删除指定元素一次&&删除所有指定元素
        int index = indexOf(element);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public E remove(int index) {
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("remove index out of range");
        }
        //保存要删除的值
        E ret = data[index];
        //移动元素
        for (int i = index + 1 ; i < size; i++) {
            data[i] = data[i - 1];
        }
        size--;
        //什么时候缩容
        //1.有效元素是容量的1/4
        //2.当前容量不得少于等于默认容量
        if (size == data.length / 4 && data.length > DEFAULT_CAPACITY ){
        resize(data.length / 2 );

        }
        return ret;
    }

    @Override
    public E get(int index) {
        if(index < 0 || index >= size){
            throw  new IllegalArgumentException("get index out of range");
        }
        return data[index ];
    }

    @Override
    public E set(int index, E element) {
        if(index < 0 || index >= size){
            throw  new IllegalArgumentException("set index out of range");
        }
        E ret = data[index];
        data[index] = element;
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    //额外添加一个函数,获取线性表数组容量
    private int getCapacity(){
        return data.length;
    }

    
    @Override
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element) ) {
            return  i;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        data = (E[]) new  Object[DEFAULT_CAPACITY];
        size = 0;
    }

    @Override
    public void sort(Comparator c) {
        if (c == null){
            throw  new IllegalArgumentException("Comparator can not be null");
        }
        for (int i = 1; i < size; i++) {
            E e =data[i];
            int j = 0;
            for (j = i ;j > 0 &&  c.compare(data[j - 1], e) > 0;j--){
                data[ j ] =data[j - 1];
            }
            data[j] = e;
        }
    }

    @Override
    public boolean equals(Object o) {
        //1判断是空？
        if (o == null){
            return  false;
        }
        //2.判断自己
        if (this == o){
            return true;
        }
        //3判断类型
        if (o instanceof ArrayList){
            //4.按照自己的逻辑比较
            ArrayList other = (ArrayList) o;
            //5.比较有效元素个数
            if (this.size != other.size){
                return  false;
            }
            //6.有效元素个数相等 就逐个比较
            for (int i = 0; i < size; i++) {
                if (data[i].equals(other.data[i])){
                    return  false;
                }
            }
            return true;
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append('[');
        if(isEmpty()){
            sb.append(']');
        }else {
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                if ( i == size - 1){
                    sb.append(']');
                }else {
                    sb.append(',');
                    sb.append(' ');
                }
            }
        }
        return sb.toString();
    }

    @Override
    public List subList(int fromIndex, int toIndex) {
        if (fromIndex  < 0 || toIndex >= size || fromIndex > toIndex){
            throw  new IllegalArgumentException("must 0 <= fromindex <= toIndex");
        }
        ArrayList list = new ArrayList<>();
        for (int i = fromIndex; i < toIndex ; i++) {
            list.add(data[i] );
        }
        return null;
    }


    //获取当前数据结构 容器迭代器
    //通过迭代器更方便挨个取出每一个元素
    //同时实现了iterabla 可以让当前数据结构 容器 被foreach循环遍历
    @Override
    public Iterator iterator() {

        return new ArrayListIterator();
    }

    //创建迭代器,内部类
    class  ArrayListIterator implements Iterator{
        private  int cur = 0;

        @Override
        //判断是否有下一个元素
        public boolean hasNext() {
            return  cur < size;
        }

        //如果有下一个 则把当前元素返回并移至到下一个元素
        @Override
        public E next() {

            return data[cur++];
        }
    }
}

package P1.接口;

import java.util.Comparator;

//线性表接口定义
public interface List extends  Iterable {
//默认在表尾加一个元素
public  void add(E element);
//指定角标添加元素
public  void add(int index, E element);
//删除指定元素
public  void remove(E element);
//删除指定角标元素,并返回原先值
public E remove(int index);
//获取指定角标处元素的值
public E get(int index);
//修改指定角标index处值为element,并返回原先的值
public  E set(int index , E element);
//获取线性表中的元素个数
public int size();
//查看元素第一次出现的角标位置
public int indexOf(E element);
//查看是否包含元素
public boolean contains(E element);
//判断线性表是否为空
public  boolean isEmpty();
//清空线性表元素
public  void  clear();
//排序
public  void  sort(Comparator c);
//获取子线性表
public List subList(int fromIndex , int toIndex);
}

package P0.测试;

import P2.线性结构.ArrayList;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

public class TestArrayList {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        System.out.println(list);
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            list.add(random.nextInt(100));
        }
        System.out.println(list);

        for (int i = 0; i < 10; i++) {
            list.add(0,i);
        }
        System.out.println(list);
        list.sort(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 -o2;
            }
        });
        System.out.println(list);

        for(Integer num : list){
            System.out.println(num);
        }
        Iterator it = list.iterator();
        while (it.hasNext()){
            System.out.println(it.next() + " ");
        }
    }
}