当前位置:首页 > 服务端 > 实现Java中的ArrayList

实现Java中的ArrayList

最近深受轮子哥影响,觉得造一些轮子应该会对自己的技术功底有一定的帮助,就决定先从简单的容器开始实现。废话不多说,就先实现一个Java中的ArrayList。

ArrayList是我们在Java中使用非常多的一个类,它是顺序表的数组实现,LinkedList是顺序表的链式实现(自己编的名字,懂就好哈),还有个Vector,它与ArrayList比较像,区别是它是线程安全的。

顺序表应该都有相同的操作,所以我先定义一个接口,描述好顺序表需要哪些操作。代码如下:

public interface KIList<T> {
    
    public void add(T item);
    public void add(int index, T item);
    public void set(int index, T item);
    public void remove(int index);
    public void remove(T item);
    public void clear();
    
    public boolean contains(T item);
    public boolean isEmpty();
    
    public T get(int index);
    
    public int indexOf(T item);
    public int size();
}

这些方法的作用,看见方法名就应该可以明白其意义了,因此不必多说了。接下来就开始着手实现吧。

第一步:初始化

首先我们需要一个构造方法,空参数的构造方法,因为是ArrayList是数组实现的顺序表,因此我们需要在一开始就给ArrayList分配一个容量大小。因此构造方法中就需要初始化一个固定大小的数组。于是就有了下面这部分代码。

public class KArrayList<T> implements KIList<T>{
    
    /** 初始化的容量的大小 */
    private final static int INIT_CAPACITY = 12;
    private Object[] mList = null;
    
    /** 当前的容量 */
    private int mCurrentCapacity = 0;
    /** 容器中元素的个数 */
    private int mSize = 0;
    
    public KArrayList() {
        mList = new Object[INIT_CAPACITY];
        mCurrentCapacity = INIT_CAPACITY;
    }
}

首先我定义了一个常量INIT_CAPACITY为12,这个12是看得Java里面的源码,好像原本这个12指的是容量自增的值。INIT_CAPACITY标明我们数组初始化的时候就在内存中开辟了一个多大的空间。

mList指的就是存数据的数组。

mCurrentCapacity指的是当前的容量。这个值并不是一层不变的,显然会随着数组放满的时候扩张一次。

mSize指的就是当前的数组中有效元素的个数了。初始化的值为0。

构造方法中,就直接new一个数组,然后把mCurrentCapacity设置一下就好了。

到这里为止我们就完成了第一步。

第二步:增加元素add

add操作有两个方法,一个是add(T),另一个是add(int, T)。它们的区别是,前者直接在顺序表的结尾插入一个元素,mSize自增1,后者是在指定的位置插入一个元素,指定位置的元素及其之后的元素向后移动一位,mSize自增1。可以画个图来表示。

实现Java中的ArrayList _ JavaClub全栈架构师技术笔记

上图表示的是add(T)的执行过程。

实现Java中的ArrayList _ JavaClub全栈架构师技术笔记

上图是add(int, T)的执行过程。

插入的过程中,需要考虑,当mSize == mCurrentCapacity的时候需要进行一次扩容,另外对于add(int, T),需要对第一个参数index进行判断。最终代码如下:

    /**
     * 插入一个元素到链表尾部
     * @param item
     * */
    @Override
    public void add(T item) {
        if (mSize == mCurrentCapacity) {
            expansion();
        }
        mList[mSize] = item;
        mSize++;
    }
    
    /**
     * 插入一个元素到指定位置,从插入位置及其后面的元素往后移动一个位置
     * @param index 要插入的位置
     * @param item
     * */
    @Override
    public void add(int index, T item) {
        if (index < 0 || index >= mSize) {    //不允许index小于0,或者index >= 数组当前大小
            throw new IndexOutOfBoundsException();
        }
        if (mSize == mCurrentCapacity) {
            expansion();
        }
        Object[] newList = new Object[mCurrentCapacity];
        System.arraycopy(mList, 0, newList, 0, index);
        System.arraycopy(mList, index, newList, index + 1, mSize - index);
        newList[index] = item;
        mList = newList;
        mSize++;
    }

