手写ArrayList

清疚 2023-06-14 04:19 1阅读 0赞

最近大改了，增加了对泛型的支持，改进了复制数组的方式，还有迭代器的实现。具体的功能都差不多了，还有几个为空，以后有机会再完善。

package myutil;
    
    import java.util.Collection;
    import java.util.Iterator;
    import java.util.List;
    import java.util.ListIterator;
    
    public class MyArrayList<E> implements List<E> {
        
        private transient Object[] elementData;//对象数组
        private int size = 0;//长度初始值为0
    
        public MyArrayList(){
        
            elementData = new Object[10];//对象数组初始长度为10
        }
    
        public MyArrayList(int initialCapacity){
        //新建指定长度的对象数组
            if(initialCapacity >= 0){
        
                elementData = new Object[initialCapacity];
            }else{
        
                throw new IllegalArgumentException("Illegal Capacity "+initialCapacity);
            }
        }
    
        private boolean checkIndex(int index){
        //判断下标是否合法
            if(index < 0 || index >= size){
        
                throw new IndexOutOfBoundsException("Index "+index+" out of bounds for length "+size);
            }
            return true;
        }
    
        private Object[] grow(int newCapacity){
        //扩容方法
            int len = elementData.length;
            if(newCapacity > len){
        //判断是否需要扩容
                Object[] elementDataNew;
                if(newCapacity > len+(len>>1)){
        //如果扩容1.5倍容量还是不足
                    elementDataNew = new Object[newCapacity];//定义新数组长度为需要的长度
                }else{
        
                    elementDataNew = new Object[len+(len>>1)];//使用位运算扩容
                }
                return elementDataNew;
            }else{
        
                return null;
            }
        }
    
        //===================================重写List接口的方法=========================================
        @Override
        public int size() {
        //返回size值
            return size;
        }
    
        @Override
        public boolean isEmpty() {
        //size为0则为空
            return size==0;
        }
    
        @Override
        public boolean contains(Object o) {
        //遍历数组判断是否包含目标元素
            for (int i = 0; i < size; i++) {
        
                if(o.equals(elementData[i])){
        
                    return true;
                }
            }
            return false;
        }
    
        @Override
        public Iterator<E> iterator() {
        
            return listIterator();
        }
    
        @Override
        public Object[] toArray() {
        //新建一个普通数组，并赋值
            Object[] array = new Object[size];
            System.arraycopy(elementData,0,array,0,size);
            return array;
        }
    
        @Override
        public <T> T[] toArray(T[] a) {
        
            System.arraycopy(elementData,0,a,0,size);
            return a;
        }
    
        @Override
        public boolean add(E e) {
        //追加元素
            Object[] elementDataNew = grow(size+1);
            if(elementDataNew == null){
        
                elementData[size] = e;//保存新元素
            }else{
        
                System.arraycopy(elementData,0,elementDataNew,0,size);//原数组中的数据复制到新数组中
                elementDataNew[size] = e;//保存新元素
                elementData = elementDataNew;//实体数组指针指向新数组
            }
            size ++;//容量+1
            return true;
        }
    
        @Override
        public boolean remove(Object o) {
        //移除指定元素
            for (int i = 0; i < size; i++) {
        
                if(o.equals(elementData[i])){
        
                    System.arraycopy(elementData,i+1,elementData,i,size-i-1);//i之后的元素依次向前移动
                    size--;//size值-1
                    return true;
                }
            }
            return false;//元素不存在则返回false
        }
    
        @Override
        public boolean containsAll(Collection<?> c) {
        
            return false;
        }
    
        @Override
        public boolean addAll(Collection<? extends E> c) {
        
            return false;
        }
    
        @Override
        public boolean addAll(int index, Collection<? extends E> c) {
        
            return false;
        }
    
        @Override
        public boolean removeAll(Collection<?> c) {
        
            return false;
        }
    
        @Override
        public boolean retainAll(Collection<?> c) {
        
            return false;
        }
    
        @Override
        public void clear() {
        //清空列表
            for (int i = 0; i < size; i++) {
        
                elementData[i] = null;
            }
            size = 0;//size值清零
        }
    
        @SuppressWarnings("unchecked")//消除类型转换警告
        @Override
        public E get(int index) {
        //返回指定位置的元素
            if(checkIndex(index)){
        
                return (E) elementData[index];
            }else{
        
                return null;
            }
        }
    
        @SuppressWarnings("unchecked")//消除类型转换警告
        @Override
        public E set(int index, E element) {
        //设置指定位置的值，并返回原来的值
            if(checkIndex(index)){
        
                Object oldValue = elementData[index];
                elementData[index] = element;
                return (E) oldValue;
            }else{
        
                return null;
            }
        }
    
        @Override
        public void add(int index, E element) {
        //在指定位置插入元素
            if(checkIndex(index)){
        
                Object [] elementDataNew = grow(size+1);//判断是否需要扩容
                if(elementDataNew == null){
        
                    System.arraycopy(elementData,index,elementData,index+1,size-index+1);//index之后的元素依次后移
                    elementData[index] = element;//保存新元素
                }else{
        
                    System.arraycopy(elementData,0,elementDataNew,0,index);//index之前的元素复制到新数组
                    elementDataNew[index] = element;//保存新元素
                    System.arraycopy(elementData,index,elementDataNew,index+1,size-index+1);//index之后的元素往后错一位复制到新数组
                    elementData = elementDataNew;//指针指向新数组
                }
                size++;//容量+1
            }
        }
    
        @SuppressWarnings("unchecked")//消除类型转换警告
        @Override
        public E remove(int index) {
        //移除指定位置的元素，并返回被移除的对象
            if(checkIndex(index)){
        
                Object oldValue = elementData[index];
                System.arraycopy(elementData,index+1,elementData,index,size-index-1);
                size--;//容量-1
                return (E) oldValue;
            }else{
        
                return null;
            }
        }
    
        @Override
        public int indexOf(Object o) {
        //遍历数组判断目标元素位置
            for (int i = 0; i < size; i++) {
        
                if(o.equals(elementData[i])){
        
                    return i;
                }
            }
            return -1;//不存在则返回-1
        }
    
        @Override
        public int lastIndexOf(Object o) {
        //从后往前遍历数组判断目标元素位置
            for(int i = size-1 ; i >= 0 ;i--){
        
                if(o.equals(elementData[i])){
        
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public ListIterator<E> listIterator() {
        
            return new ListItr<>();
        }
    
        @Override
        public ListIterator<E> listIterator(int index) {
        
            return new ListItr<>(index);
        }
    
        @Override
        public List<E> subList(int fromIndex, int toIndex) {
        //截取指定位置的列表
            int newLength = toIndex - fromIndex;//新数组的长度
            MyArrayList<E> newArray = new MyArrayList<>(newLength);
            if(fromIndex < 0 || fromIndex >= size || toIndex < fromIndex || toIndex >= size){
        //判断下标是否合法
                throw new IndexOutOfBoundsException("fromIndex "+fromIndex+",toIndex "+toIndex+",size"+size);
            }
            System.arraycopy(elementData,fromIndex,newArray.elementData,0,newLength);//截取原数组中的元素并复制到新集合的数组中
            newArray.size = newLength;//大小修改为数组长度
            return newArray;
        }
    
        //================================其他方法====================================
        public void trimToSize(){
        //调整内部数组的长度与size相等
            elementData = toArray();//其实就是转换为普通数组
        }
    
        public boolean equals(Object o){
        //重写equals方法
            if(o==this){
        //先判断对象是不是他自身
                return true;
            }else if(o instanceof MyArrayList){
        //再判断对象类型是不是ArrayListCopy对象
                MyArrayList listObj = (MyArrayList)o;//向下转型
                if(this.size==listObj.size()){
        //比较两个对象的size是否相同
                    for (int i = 0; i < this.size; i++) {
        
                        if(this.elementData[i]!=listObj.get(i)){
        //只要有一对元素不相同则返回false
                            return false;
                        }
                    }
                    return true;//所有元素都相同则返回true
                }else{
        
                    return false;
                }
            }else{
        
                return false;
            }
        }
    
        protected void removeRange(int fromIndex,int toIndex){
        //移除指定范围的元素
            if(fromIndex < 0 || fromIndex >= size || toIndex < fromIndex || toIndex >= size){
        //判断下标是否合法
                throw new IndexOutOfBoundsException("fromIndex "+fromIndex+",toIndex "+toIndex+",size "+size);
            }
            System.arraycopy(elementData,toIndex,elementData,fromIndex,size-toIndex);//依次向前移动
            size -= toIndex-fromIndex;//重新设置size
        }
    
        public void ensureCapacity(int minCapacity){
        //如果需要，则扩容到指定大小
            if(minCapacity > size){
        
                Object[] elementDataNew = new Object[minCapacity];
                System.arraycopy(elementData,0,elementDataNew,0,size);
                elementData = elementDataNew;
                size = minCapacity;
            }
        }
    
        public String toString(){
        //重写toString方法
            StringBuilder sb = new StringBuilder("[");
            for (int i = 0; i < size-1; i++) {
        
                sb.append(elementData[i]);
                sb.append(",");
            }
            if(size > 0){
        
                sb.append(elementData[size-1]);
            }
            sb.append("]");
            return sb.toString();
        }
    
        private class ListItr<E> implements ListIterator<E> {
        
            private int cursor = -1;
    
            private ListItr(int cursor) {
        
                this.cursor = cursor;
            }
    
            private ListItr() {
        
            }
    
            @Override
            public boolean hasNext() {
        
                return cursor+1 < size;
            }
    
            @SuppressWarnings("unchecked")
            @Override
            public E next() {
        
                cursor++;
                return (E) elementData[cursor];
            }
    
            @Override
            public boolean hasPrevious() {
        
                return cursor > -1;
            }
    
            @SuppressWarnings("unchecked")
            @Override
            public E previous() {
        
                cursor--;
                return (E) elementData[cursor];
            }
    
            @Override
            public int nextIndex() {
        
                return cursor+1;
            }
    
            @Override
            public int previousIndex() {
        
                return cursor -1 ;
            }
    
            @Override
            public void remove() {
        
    
            }
    
            @Override
            public void set(E e) {
        
    
            }
    
            @Override
            public void add(E e) {
        
    
            }
        }
    }