自己实现ArrayList

思路：

一载体

ArrayList是一个集合容器，必然要有一个保存数据的载体。

public class MyArraylist {

    private final static int INIT_COUNT = 10;

    Object[] arrays;

    public MyArraylist() {

        this(INIT_COUNT);

    }

    public MyArraylist(int count) {

        arrays = new Object[count];

    }

}

二属性

长度

得到集合会初始化一个数组长度，集合的元素个数不能是数组长度。

public class MyArraylist2 {

    private int size;

    public int size(){

        return size;

    }

}

三方法

增删改查

增加

按默认索引加入元素，按索引加入元素，加入单个元素，加入批量元素。这里只举按单个加入元素的例子。

首先需要判断索引是否非法

public void checkIndexRange(int index) {

        if (index > size) {

            throw new IndexOutOfBoundsException("数组越界");

        }

    }

    public void checkIndexRangeForAdd(int index) {

        if (index > size || index < 0) {

            throw new IndexOutOfBoundsException("数组越界");

        }

}

判断当前数组是否需要扩容。如果索引大于当前数组长度，按当前长度的50%增加。并将当前数组复制到新的数组。

public void checkIndex(int index) {

        if (index > arrays.length) {

            int oldLength = size;

            int newLength = oldLength + (index >> 1);

            arrays = Arrays.copyOf(arrays, newLength);

        }

    }

增加单个元素

    public void add(Object obj, int index) {

        checkIndexRangeForAdd(index);//判断索引是否非法

        checkIndex(size + 1);//判断数组是否需要扩容

        System.arraycopy(arrays, index, arrays, index + 1, size - index);

        arrays[index] = obj;

        size++;

    }

    public boolean add(Object obj) {

        checkIndex(size + 1);//判断数组是否需要扩容

        arrays[size++] = obj;

        return true;

    }

获取元素

public T get(int index) {

        checkIndexRangeForAdd(index);

        return (T) arrays[index];

    }

更新元素

    public T set(Object obj, int index) {

        checkIndexRange(index);

        T t = (T) arrays[index];

        arrays[index] = obj;

        return t;

    }

删除元素

public T remove(int index) {

        checkIndexRange(index);

        T t = (T) arrays[index];

        int moveLength = size - index - 1;

        if (moveLength > 0) {

            System.arraycopy(arrays, index + 1, arrays, index, moveLength);

        }

        arrays[--size] = null;

        return t;

    }

四迭代

使用增强型for循环迭代输出，以及Java 8引进的lambda表达式实现foreach。

首先生成一个迭代器。

private class MyArrayListIterator implements Iterator<T> {

        private int count;

        public boolean hasNext() {

            return count != size;

        }

        public T next() {

            checkModcount();

            return (T) arrays[count++];

        } 

    }

然后继承Iterable接口。

public class MyArraylist2<T> implements Iterable<T>{

    @Override

    public Iterator<T> iterator() {

        return new MyArrayListIterator();

    }

}

五线程安全问题

ArrayList没有实现线程安全，但是在迭代的时候，不允许修改。

ArrayList使用一个成员变量modCount在迭代开始的时候记录ArrayList正在做修改(增加，修改，删除)的数量，然后在每迭代一行的时候，去比较modCount是否发生变化。如果发生变化，证明此刻有其它的线程或者就是本线程就对它进行修改，然后抛出异常。

定义modcount变量。

private transient int modcount;

在增加，修改，删除的时候，均需将此值加1。

public boolean add(Object obj) {

        checkIndex(size + 1);

        modcount++;//加1

        arrays[size++] = obj;

        return true;

    }

    public void checkIndex(int index) {

        if (index > arrays.length) {

            modcount++;//加1

            int oldLength = size;

            int newLength = oldLength + (index >> 1);

            arrays = Arrays.copyOf(arrays, newLength);

        }

    }

