【算法】1.线性表的实现（ArraysList）

本文主要是介绍【算法】1.线性表的实现（ArraysList），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. List接口的定义
   线性结构可以由顺序存储结构和链式存储结构实现
   将两者对线性结构共同的操作进行抽取，定义出线性结构的接口

   package p1.接口;
   import java.util.Comparator;
   //线性表接口的定义
   public interface List<E> extends Iterable<E> {
   	//默认在表尾添加一个元素
   	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);
   	//修改指定角标处的元素，并返回原先的值
   	public E set(int index, E element);
   	//获取线性表中元素的个数
   	public int size();
   	//查看元素第一次出现的角标位置（从左到右）
   	public int indexOf(E elemrnt);
   	//判断是否包含元素
   	public boolean contains(E element);
   	//判断线性表是否为空
   	public boolean isEmpty();
   	//清空线性表
   	public void clear();
   	//按照比较器的内容进行排序
   	public void sort(Comparator<E> c);
   	//获取子线性表[formIndex,toIndex)
   	public List<E> subList(int fromIndex, int toIndex);
   }
   

2. 线性表的实现ArrayList

ArrayList就是线性结构顺序存储方式的具体实现，称为线性表
创建ArrayList类实现List接口

2.1定义相关成员属性

三个成员属性：data size DEFAULT_CAPACITY

	/数组的容器 data.length 指的就是当前数组的容量
    private E[] data;
    //元素的个数 size == 0 线性表为空 size == data.length 线性表满了
    //size 新元素默认尾部添加时要去的角标
    private int size;
    //默认容量
    private static int  DEFAULT_CAPACITY = 10;
    //创建一个默认容量为10的线性表

2.2定义构造函数

data不能直接引用外部传入的数组arr否则外部对arr的修改会引起ArrayList内部的一些问题

	//创建一个默认容量为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;
    }
    //传入一个数组 将该数组封装成为一个线性表
    public 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]);
        }
    }

3. ArraysList中具体方法的实现

3.1默认在表尾添加一个元素	
	直接调用add(int index, E element)

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

3.2在指定角标处添加元素
	1.首先判断下标存在
	2.再判断线性表是否为满，如果元素数量等于线性表容量，调用扩缩容的方法进行扩容
	3.扩容默认两倍扩
	4.然后从下标size-1开始到index位置的数挨个往后移动一个
	5.将新元素插入到指定位置

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(2 * data.length);
        }
        //向后移动元素
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        //将新元素插入到指定位置
        data[index] = element;
        size++;
    }

3.3扩容/缩容方法

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

3.4删除指定元素

 public void remove(E element) {
        int index = indexOf(element);
        if(index != -1){
            remove(index);
        }
    }

3.5删除指定角标处的元素，并返回原先值
	1.首先判断下标存在
	2.先保存要删除的值
	3.移动元素
	4. 当有效元素是容量的1/4且当前容量不得小于等于默认容量

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 - 1] = data[i];
        }
        size--;

        //什么时候缩容
        //1.有效元素是容量的1/4
        //2.当前容量不得小于等于默认容量
        if (size == data.length / 4 && data.length > DEFAULT_CAPACITY) {
            resize(data.length / 2);
        }
        return ret;
    }

3.6获取指定角标元素

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

    }

3.7修改指定角标处的元素，并返回原先的值

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;
    }

3.8获取线性表中元素的个数

public int size() {
        return size;
    }

3.9额外添加一个函数 获取线性表中那个数组的容量

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

3.10查看元素第一次出现的角标位置（从左到右）

public int indexOf(E element) {
         /*
        == 比的是啥？主要看等号的两边是啥
        == 两边是基本数据类型的话 比的是值
            byte short int long
            float double
            char boolean
        == 两边是引用数据类型的话 比的是地址
            数组 字符串 其他的类对象
        */
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

3.11按照比较器的内容进行排序

@Override
    //按照比较器的内容进行排序
    public void sort(Comparator<E> 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;
        }
    }

3.12获取子线性表[formIndex,toIndex)

//获取子线性表[formIndex,toIndex)
    public List<E> subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
            throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");
        }
        ArrayList<E> list = new ArrayList<>();
        for (int i = fromIndex; i <= toIndex; i++) {
            list.add(data[i]);
        }
        return list;
    }

3.13重写equals方法

public boolean equals(Object o) {
        //1.判空
        if (o == null) {
            return false;
        }
        //2.判自己
        if (this == o) {
            return true;
        }
        //3.判类型
        if (o instanceof ArrayList) {
            //4.按照自己的逻辑进行比较
            ArrayList<E> other = (ArrayList<E>) o;
            //5.先比有效元素的个数
            if (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;
    }

3.14重写toString方法

 public String toString() {
        StringBuilder sb = new StringBuilder();
        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();
    }
    //获取当前这个数据结构/容器 的 迭代器
    //通过迭代器对象 更方便挨个取出每一个元素
    //同时 实现了Iterable 可以让当前的数据结构/容器 被foreach循环遍历
    @Override
    public Iterator<E> iterator() {
        return new ArrayListIterator();
    }


    //创建一个属于ArrayList的迭代器
    class ArrayListIterator implements Iterator<E> {
        private int cur = 0;
        @Override
        public boolean hasNext() {//判断是否有下一个元素
            return cur < size;
        }
        @Override
        public E next() {//如果有下一个元素 则把当前元素返回 并移至到下一个元素
            return data[cur++];
        }
    }

3.15创建一个属于ArrayList的迭代器

    //获取当前这个数据结构/容器 的 迭代器
    //通过迭代器对象 更方便挨个取出每一个元素
    //同时 实现了Iterable 可以让当前的数据结构/容器 被foreach循环遍历
    @Override
    public Iterator<E> iterator() {
        return new ArrayListIterator();
    }
    //创建一个属于ArrayList的迭代器
    class ArrayListIterator implements Iterator<E> {
        private int cur = 0;
        @Override
        public boolean hasNext() {//判断是否有下一个元素
            return cur < size;
        }
        @Override
        public E next() {//如果有下一个元素 则把当前元素返回 并移至到下一个元素
            return data[cur++];
        }
    }

这篇关于【算法】1.线性表的实现（ArraysList）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！