需要注意的几个地方:

1.expansion()方法是自己写的扩容函数,代码如下:

    /**
     * 扩容,当 mSize == mCurrentCapacity 时调用
     * */
    private void expansion() {
        Object[] oldList = mList;
        Object[] newList = new Object[getNewCapacity()];
        System.arraycopy(oldList, 0, newList, 0, oldList.length);
        mList = newList;
    }
    
    /** 
     * 获取新的容量大小
     * 当满的时候每次增加当前容量的50%
     * */
    private int getNewCapacity() {
        return mCurrentCapacity = mCurrentCapacity + (mCurrentCapacity >> 1);
    }

2.注意System.arraycopy()方法,这个是Java提供的一个系统方法,作用就是对数组进行复制操作。

3.注意index的判断,如果越界需要抛出IndexOutOfBoundException。

到此为止,我们就完成了增加操作。

第三步:其他的方法

完成了增加方法后,其他的方法就比较简单或者类似了。直接贴代码就可以看懂了。(顺序表的数组实现本来就是相对比较简单的内容啦)

接下来就是整个类的全部代码。

package kross.java.util;

/**
 * 用数组实现的链表
 * @author krosshuang(krossford@foxmail.com)
 * @update 2014-9-26 18:36:50 第一次创建
 * @update 2014-09-28 17:12:46 测试完成
 * */
public class KArrayList<T> implements KIList<T>{
    
    /** 初始化的容量的大小 */
    private final static int INIT_CAPACITY = 12;
    private Object[] mList = null;
    
    /** 当前的容量 */
    private int mCurrentCapacity = 0;
    /** 容器中元素的个数 */
    private int mSize = 0;
    
    public KArrayList() {
        mList = new Object[INIT_CAPACITY];
        mCurrentCapacity = INIT_CAPACITY;
    }
    
    /**
     * 插入一个元素到链表尾部
     * @param item
     * */
    @Override
    public void add(T item) {
        if (mSize == mCurrentCapacity) {
            expansion();
        }
        mList[mSize] = item;
        mSize++;
    }
    
    /**
     * 插入一个元素到指定位置,从插入位置及其后面的元素往后移动一个位置
     * @param index 要插入的位置
     * @param item
     * */
    @Override
    public void add(int index, T item) {
        if (index < 0 || index >= mSize) {    //不允许index小于0,或者index >= 数组当前大小
            throw new IndexOutOfBoundsException();
        }
        if (mSize == mCurrentCapacity) {
            expansion();
        }
        Object[] newList = new Object[mCurrentCapacity];
        System.arraycopy(mList, 0, newList, 0, index);
        System.arraycopy(mList, index, newList, index + 1, mSize - index);
        newList[index] = item;
        mList = newList;
        mSize++;
    }
    
    /**
     * 更新指定位置的元素
     * @param index
     * @param item
     * */
    @Override
    public void set(int index, T item) {
        if (index < 0 || index >= mSize) {
            throw new IndexOutOfBoundsException();
        }
        mList[index] = item;
    }
    
    /**
     * 移除指定位置的元素,后面的元素向前移动一位
     * @param index
     * */
    @Override
    public void remove(int index) {
        if (index < 0 || index >= mSize) {
            throw new IndexOutOfBoundsException();
        }
        Object[] newList = new Object[mCurrentCapacity];
        System.arraycopy(mList, 0, newList, 0, index);
        System.arraycopy(mList, index + 1, newList, index, mSize - index);
        mList = newList;
        mSize--;
    }
    
    /**
     * 移除链表中特定的元素。(如果item在链表中有多个,只移除第一个)
     * @param item
     * */
    @Override
    public void remove(T item) {
        for (int i = 0; i < mSize; i++) {
            if (mList[i].equals(item)) {
                remove(i);
                break;
            }
        }
    }
    