public T set(Object obj, int index) {

        checkIndexRange(index);

        modcount++;//加1

        T t = (T) arrays[index];

        arrays[index] = obj;

        return t;

    }

public T remove(int index) {

        checkIndexRange(index);

        modcount++;//加1

        @SuppressWarnings("unchecked")

        T t = (T) arrays[index];

        int moveLength = size - index - 1;

        if (moveLength > 0) {

            System.arraycopy(arrays, index + 1, arrays, index, moveLength);

        }

        arrays[--size] = null;

        return t;

    }

在迭代的时候，将此值赋给另一个变量exceptCount。然后再每迭代一行的时候，将exceptCount与modcount比较。

private class MyArrayListIterator implements Iterator<T> {

        private int exceptCount = modcount; 

        public void checkModcount() {

            if (exceptCount != modcount) {

                throw new ConcurrentModificationException();

            }

        }

    }

最后实现的全部代码

package com.skycomm.sdf;

import java.util.Arrays;

import java.util.ConcurrentModificationException;

import java.util.Iterator;

public class MyArraylist<T> implements Iterable<T> {

    private final static int INIT_COUNT = 10;

    private int size = 0;

    private transient int modcount;

    Object[] arrays;

    public MyArraylist() {

        this(INIT_COUNT);

    }

    public MyArraylist(int count) {

        arrays = new Object[count];

    }

    public void add(Object obj, int index) {

        checkIndexRangeForAdd(index);

        checkIndex(size + 1);

        System.arraycopy(arrays, index, arrays, index + 1, size - index);

        arrays[index] = obj;

        size++;

    }

    public boolean add(Object obj) {

        checkIndex(size + 1);

        modcount++;//加1

        arrays[size++] = obj;

        return true;

    }

    public void checkIndex(int index) {

        if (index > arrays.length) {

            modcount++;//加1

            int oldLength = size;

            int newLength = oldLength + (index >> 1);

            arrays = Arrays.copyOf(arrays, newLength);

        }

    }

    public T get(int index) {

        checkIndexRangeForAdd(index);

        return (T) arrays[index];

    }

    public T remove(int index) {

        checkIndexRange(index);

        modcount++;//加1

        @SuppressWarnings("unchecked")

        T t = (T) arrays[index];

        int moveLength = size - index - 1;

        if (moveLength > 0) {

            System.arraycopy(arrays, index + 1, arrays, index, moveLength);

        }

        arrays[--size] = null;

        return t;

    }

    public T set(Object obj, int index) {

        checkIndexRange(index);

        modcount++;//加1

        T t = (T) arrays[index];

        arrays[index] = obj;

        return t;

    }

    public void checkIndexRange(int index) {

        if (index > size) {

            throw new IndexOutOfBoundsException("数组越界");

        }

    }

    public void checkIndexRangeForAdd(int index) {

        if (index > size || index < 0) {

            throw new IndexOutOfBoundsException("数组越界");

        }

    }

    public int size() {

        return size;

    }

    public boolean isEmpty() {

        return size == 0;

    }

    public String toString() {

        Iterator<T> it = iterator();

        if (!it.hasNext())

            return "[]";

        StringBuilder sb = new StringBuilder();

        sb.append('[');

        for (;;) {

            T e = it.next();

            sb.append(e == this ? "(this Collection)" : e);

            if (!it.hasNext())

                return sb.append(']').toString();

            sb.append(',').append(' ');

        }

    }

    public Iterator<T> iterator() {

        return new MyArrayListIterator();

    }

    private class MyArrayListIterator implements Iterator<T> {

        private int count;

        private int exceptCount = modcount;

        public boolean hasNext() {

            return count != size;

        }

        public T next() {

            checkModcount();

            return (T) arrays[count++];

        }

        public void checkModcount() {

            if (exceptCount != modcount) {

                throw new ConcurrentModificationException();

            }

        }

    }

}

巴特西

自己实现ArrayList

最新文章

热门文章