ArrayList线性表Java实现

超、凢脫俗 2022-06-02 10:22 158阅读 0赞

自定义List接口

/** * * @ClassName: List * @Description: 列表的接口 * @author xiaomu * @date 2018年1月14日 下午4:25:05 * * @param <T> */
    public interface List<T> {
        /** * 判断列表是否为空 * @Title: isEmpty * @Description: 判断列表是否为空 * @param @return 设定文件 * @return boolean 返回类型 * @throws */
        boolean isEmpty();
    
        /** * 获得列表长度 * @Title: lenth * @Description: 获得列表长度 * @param @return 设定文件 * @return int 返回类型 * @throws */
        int lenth();
    
        /** * 根据序号获取单个元素 * @Title: get * @Description: 根据序号获取单个元素 * @param @param index * @param @return 设定文件 * @return T 返回类型 * @throws */
        T get(int index);
    
        /** * 从头开始查询一个元素，若找到则返回序号，找不到则返回-1 * @Title: indexOf * @Description:从头开始查询一个元素，若找到则返回序号，找不到则返回-1 * @param @param elem * @param @return 设定文件 * @return int 返回类型 * @throws */
        int indexOf(T elem);
    
        /** * 向指定位置之后插入一个元素 * @Title: insert * @Description:向指定位置之后插入一个元素 * @param @param index * @param @param elem 设定文件 * @return void 返回类型 * @throws */
        void insert(int index, T elem);
    
        /** * 删除指定位置的元素 * @Title: remove * @Description: 删除指定位置的元素 * @param @param index * @param @return 设定文件 * @return T 返回类型 * @throws */
        T remove(int index);
    
        /** * 在列表最后添加一个元素 * @Title: add * @Description: 在列表最后添加一个元素 * @param @param elem 设定文件 * @return void 返回类型 * @throws */
        void add(T elem);
    
        /** * 从列表最后删除一个元素，并且返回这个元素 * @Title: pop * @Description: 从列表最后删除一个元素，并且返回这个元素 * @param @return 设定文件 * @return T 返回类型 * @throws */
        T pop();
    
        /** * 删除列表中所有元素 * @Title: removeAll * @Description: 删除列表中所有元素 * @param 设定文件 * @return void 返回类型 * @throws */
        void removeAll();
    }

ArrayList:

/** * * @ClassName: ArrayList * @Description: 线性表 * @author xiaomu * @date 2018年1月14日 下午3:53:06 * * @param <T> */
    @SuppressWarnings("all")
    public class ArrayList<T> implements List<T> {
        private final static int INIT_SIZE = 10;
        private final static int EXPAND_SIZE = 20;
        private int size = 0;
        private Object[] elementData;
    
        public ArrayList() {
            this(INIT_SIZE);
        }
    
        public ArrayList(int size) {
            elementData = new Object[size];
        }
    
        private void expend() {
            Object[] temp = new Object[elementData.length + EXPAND_SIZE];
            System.arraycopy(elementData, 0, temp, 0, size);
            elementData = temp;
        }
    
        @Override
        public boolean isEmpty() {
            return 0 == size;
        }
    
        @Override
        public int lenth() {
            return size;
        }
    
        @Override
        public T get(int index) {
            if (index < 0 || index > size - 1) {
                return null;
            }
            return (T) elementData[index];
        }
    
        @Override
        public int indexOf(T elem) {
            if (null == elem) {
                return -1;
            }
            for (int i = 0; i < size; i++) {
                if (elem == elementData[i]) {
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public void insert(int index, T elem) {
            if (size + 1 > elementData.length) {
                expend();
            }
            if (index != size) {
                System.arraycopy(elementData, index, elementData, index + 1, size - index);
            }
    
            elementData[index] = elem;
            size++;
    
        }
    
        @Override
        public T remove(int index) {
            T elem = (T) elementData[index];
            System.arraycopy(elementData, index, elementData, index - 1, size - index);
            elementData[size--] = null;
            return elem;
        }
    
        @Override
        public void add(T elem) {
            if (size + 1 > elementData.length) {
                expend();
            }
            elementData[size++] = elem;
    
        }
    
        @Override
        public T pop() {
            T elem = (T) elementData[size--];
            return elem;
        }
    
        @Override
        public void removeAll() {
            while (size >= 0) {
                elementData[size--] = null;
            }
            size = 0;
        }
    
    }

线性表的特点：  
1、采用一段连续的储存单元依次储存线性表的数据元素  
2、查找的时间复杂度为O(1)  
3、插入和删除的时间复杂度为O(n)  
4、线性表需要预分配储存空间，可能会造成内存浪费