Java数据结构和算法(1)--自定义一个数组类和动态数组类

前言

今天就要离校了,大学生涯也走到了尽头。肯定有很多不舍,不舍的是学校的安逸和美丽的女友。同时也对自己的未来充满着信心,希望自己能够强大起来,保护自己想要保护的人。之前一段时间,在掘金上面看到一篇文章,文章提到了一个思想:学会编程,而不是学会Java,文中提到了自定义一个模仿ArrayList的类,要去实现其中的add,get,remove等方法。同时正好我之前也在看《Java数据结构和算法》这本书,文中第二章也详细讲解了数组,所以自己也动手完成了自定义一个数组内和动态数组类,于是乎就有了这篇文章去温故而知新。


数组

数组是应用最广泛的数组存储结构。 优点:插入快,如果知道下标,可以非常地存取 缺点:查找慢,删除慢,大小固定。


动态数组

Java也提供了顺序结构的动态数组类ArrayList<E>,数组采用的是顺序结构来存储数据,可以有效利用空间,可用于存储大量的数据,数组不适合动态的改变它所存储的数据,如增加,删除一个单元等。由于数组采用顺序结构存储数据,数组获得第n单元中的数据的速度要比链表获得第n单元中的数据快。

写一个数组类

这个数组类肯定有insert(),find(),delete(),display()这些基础方法。 insert():插入一个元素,然后数组长度+1,返回true。

    public void insert(long value){
        a[count]=value;
        count++;
    }

find():根据元素的值,遍历整个数组的元素,找到返回true,没有找到返回false

public boolean find(long searchValue){
        int j;
        
        for(j=0;j<count;j++){
            
            if(a[j]==searchValue){
                break;
            }
        }
        
        if(j==count){
            return false;
        }else{
            return true;
        }
    }

delete():根据元素的值,遍历整个数组的元素,没有找到对应的元素值,返回flase, 找到了该元素存储在数组的位置,让该位置后面的所有元素向前移动一个位置,返回true。

    public boolean delete(long deleteValue){
        
        int j;
        for(j=0;j<count;j++){
            
            if(a[j]==deleteValue){
                
                break;
            }
            
        }
        
        if(j==count){
            
            return false;
        }else{
            
            for(int k=j;k<count;k++){
                
                a[k]=a[k+1];
            }
            
            count--;
            return true;
        }
    }

display():遍历整个数组的元素,打印数组。

    public void display(){
        int j;
        for(j=0;j<count;j++){
            System.out.print(a[j]+" ");
        }
        System.out.print("\n");
        
    }

写一个简单的动态数组类

其实这还是比较难的,但是看了一下ArrayList<E>的源码后,写一个带有基本功能的类还是没有问题的。基本方法:add(),remove(),contain(),toString(),toArray(),removeRange(),get()等。

首先是构造器,有2个构造器,分别一个是有参和无参的。有参的构造器需要传入的参数是所需初始化数组的容量大小,如果这个容量大小>0,那么创建一个数组,数组容量大小为传入的参数。如果这个容量大小=0,那么把EMPTY_ELEMENTDATA这个空数组对象赋给elementData这个数组变量。如果这个容器大小<0,那么抛出参数异常。对于无参构造器而言,直接把elementData数组变量引用这个DEFAULT_CAPACITY_ELEMENTDATA数组对象。

public CmazList1(int inititalCapcacity){
        
        if(inititalCapcacity>0){
            
            this.elementData=new Object[inititalCapcacity];
            
        }else if(inititalCapcacity==0){
            this.elementData=EMPTY_ELEMENTDATA;
        }else{
            
            throw new IllegalArgumentException("参数错误");
        }
    }
    
    public CmazList1(){
        
        this.elementData=DEFAULT_CAPACITY_ELEMENTDATA;
    }

contain():调用indexOf()方法,如果indexOf返回的int值大于0就说明此对象在数组中找到对应存储的位置,那么返回true,否则返回false。

public boolean contain(Object object){
        
        return indexOf(object)>=0;
    }

indexOf():通过遍历整个数组元素,判断该数组的某个单元是否包含这个对象,如果找到了这个对象,返回其存储在数组的下标,否则返回-1。

public int indexOf(Object object){
        
        if(object==null){
            
            for(int i=0;i<size;i++){
                
                if(elementData[i]==null){
                    
                    return i;
                }
            }
        }else{
            
            for(int i=0;i<size;i++){
                
                if(elementData[i].equals(object)){
                    
                    return i;
                    
                }
            }
        }
        
        return -1;
    }

add():先调用 ensureCapacityInternal()方法,进行相关扩容等处理操作。然后添加元素,size加1。size用于记录在数组中元素的个数。

public  boolean  add(Object object){
        
        ensureCapacityInternal(size+1);
        
        elementData[size++]=object;
        
        return true;
    }

