顺序表和模拟实现ArrayList的常用方法

灰太狼 2022-11-06 01:00 283阅读 0赞

### 模拟实现ArrayList的常用方法 ###

*  ArrayList
 *   *  ArrayList：顺序表
     *  顺序表和数组的区别：
     *  顺序表中的注意点：
 *  ArrayList的常用方法
 *  模拟实现ArrayList的常用方法

# ArrayList #

## ArrayList：顺序表 ##

我们可以将顺序表的底层理解成为一个数组（可以扩容的数组），但是相比于数组多出一个记录有效数据的计数器size，如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

## 顺序表和数组的区别： ##

上面说，顺序表的底层可以理解为一个数组，但是相比于数组，更加的高级。  
顺序表可以自己扩容；  
顺序表严格区分数组容量和元素的个数。  
所以数组其实就是一种不完备的顺序表。

## 顺序表中的注意点： ##

我们需要区分顺序表中的两个概念：容量（capacity）和元素个数（size）。  
容量可以理解为数组的大小（长度），元素个数是size中记录的有效元素个数。  
顺序表中，数据的存储是需要连续的，不可以元素和元素之间存在“空隙”，当进行插入、删除等操作时，操作完成后，也要保证顺序表的连续。

# ArrayList的常用方法 #

在Java中，内置了ArrayList的许多方法，我们常用的一些方法（增删改查），如下：

//尾插
        boolean add(Integer e);
        //指定位置插入
        void add(int index, Integer e);
        //删除指定位置
        Integer remove(int index);
        //删除指定元素
        boolean remove(Integer e);
        //获取元素
        Integer get(int index);
        //set
        Integer set(int index, Integer e);
        //判断是否包含
        boolean contains(Integer e);
        //从前到后首次遇到
        int indexOf(Integer e);
        //从后到前首次遇到
        int lastIndexOf(Integer e);
        //请空顺序表
        void clear();
        //获取元素个数
        int size();
        //判断size==0？
        boolean isEmpty();

# 模拟实现ArrayList的常用方法 #

当我们需要模拟实现ArrayList的时候，我们需要先创建一个数组，和计数器size。  
我们需要考虑到数组连续性的问题，以及操作中判断数组是否满了，需要2倍扩容的题，以及下标合法性校验…

1、定义接口，列出需要实现的方法：

package ArrayList;
    public interface MyList { 
        //尾插
        boolean add(Integer e);
        //指定位置插入
        void add(int index, Integer e);
        //删除指定位置
        Integer remove(int index);
        //删除指定元素
        boolean remove(Integer e);
        //获取元素
        Integer get(int index);
        //set
        Integer set(int index, Integer e);
        //判断是否包含
        boolean contains(Integer e);
        //从前到后首次遇到
        int indexOf(Integer e);
        //从后到前首次遇到
        int lastIndexOf(Integer e);
        //请空顺序表
        void clear();
        //获取元素个数
        int size();
        //判断size==0？
        boolean isEmpty();
    }

2、具体实现：

package ArrayList;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    /** * 模拟实现自己的ArrayList */
    public class MyArrayList implements MyList { 
        private Integer[] array;
        private int size;
    
        public MyArrayList() { 
            array = new Integer[10];
            size = 0;
        }
    
        //判断是否满了
        private void isFull() { 
            if (size < array.length) { 
                return;
            }
            //2倍扩容
            this.array = Arrays.copyOf(this.array, array.length * 2);
        }
    
    
        @Override
        public boolean add(Integer e) { 
            isFull();
            array[size] = e;
            size++;
            return true;
        }
    
        @Override
        public void add(int index, Integer e) { 
            isFull();
            if (index < 0 || index > size()) { 
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
            }
            for (int from = size() - 1; from >= index; from--) { 
                array[from + 1] = array[from];
            }
            array[index] = e;
            size++;
        }
    
        @Override
        public Integer remove(int index) { 
            if (index < 0 || index >= size()) { 
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
            }
            Integer e = array[index];
            for (int from = index + 1; from < size; from++) { 
                array[from - 1] = array[from];
            }
            array[size - 1] = null;
            size--;
            return e;
        }
    
        @Override
        public boolean remove(Integer e) { 
    
            int i = indexOf(e);
            if (i < 0) { 
                return false;
            }
            remove(i);
            return true;
        }
    
        @Override
        public Integer get(int index) { 
            if (index < 0 || index >= size()) { 
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
            }
            return array[index];
        }
    
        @Override
        public Integer set(int index, Integer e) { 
            if (index < 0 || index >= size()) { 
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
            }
            Integer old = array[index];
            array[index] = e;
            return old;
        }
    
        @Override
        public boolean contains(Integer e) { 
            return indexOf(e) >= 0;
        }
    
        @Override
        public int indexOf(Integer e) { 
            for (int i = 0; i < size(); i++) { 
                if (array[i].equals(e)) { 
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public int lastIndexOf(Integer e) { 
            for (int i = size() - 1; i >= 0; i--) { 
                if (array[i].equals(e)) { 
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public void clear() { 
            Arrays.fill(array, null);
            size = 0;
        }
    
        @Override
        public int size() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return size == 0;
        }
    
        @Override
        public String toString() { 
    
            Integer[] toShow = Arrays.copyOf(array, size);
            return Arrays.toString(toShow);
        }
    }

3、测试

package ArrayList;
    
    public class MyArrayListDemo { 
        public static void main(String[] args) { 
            MyList list = new MyArrayList();
            System.out.println(list);   // []
            list.add(1);
            list.add(2);
            list.add(3);
            System.out.println(list);   // [1, 2, 3]
            list.add(0, 100);
            list.add(0, 200);
            list.add(0, 300);
            System.out.println(list);   // [300, 200, 100, 1, 2, 3]
    
            Integer remove = list.remove(2);
            System.out.println(list);   // [300, 200, 1, 2, 3]
            System.out.println(remove); // 100
    
            boolean r = list.remove((Integer)1);    // 通过类型转换，确认调用的是 remove(Integer) 而不是 remove(int)
            System.out.println(r);      // true
            System.out.println(list);   // [300, 200, 2, 3]
    
            System.out.println(list.size());
            System.out.println(list.isEmpty());
            list.clear();
            System.out.println(list.size());
            System.out.println(list.isEmpty());
        }
    }

4、结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]  
总结：我发现数据结构的逻辑性很强，需要慢慢的思考，结合图形，加深理解！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221023/53637433e53f41eab624f8e7b945e418.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/6af54ebdce85472c8f18b5d9ea7298d6.png