1、什么是数据结构
数据结构是计算机存储、组织数据的方式，数据结构分为线性结构、树形结构、图形结构。
- 线性表就是线性结构的，而数组、链表、栈、队列、都属于线性表，由于哈希表中用到了数组，所以哈希表也算是线性结构的。
- 二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集都属于树形结构。
- 邻接矩阵、邻接表属于图形结构。
本文主要讲下线性结构的数组。
2、数组
数组是一种顺序存储的线性表，所有内存地址都是连续的。
数组的定义如下：
int[] array=new int[] {11,22,33}
在内存中表示如下
image.png
上面数组中的元素是int型的，每个元素占4个字节，上面数组中有三个元素，所以在内存中申请了12个字节的内存空间，并且内存地址是连续的。
而且需要注意的是：数组一旦初始化后，容量就已经确定了，无法动态的修改其容量，但是在实际开发中我们想要的数组是可以修改容量，下面就来看下如何实现动态数组。
3、动态数组
设计动态数组前，先来看下向外提供哪些方法。
- int size(); //元素的数量
- boolean isEmpty()；//数组中元素是否为空
- boolean contains(E element)；//数组中是否包含某个元素
- void add(E element)；//添加元素到最后面
- void add(int index,E element)；//向index位置添加元素
- E get(int index)；//获取index位置的元素
- E set(int index,E element)；//设置index位置的元素
- E remove(int index)；//删除某个位置的元素
- E remove(E element)；//删除某个元素
- int indexOf(E element)；//获取某个元素的index
- clear()；//清空元素
public class ArrayList<E> {
/**
* @return 返回数组中元素的个数
*/
public int size() {
return 0;
}
/**
* @return 数组是否为空
*/
public boolean isEmpty() {
return false;
}
/**
* @param element
* @return 是否包含元素element
*/
public boolean contains(E element) {
return false;
}
/**
* 添加元素
*
* @param element
*/
public void add(E element) {
}
/**
* 向指定位置添加元素
*
* @param index
* @param element
*/
public void add(int index, E element) {
}
/**
* 获取指定位置的元素
*
* @param index
* @return
*/
public E get(int index) {
return null;
}
/**
* 设置index位置的元素
*
* @param index
* @param element
*/
public void set(int index, E element) {
}
/**
* 删除指定位置的元素
*
* @param index
* @return
*/
public E remove(int index) {
return null;
}
/**
* 删除元素
*
* @param element
* @return
*/
public E remove(E element) {
return null;
}
/**
* 返回指定元素的位置
* @param element
* @return
*/
public int indexOf(E element) {
return -1;
}
/**
* 清空元素
*/
public void clear() {
}
}
3.1、元素的添加
- 如果元素添加在数组尾部，则直接添加；
-
如果元素添加不在数组的尾部，则需要将数组的所有元素都向后移动一位，如果在头部添加则需要将数组中所有元素向后移动一位。
image.png
具体代码如下：
/**
* 添加元素
*
* @param element
*/
public void add(E element) {
// elements[size] = element;
// size++;
add(size, element);
}
/**
* 向指定位置添加元素
*
* @param index
* @param element
*/
public void add(int index, E element) {
checkIndexForAdd(index);
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size++;
}
private void checkIndexForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("index is " + index + " size is " + size);
}
3.2、删除元素
删除元素不同于添加，我们需要将数组中的元素向前移动。而且需要对最后一个元素进行处理。
image.png
具体代码如下：
/**
* 删除指定位置的元素
*
* @param index
* @return
*/
public E remove(int index) {
checkIndex(index);
E oldE = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
//如果数组中需要存入的数据类型为对象类型的，那么数组中存入的是对象的内存地址
//在删除元素时需要将元素向前移动，如果不将数组的最后一个元素置成null，那么它在
//下次被赋值之前都会一直引用这个对象，无法被垃圾回收。
elements[size - 1] = null;
size--;
return oldE;
}
这里需要注意的时，删除时的index的check不同于add()，在add()时，允许向index=size的位置添加元素，而删除时，并不能删除index=size的位置添加元素，很好理解，因为这个位置并没有元素。具体的代码如下：
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("index is " + index + " size is " + size);
}
删除元素还有一个方法未实现
/**
* 删除元素
*
* @param element
* @return
*/
public E remove(E element) {
return null;
}
这个方法需要用到indexOf()方法，这里先来实现一下
/**
* 返回指定元素的位置
*
* @param element
* @return 返回-1，表示未找到元素
*/
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
if (element == null) {
if (elements[i] == null)
return i;
} else {
if (element.equals(elements[i]))
return i;
}
}
return -1;
}
需要注意当查找的元素为null时，需要进行判断，否则会造成空指针异常。
有了indexOf()方法，我们就能通过该方法查找要删除元素的index，然后通过remove(int index)来删除元素了
/**
* 删除元素
*
* @param element
* @return
*/
public E remove(E element) {
return remove(indexOf(element));
}
3.3、其他方法的实现
/**
* @return 返回数组中元素的个数
*/
public int size() {
return size;
}
/**
* @return 数组是否为空
*/
public boolean isEmpty() {
return size==0;
}
/**
* @param element
* @return 是否包含元素element
*/
public boolean contains(E element) {
return indexOf(element)!=-1;
}
/**
* 获取指定位置的元素
*
* @param index
* @return
*/
public E get(int index) {
checkIndex(index);
return elements[index];
}
/**
* 设置index位置的元素
*
* @param index
* @param element
*/
public void set(int index, E element) {
checkIndex(index);
elements[index]=element;
}
3.4、clear()方法的实现
3.4.1、当动态数组中存入的是基本类型的数据时，数组在内存中的表示如下
以int型数组举例：
int[] array=new int[]{11,22,33,44,55,66,77};
image.png
通过new关键字创建长度为7的数组，会存放在堆空间中，变量array会存在栈空间中，并将数组在堆中的内存首地址赋值给变量array。
数组中存入的数据为基本类型数据时，我们在清空元素时直接将size=0即可实现元素清空的效果。
3.4.2、数组中存入对象数据
Object[] objects=new Object[7];
内存分配如下：
image.png
此时数组中存入的并不是对象本身，而是对象的内存地址，在执行清空元素时，需要将数组中的数据置成null，否则只把size置成0，在数组中元素被覆盖前对象会一直被引用，而不能被垃圾回收器回收。
注意：有的人可能会将objects=null，但是这样我们创建的数组就会被垃圾回收，下次使用的时候还要重新创建数组，对象的创建和销毁也是很耗资源的，而直接将size设置为0，虽然数组中存入之前的数据但是不能被访问的，在再次向其中添加数据时，会直接覆盖旧数据。
完整的代码如下
package com.ygj;
public class ArrayList<E> {
private int size;
private E[] elements;
private static final int DEFAULT_CAPACTITY = 10;
public ArrayList() {
this(DEFAULT_CAPACTITY);
}
public ArrayList(int capacity) {
if (capacity <= DEFAULT_CAPACTITY)
capacity = DEFAULT_CAPACTITY;
elements = (E[]) new Object[capacity];
}
/**
* @return 返回数组中元素的个数
*/
public int size() {
return size;
}
/**
* @return 数组是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* @param element
* @return 是否包含元素element
*/
public boolean contains(E element) {
return indexOf(element) != -1;
}
/**
* 添加元素
*
* @param element
*/
public void add(E element) {
// elements[size] = element;
// size++;
add(size, element);
}
/**
* 向指定位置添加元素
*
* @param index
* @param element
*/
public void add(int index, E element) {
checkIndexForAdd(index);
ensureCapacity(size);
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size++;
}
/**
* 扩容
*
* @param capactity
*/
private void ensureCapacity(int capactity) {
if (capactity >= elements.length) {
int newCapacity = capactity + (capactity >> 1);
System.out.println("扩容 oldCapactity:" + elements.length + " newCapacity:" + newCapacity);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
}
private void checkIndexForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("index is " + index + " size is " + size);
}
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("index is " + index + " size is " + size);
}
/**
* 获取指定位置的元素
*
* @param index
* @return
*/
public E get(int index) {
checkIndex(index);
return elements[index];
}
/**
* 设置index位置的元素
*
* @param index
* @param element
*/
public void set(int index, E element) {
checkIndex(index);
elements[index] = element;
}
/**
* 删除指定位置的元素
*
* @param index
* @return
*/
public E remove(int index) {
checkIndex(index);
E oldE = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
// 如果数组中需要存入的数据类型为对象类型的，那么数组中存入的是对象的内存地址
// 在删除元素时需要将元素向前移动，如果不将数组的最后一个元素置成null，那么它在
// 下次被赋值之前都会一直引用这个对象，无法被垃圾回收。
elements[size - 1] = null;
size--;
return oldE;
}
/**
* 删除元素
*
* @param element
* @return
*/
public E remove(E element) {
return remove(indexOf(element));
}
/**
* 返回指定元素的位置
*
* @param element
* @return 返回-1，表示未找到元素
*/
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
if (element == null) {
if (elements[i] == null)
return i;
} else {
if (element.equals(elements[i]))
return i;
}
}
return -1;
}
/**
* 清空元素
*/
public void clear() {
for (E e : elements)
e = null;
size = 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size=" + size + " capactity=" + elements.length + "[");
for (int i = 0; i < size; i++) {
sb.append(elements[i]);
if (i != size - 1)
sb.append(",");
}
sb.append("]");
return sb.toString();
}
}