ensureCapacityInternal():首先看整个英文的意思是确保内部容量。首先要判断这个数组是哪一个构造器初始化的。如果这个数组是无参构造器初始化的,那么这个数组肯定没有设置初始化数组的容量大小,是一个空数组。然后把minCapacity的值在传入的minCapacity的值和默认容器大小的值中取出最大的一个值,即为minCapacity的值。然后调用ensureExplicitCapacity()

private void ensureCapacityInternal(int minCapacity){
        
        
        if(this.elementData==DEFAULT_CAPACITY_ELEMENTDATA){
            
            minCapacity=Math.max(minCapacity, DEFAULT_CAPACITY);
        }
        
        ensureExplicitCapacity(minCapacity);
    }

ensureExplicitCapacity():这个方法进行的操作,去判断是否要进行扩容。如果minCapacity大于数组的长度,说明这个数组需要进行扩容了,因为数组的空间容不下即将添加的元素。接下来调用grow()去进行扩容。

private void ensureExplicitCapacity(int minCapacity){
        
        modCount++;
        
        if(minCapacity-elementData.length>0){
            
            grow(minCapacity);
        }
    }

grow():进行扩容的操作,扩容后的大小是原来大小的1.5倍。>>1是右移1位,移动后的值是移动前的值的0.5倍。如果扩容后的大小比minCapacity小,那么就把minCapacity的值赋给newCapacity。如果newCapacity的值比我们之前定义的MAX_ARRAY_SIZE还要大的话,那么就调用hugeCapacity()方法。MAX_ARRAY_SIZE我们定义的大小是Integer.MAX_VALUE-8,也就是Integer型数值的最大值-8。补充:原码是直接将一个数值换算成二进制数,但计算机以补码的形式保存所有的整数。一般情况下,不会出现newCapacity>MAX_ARRAY_SIZE的情况。

private void grow(int minCapacity){
        
        int oldCapacity=elementData.length;
        
        int newCapacity=oldCapacity+(oldCapacity>>1);
        
        if(minCapacity-newCapacity>0){
            
            newCapacity=minCapacity;
        }
        
        if(newCapacity-MAX_ARRAY_SIZE>0){
            
            newCapacity=hugeCapacity(minCapacity);
        }
        
        this.elementData=Arrays.copyOf(elementData,newCapacity);
    }

remove():遍历整个数组元素,如果发现该数组包含这个对象,那么调用fastRemove()删除存储此对象的单元。

public boolean  remove(Object object){
        
        if(object==null){
            
            for(int i=0;i<size;i++){
                
                if(elementData[i]==null){
                    
                    fastRemove(i);
                    return true;
                }
            }
        }else{
            
            for(int i=0;i<size;i++){
                
                if(elementData[i].equals(object)){
                    fastRemove(i);      
                    return true;
                }
            }
        }
        
        return false;
        
    }

remove():首先调用get()方法,通过下标得到此单元存储的元素值。这个方法返回就是这个元素值。计算出删除此元素需要挪动的元素个数。如果挪动的元素个数>0,那么调用System.arraycopy()方法,得到一个移动后的数组。elementData[--size]=null,移动后的数组剩余一个存储没有任何元素的单元,那么size--,把没有存储任何元素的单元置为null,通知GC清除无用的内存。 讲解:System.arraycopy(src, srcPos, dest, destPos, length) src:源数组 srcPos:源数组要复制元素的起始位置 dest:目的数组 destPos:目的数组把复制的元素放置的起始位置 length:复制元素的长度

public E remove(int index){
        rangeCheck(index);
        modCount++;
        E oldValue=get(index);
        int movedNum=size-1-index;
        
        if(movedNum>0){
            
            System.arraycopy(elementData,index+1, elementData, index, movedNum);
        }
        
        elementData[--size]=null;
        
        return oldValue;
    }

removeRange():需要注意的是toIndex指的是要删除的最后一个元素的下一个元素的下标。思路和remove()是一样的,只是remove()是删除一个元素,removeRange()删除的是多个元素。

public void removeRange(int fromIndex,int toIndex){
        
        modCount++;
        
//      int movedNum=size-1-(toIndex-1);
        int movedNum=size-toIndex;
        
        if(movedNum>0){
            
            System.arraycopy(elementData, toIndex, elementData, fromIndex, movedNum);
        }

        int newSize=size+fromIndex-toIndex;
        
        for(int i=newSize;i<size;i++){
            
            elementData[newSize]=null;
        }
        
        size=newSize;
        
    }

源码附上

public class CmazList1<E> {
    
    private static final Object[] DEFAULT_CAPACITY_ELEMENTDATA={};
    
    private static final Object[] EMPTY_ELEMENTDATA={};
    
    private static final int MAX_ARRAY_SIZE=Integer.MAX_VALUE-8;
    
    private static int DEFAULT_CAPACITY=10;
    
    private Object[] elementData;
    
    private int modCount=0;
    
    private int size;
    
