手写ArrayList简单实现其主要功能
package test;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* @author wcy
*手写ArrayList(泛型)
*要求：
*add()
*remove()
*get()
*set()
*size()
*iterator()
*contain()
*clear()
*/
public class ArrayListTest<T> {
//默认容量为10
private static final int DEFAULT_CAPACITY = 10;
/**
* 用elementData数组存储书库，ArrayList的容量就是该数组的长度
*/
Object[] elementData ;
/**
* 一个空数组
* 用户使用有参构造函数指定长度为0时返回该数组
*/
private static final Object[] EMPTY_ELEMRNTDATA = {};
/**
* 一个空的数组实例
* 当用户构造空的ArrayList时(调用无参构造函数)，返回该数组。
* 注意和EMPTY_ELEMRNTDATA的区别
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_elementData = {};
//ArrayList实际存储数量
private int size;
/**
* 无参构造函数
* 创建一个空的ArrayList,此时其内数组缓冲区 elementData = {}，长度为0
* 当元素第一次被加入时，扩容至默认容量10
*/
public ArrayListTest() {
this.elementData = DEFAULTCAPACITY_EMPTY_elementData;
}
/**
* 有参构造函数（参数为数字（初始值））
* @param initialCapacity 设置的初始容量
* @throws IllegalArgumentException 若初始值小于0，抛出
*/
public ArrayListTest(int initialCapacity) {
if(initialCapacity>0) {
this.elementData = new Object[initialCapacity];
}else if(initialCapacity == 0) {
this.elementData = EMPTY_ELEMRNTDATA;
}else{
throw new IllegalArgumentException("错误初始值，初始值必须大于1");
}
}
/**
* 有参构造函数（参数为集合）
* @param c 要放入ArrayList中的集合，其中的元素会全部添加到新建的ArrayList实例中
*/
public ArrayListTest(Collection<? extends T> c) {
//将集合转换为Object数组
elementData = c.toArray();
//吧转换后的数组的长度赋值给当前ArrayList的size，并判断是否为0
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 这句话意思是：c.toArray 可能不会返回 Object[]，可以查看 java 官方编号为 6260652 的 bug
if (elementData.getClass() != Object[].class)
// 若 c.toArray() 返回的数组类型不是 Object[]，则利用 Arrays.copyOf(); 来构造一个大小为 size 的 Object[] 数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 替换空数组
this.elementData = EMPTY_ELEMRNTDATA;
}
}
/**
* 数组缓冲区最大存储容量
* 为什么减去8？-->一些VM会在一个数组中存储某些数据
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容方法
* 确保ArrayList至少能存储minCapacity个元素
* 扩容公式：新容量 = 旧容量 + （旧容量>>1）；即相当于扩充为当前的1.5倍
* @param minCapacity 指定的最小容量
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >>1);
if(newCapacity < minCapacity) {
newCapacity = minCapacity;
}
if(newCapacity>MAX_ARRAY_SIZE) {
newCapacity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 大容量分配，最大分配Integer.MAX_VALUE
* @param minCapacity
*/
private static int hugeCapacity(int minCapacity) {
if(minCapacity <0) {
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
}
/**
* 保证ArrayList的容量足够add()函数添加元素
* @param minCapacity
*/
private void ensureCapacityInternal(int minCapacity) {
if(elementData == DEFAULTCAPACITY_EMPTY_elementData) {
minCapacity = Math.max(minCapacity, DEFAULT_CAPACITY);
}
if(minCapacity > elementData.length) {
grow(minCapacity);
}
}
/**
* size() 发牛ArrayList实际存储的元素数量
*/
public int size() {
return size;
}
/**
* 判断ArrayList是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 判断ArrayList是否半酣某个元素
*/
public boolean contains(Object o) {
return indexOf(o)>=0;
}
/**
* indexOf(Object o)
* @return 存在？ 最低索引值：-1
*/
public int indexOf(Object o) {
if(o == null) {
for(int i = 0;i<size;i++) {
if(elementData[i] == null) {
return i;
}
}
}else {
for(int i = 0;i < size;i++) {
if(o.equals(elementData[i])) {
return i;
}
}
}
return -1;
}
/**
* get()函数
* @param index
* @return 返回指定位置上的元素（从零开始）
*/
public T get (int index) {
rangeCheck(index);
return (T) elementData[index];
}
/**
* set(int index，T element) 函数,设置elementData[index]的值为element
* @param index
* @param element
* @return 先前位于指定位置的元素
*/
public T set (int index,T element) {
rangeCheck(index);
T oldValue = (T) elementData[index];
elementData[index] = element;
return oldValue;
}
/**
* 检查索引是否越界，若越界则抛出异常
* IndexOutOfBoundsException（String s）方法打印字符串
*/
public void rangeCheck(int index) {
if(index>=size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
/**
*
* @param index
* @return 返回一个字符串，表明所求索引和实际大小
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 添加某个元素到arraylist的末尾
* @param e
* @return
*/
public boolean add(T e) {
ensureCapacityInternal(size+1);
elementData[size++] = e;
return true;
}
public void add (int index,T element) {
rangeCheck(index);
//保证容量足够大
ensureCapacityInternal(size+1);
//将index位置及其之后所有元素向后移动一位
//arraycopy函数，第一个参数为要复制的数组，第二个为开始复制的下标，第三个为复制到哪个数组，第四个为复制到数组的什么位置开始，最后一个参数是复制数组的长度
System.arraycopy(elementData, index, elementData, index+1, size-index);
//在空出来的位置上添加需要添加的值
elementData[index] = element;
//size属性+1
size++;
}
/**
* 按下表索引移除元素
* @param index
*/
public void remove (int index) {
rangeCheck(index);
int numMoved = size -index -1;
if(numMoved > 0) {
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
//将最后一个元素置空
elementData[--size] = null;
}
/**
* 按照数组中第一个o元素
* @param o
* @return
*/
public boolean remove (Object o) {
if(o == null) {
for(int i = 0;i<size;i++) {
if(elementData[i] == null) {
remove(i);
return true;
}
}
}else {
for(int i = 0;i<size;i++) {
if(o.equals(elementData[i])) {
remove(i);
return true;
}
}
}
return false;
}
/**
* 清空ArrayList中的所有元素
*/
public void clear() {
for(int i = 0;i<size;i++) {
elementData[i] = null;
}
size = 0;
}
public Iterator<T> iterator(){
return new Itr();
}
private class Itr implements Iterator<T>{
int cursor; // 光标，默认为0，为下个元素的索引
int lastRet = -1; // 最后一个元素的索引
/**
* 查询是否有下一个元素
*/
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return cursor!=size;
}
/**
* 返回下一个元素
*/
@Override
public T next() {
// TODO Auto-generated method stub
int i = cursor;
if(i>=size) {
throw new NoSuchElementException();
}
if(i>= elementData.length) {
throw new ConcurrentModificationException();
}
cursor = i+1;
//给lastRet赋值
return (T) elementData[lastRet = i];
}
//需要和next配合使用
public void remove() {
if(lastRet<0) {
throw new IllegalStateException();
}
try {
//移除最后一个元素
ArrayListTest.this.remove(lastRet);
//cursor比lastRet大1，所以指针往前移动一位
cursor = lastRet;
//将lastRet重新设为-1
lastRet = -1;
}catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
}
//测试
public static void main(String[] args) {
ArrayListTest<Integer> a = new ArrayListTest<>();
a.add(1);
a.add(2);
a.add(3);
// a.add("测试");
// System.out.println("size"+"="+a.size);
// for(int i = 0;i<a.size;i++) {
// System.out.println(a.get(i));
// }
// System.out.println("--------");
// a.remove(0);
// System.out.println("size"+"="+a.size);
// for(int i = 0;i<a.size;i++) {
// System.out.println(a.get(i));
// }
// System.out.println("--------");
// a.set(0, 1);
// for(int i = 0;i<a.size;i++) {i
// System.out.println(a.get(i));
// }
Iterator<Integer> itr = a.iterator();
while(itr.hasNext()) {
System.out.println(itr.next());
}
}
}
实现栈
package test;
/**
* 用自己写的ArrayList实现栈
* @author wcy
*pop()
*push (Object o)
*isEmpty()
*getStackSize()
*/
public class StackTest {
private ArrayListTest list= new ArrayListTest<>() ;
//压栈
public void push (Object o) {
System.out.println("进栈元素为:"+o);
list.add(o);
}
//检查栈是否为空
public boolean isEmpty() {
return list.isEmpty();
}
//出栈
public void pop() {
Object obj = null;
if(list.isEmpty()) {
return;
}else {
obj = list.get(list.size()-1);
System.out.println("出栈的元素为:"+obj);
list.remove(obj);
}
}
//返回栈中元素数量
public int getStackSize() {
return list.size();
}
public static void main(String[] args) {
StackTest stack = new StackTest();
stack.push(1);
stack.push("df");
stack.push(3);
System.out.println(stack.getStackSize());
stack.pop();
stack.pop();
}
}
京公网安备 11010502036488号