    /**
     * 将链表清空,capacity不变
     * */
    @Override
    public void clear() {
        mList = new Object[mCurrentCapacity];
        mSize = 0;
    }
    
    /**
     * 判断是否包含某个元素
     * @param item
     * @return true表示有这个元素,false表示没有这个元素
     * */
    @Override
    public boolean contains(T item) {
        for (int i = 0; i < mSize; i++) {
            if (mList[i].equals(item)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断链表是否为空
     * @return boolean
     * */
    @Override
    public boolean isEmpty() {
        return (mSize == 0) ? true : false;
    }
    
    /**
     * 获取指定位置的元素
     * @param index
     * @return
     * */
    @SuppressWarnings("unchecked")
    @Override
    public T get(int index) {
        if (index < 0 || index >= mSize) {
            throw new IndexOutOfBoundsException();
        }
        return (T)mList[index];
    }
    
    /**
     * 获取特定元素所在的位置。
     * 如果该链表中存在多个相同的元素,只返回第一个的位置,如果找不到,则返回-1。
     * @param item
     * @return int 如果没找到,返回-1
     * */
    @Override
    public int indexOf(T item) {
        for (int i = 0; i < mSize; i++) {
            if (mList[i].equals(item)) {
                return i;
            }
        }
        return -1;
    }
    
    
    /**
     * 获取当前链表的长度
     * @return int
     * */
    @Override
    public int size() {
        return mSize;
    }

    /**
     * 扩容,当 mSize == mCurrentCapacity 时调用
     * */
    private void expansion() {
        Object[] oldList = mList;
        Object[] newList = new Object[getNewCapacity()];
        System.arraycopy(oldList, 0, newList, 0, oldList.length);
        mList = newList;
    }
    
    /** 
     * 获取新的容量大小
     * 当满的时候每次增加当前容量的50%
     * */
    private int getNewCapacity() {
        return mCurrentCapacity = mCurrentCapacity + (mCurrentCapacity >> 1);
    }
    
    public static void main(String[] args) {
        KArrayList<Integer> arr = new KArrayList<Integer>();
        
        for (int i = 1; i <= 50; i++) {
            arr.add(i);
        }
        
        arr.add(10, 99);
        arr.add(0, 99);
    
        System.out.println(arr.get(51));
        
        //arr.clear();
        
        //System.out.println(arr.contains(99));
        //System.out.println(arr.indexOf(59));
        
        arr.remove(11);
        
        arr = null;
    } 
}

另外,里面main方法是用来做测试的,我自己测的感觉没啥问题。

然后对比一下Java的源码,有一个比较大的困惑就是:

Java中它将数组对象前面加上了transient关键字,这个关键字的作用是:序列化的时候,不会将该字段序列化。也就是说,我在程序中创建了一个[1, 2, 3]的数组,序列化的时候不会序列化这些内容,从文件中反序列化的时候难道[1, 2, 3]就取不出来了吗?

不光是ArrayList,其他的几个容器,数据相关的属性都有这个声明。这一点是比较困惑。mark一下,以后搞明白了再更新上来。

 

 【更新】2014-10-07 17:43:52

关于transient关键字的作用,对于ArrayList来说,是使用数组来存储数据的,但实际的数据只有5个,也就是mSize=5,但数组实际的大小是7(假设),或者更大,那么如果要序列化的时候,就会把那两个空数据的也序列化,无疑就浪费了空间,实际上只有5个有效数据。所以增加了transient字段。而wirteObject方法会自动的将ArrayList中有效数据的部分进行序列化,这样就避免了取出来是null的情况。

 

原文地址:http://www.cnblogs.com/kross/p/4009446.html

作者:krosshuang
来源链接:https://www.cnblogs.com/kross/p/4009446.html

版权声明:
1、Java侠(https://www.javaxia.com)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。





本文链接:https://www.javaxia.com/server/125693.html

分享给朋友:

“实现Java中的ArrayList” 的相关文章