    public CmazList1(int inititalCapcacity){
        
        if(inititalCapcacity>0){
            
            this.elementData=new Object[inititalCapcacity];
            
        }else if(inititalCapcacity==0){
            this.elementData=EMPTY_ELEMENTDATA;
        }else{
            
            throw new IllegalArgumentException("参数错误");
        }
    }
    
    public CmazList1(){
        this.elementData=DEFAULT_CAPACITY_ELEMENTDATA;
    }
    
    public boolean contain(Object object){
        
        return indexOf(object)>=0;
    }
    
    public int indexOf(Object object){
        
        if(object==null){
            
            for(int i=0;i<size;i++){
                
                if(elementData[i]==null){
                    
                    return i;
                }
            }
        }else{
            
            for(int i=0;i<size;i++){
                
                if(elementData[i].equals(object)){
                    
                    return i;
                    
                }
            }
        }
        
        return -1;
    }
    
    public  boolean  add(Object object){
        
        ensureCapacityInternal(size+1);
        
        elementData[size++]=object;
        
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity){
        
        
        if(this.elementData==DEFAULT_CAPACITY_ELEMENTDATA){
            
            minCapacity=Math.max(minCapacity, DEFAULT_CAPACITY);
        }
        
        ensureExplicitCapacity(minCapacity);
    }
    
    
    private void ensureExplicitCapacity(int minCapacity){
        
        modCount++;
        
        if(minCapacity-elementData.length>0){
            
            grow(minCapacity);
        }
    }
    
    private void grow(int minCapacity){
        
        int oldCapacity=elementData.length;
        
        int newCapacity=oldCapacity+(oldCapacity>>1);
        
        if(minCapacity-newCapacity>0){
            
            newCapacity=minCapacity;
        }
        
        if(newCapacity-MAX_ARRAY_SIZE>0){
            
            newCapacity=hugeCapacity(minCapacity);
        }
        
        this.elementData=Arrays.copyOf(elementData,newCapacity);
    }
    
    private int hugeCapacity(int minCapacity){
        
        if(minCapacity<0){
            
            throw new OutOfMemoryError();
        }
        return minCapacity>MAX_ARRAY_SIZE?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
    }
    
    public boolean  remove(Object object){
        
        if(object==null){
            
            for(int i=0;i<size;i++){
                
                if(elementData[i]==null){
                    
                    fastRemove(i);
                    return true;
                }
            }
        }else{
            
            for(int i=0;i<size;i++){
                
                if(elementData[i].equals(object)){
                    fastRemove(i);      
                    return true;
                }
            }
        }
        
        return false;
        
    }
    
    
    private  void fastRemove(int index){
        modCount++;
        int movedNum=size-1-index;
        if(movedNum>0){
        
            System.arraycopy(elementData, index+1, elementData, index, movedNum);
        }
        
        elementData[--size]=null;
        
    }
    
    public E remove(int index){
        rangeCheck(index);
        modCount++;
        E oldValue=get(index);
        int movedNum=size-1-index;
        
        if(movedNum>0){
            
            System.arraycopy(elementData,index+1, elementData, index, movedNum);
        }
        
        elementData[--size]=null;
        
        return oldValue;
    }
    
    public E get(int index){
        rangeCheck(index);
        return (E) elementData[index];
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<size;i++){
            sb.append(elementData[i]+" ");
        }
        return sb.toString();
    }
    
    public Object[] toArray(){
        
        return Arrays.copyOf(this.elementData, size);
    }
    
    /**
     * toIndex是指要删除的最后一个元素的下一个元素的下标
     * 比如我要删除下标为5的元素,那么toIndex=6
     * @param fromIndex
     * @param toIndex
     */
    public void removeRange(int fromIndex,int toIndex){
        
        modCount++;
        
//      int movedNum=size-1-(toIndex-1);
        int movedNum=size-toIndex;
        
        if(movedNum>0){
            
            System.arraycopy(elementData, toIndex, elementData, fromIndex, movedNum);
        }
//      
        int newSize=size+fromIndex-toIndex;
        
        for(int i=newSize;i<size;i++){
            
            elementData[newSize]=null;
        }
        
        size=newSize;
        
    }
    
    private  void rangeCheck(int index){
        
        if(index>=size||index<0){
            
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }
    
    
    private String outOfBoundsMsg(int index){
        return "index:"+index+",size="+size;
    }
}

尾言

数据结构和算法的复利性远比其他时髦技术要多的多。对于程序员来说,不进则死。 打好牢固的基础,一定是没有错的。笨鸟先飞,很适合我。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

3596
来自专栏Java后端技术

一道面试题引发的思考

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

660
来自专栏java小白

ArrayList源码详解

1685
来自专栏用户画像

6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

861
来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

1121
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

1033
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

982
来自专栏我就是马云飞

ArrayList到底是什么?

ArrayList是日常开发中使用最频繁的集合类。首先这边简单介绍一下ArrayList:

1222
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——ArrayList

874
来自专栏武培轩的专栏

ArrayList源码解析(JDK1.8)

1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 imp...

2945

扫码关注云+社区