List接口
首先我们需要定义所有需要的方法，比如添删该查等
public interface List<E> {
/**
* 返回线性表的大小，即数据的元素
*/
int size();
/**
* 根据索引获得数据元素
*/
E get(int index);
/**
* 线性表是否为空
*/
boolean isEmpty();
/**
* 线性表是否包含元素
*/
boolean contains(Object o);
/**
* 返回数据元素e在线性表中的序列号
*/
int indexOf(Object o);
/**
* 将数据元素E添加到线性表末尾
*/
boolean add(E e);
/**
* 添加到指定的位置
*/
void add(int index, E element);
/**
* 将e添加到元素obj之前
*/
void addBefore(E obj, E e);
/**
* 将e添加到元素obj之后
*/
void addAfter(E obj, E e);
/**
* 删除序列号index位置的元素
*/
E remove(int index);
/**
* 删除线性表中第一个和e相同的元素
*/
boolean removeValue(Object e);
/**
* 替换线性表中index中的元素e
*/
E set(int index, E element);
/**
* 清空数组
*/
void clear();
}
实现ArrayList
- 首先我们需要参数。一个数组和这个数组的大小
private Object[] elementData;
//元素的个数
private int size;
这时候，我们会发现数组没有初始化，我们可以用构造函数对其进行初始化,这里我为了方便测试(懒)，我设置数组的大小是4
//返回默认的数组
public ArrayList() {
//默认初始化4个数组
this(4);
}
public ArrayList(int initialCapacity) {
//给数组分配空间
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else {
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
有几个方法特别简单，就不阐述了，直接贴代码
@Override
public int size() {
return size;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Array index is out of bounds");
}
return (E) elementData[index];
}
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 改变索引index值,并返回旧值
*/
@Override
public E set(int index, E element) {
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
添加元素到线性表的最后
- 这里需要考虑的一个就是数组的扩容问题，首先我们什么时候进行数组的扩容，比如，我当前数组的大小size是4，当前数组的长度lenght也是4，这时候我们添加数据的时候size就是5了，这时候数组的长度4肯定不够,就需要扩容。
- 那么扩容多少？Java中提供的是增长50%
- 怎么扩容呢？简单点来说就是new一个数组，其大小是原本数组的大小+原本的数组的大小/2,然后将原本的数据拷贝进去，你可以for循环，这里可以调用Java提供了一个Arrays.copyOf方法，有两个参数，第一个参数返回新的数组，第二参数新数组的长度
/**
* 扩容
*/
private void grow(int minCapacity) {
//判断下个添加的时候位置够不够,不够就进行扩容
if (minCapacity > elementData.length) {
//获取旧数组的长度
int oldCapacity = elementData.length;
//指定新数组的长度=旧数组的长度+旧数组的长度的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
//将旧的数组拷贝到新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
回到刚才添加方法，首先第一步我们需要判断添加一个参数之后的大小，是否需要扩容，之后给数组的最后一个位置设置值，然后对size进行加1
/**
* 将数据元素e添加到线性表末
*/
@Override
public boolean add(E e) {
grow(size + 1);
elementData[size++] = e;
System.out.println("elementData length is:" + elementData.length);
return true;
}`
-
添加值到指定的位置
这里需要弄清楚如何添加
image.png
首先我们需要将要被添加的索引的位置之后的所有值往后移动一位，随后要被添加位置就会被空出来，然后重新设值进去。这里我们使用Java中的 System.arraycopy方法,其源码如下
public static native void arraycopy(Object var0, int var1, Object var2, int var3, int var4);
第一个参数：原数组
第二个参数：从原数组什么位置开始复制
第三个参数：新数组
第四个参数：从新数组什么位置开始拷贝
第五个参数：旧数组要拷贝的长度
@Override
public void add(int index, E element) {
//判断是否需要扩容
grow(size + 1);
//从elementData数据index位置开始到size-index的所有数据拷贝到elementData的index+1开始到最后的位置
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
//size一定要记得++
size++;
}
将e添加到元素obj之前
在此之前需要判断元素obj是否存在并获得它的下标
@Override
public boolean contains(Object o) {
return indexOf(o) > -1;
}
/**
* 返回数据元素e在线性表中的序列号
*/
@Override
public int indexOf(Object o) {
if (o == null) {
//可能添加了空数据
for (int i = 0; i < size; i++) {
if (elementData[i] == null) {
return i;
}
}
} else {
//进行for循环
for (int i = 0; i < size; i++) {
if (elementData[i] == o) {
return i;
}
}
}
return -1;
}
首先判断需不需要扩容，第二步，判断是否含有obj元素，若有则获取其的下标，然后和add一样的思路
/**
* 将e添加到元素obj之前
*/
@Override
public void addBefore(E obj, E e) {
grow(size + 1);
if (contains(obj)) {
//首先找到obj的下标
int index = indexOf(obj);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = e;
size++;
} else {
//如果obj不存在，e就默认添加第一个位置
add(0, e);
size++;
}
}
将e添加到元素obj之后
/**
* 将e添加到元素obj之后
*/
@Override
public void addAfter(E obj, E e) {
grow(size + 1);
if (contains(obj)) {
//首先找到obj的下标
int index = indexOf(obj);
System.arraycopy(elementData, index + 1, elementData, index + 2, size - index - 1);
elementData[index + 1] = e;
size++;
} else {
//如果obj不存在，e就默认添加最后一个位置
add(e);
size++;
}
}
删除序列号index位置的元素,并返回旧值
image.png
@Override
public E remove(int index) {
E oldValue = (E) elementData[index];
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
//最后一个位置的数据设置为空
elementData[--size] = null;
return oldValue;
}
删除元素e
@Override
public boolean removeValue(Object e) {
for (int index = 0; index < size; index++) {
if (e.equals(elementData[index])) {
remove(index);
return true;
}
}
return false;
}
