数据结构01-自定义ArrayList

54 阅读 0 评论 36 点赞

我是靠谱客的博主平淡菠萝，最近开发中收集的这篇文章主要介绍数据结构01-自定义ArrayList，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

闲话少叙，直接步入正题，接下来会手动实现一个低配版ArrayList，提供基本的增删改查等方法；

1.定义一个MyList接口，提供所需要实现的基本功能

package A01.LSQ;
public interface MyList<E>
{
// 新增数据
E add(E data);
// 插入数据
E add(int index, E data);
// 容器大小
int size();
// 根据下标取出数据
E get(int index);
// 根据下标删除数据
boolean remove(int index);
// 删除指定数据，如果有多个则删除下标最小的
boolean remove(E data);
// 修改数据
E set(int index, E data);
}

2.定义实现类

package A01.LSQ;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyArrayList<E> implements MyList<E>, Iterable<E>
{
// 保存数据的数组
private E[] arr;
// 数组长度
private int len;
// 线性表大小
private int size;
// 数组每次的增量
private final int addSize;
public MyArrayList()
{
this(10);
}
public MyArrayList(int len)
{
this(10, 10);
}
public MyArrayList(int len, int addSize)
{
this.len = len;
this.addSize = addSize;
arr = (E[]) new Object[len];
size = 0;
}
@Override
public E add(E data)
{
return add(size, data);
}
@Override
public E add(int index, E data)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("数组越界");
if (size == len)
{
addArrSize(len + addSize);
}
for (int i = size; i > index; i--)
{
arr[i] = arr[i - 1];
}
arr[index] = data;
size++;
return data;
}
@Override
public int size()
{
return size;
}
@Override
public E get(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界");
return arr[index];
}
@Override
public boolean remove(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界");
for (int i = index; i < size; i++)
{
arr[i] = arr[i + 1];
}
size--;
return true;
}
@Override
public boolean remove(E data)
{
for (int i = 0; i < size; i++)
{
if (data.equals(arr[i]))
{
return remove(i);
}
}
return false;
}
@Override
public E set(int index, E data)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界");
arr[index] = data;
return data;
}
public void addArrSize(int len)
{
E[] temp = (E[]) new Object[len];
for (int i = 0; i < size; i++)
{
temp[i] = arr[i];
}
arr = temp;
this.len = len;
}
// 实现增强for循环的内部类
@Override
public Iterator<E> iterator()
{
return new MyArrayListIterator();
}
private class MyArrayListIterator implements Iterator<E>
{
private int current = 0;
@Override
public void remove()
{
MyArrayList.this.remove(--current);
}
@Override
public boolean hasNext()
{
return current < size;
}
@Override
public E next()
{
if(!hasNext())
throw new NoSuchElementException();
return arr[current++];
}
}
}

至此，一个简单的自定义ArrayList已经基本实现了，与API中的相比，功能略显单一，性能略显差异，API中的数组拷贝使用底层的System.copy()方法，该方法是C语言实现的，效率高于Java语言。