数据结构与算法-基础（一）动态数组

2022-11-08 21:21:15

摘要

日常开发中，会经常创建数组，并使用数组的添加、删除等方法。现在就是要以数据结构的方式，来探究一下这些方法是怎么实现的。

本文结构先总结 Array 常用的 API，接下来由简单到复杂，由基础到组合思路实现，最后优化细节。你可以按照文章的顺序来梳理思路，去实现一下。

在文章的最后有完整的代码实现，你可以实现完了作为参考对照，或者不想看太多文字，直接跳到代码，自己去看代码理解也是可以的。

动态数组通俗些说就是可以无限的添加元素，不用考虑数组装不下的问题。其本质就是时刻监控数组中的剩余空间，及时的扩容和缩容，让数组动态的保持适当的容量大小。

数组的数据结构和对外的 API 函数，是在常见的基础上建立的，其中穿插着一些恰到好处的代码处理。不同的代码语言有不同的实现，但是数据结构是经历了几十年的检视，设计逻辑是可以套用到大部分代码语言上的。

Array 的常用 API

先来总结一下，日常使用 Array 的 API 大都逃不过下面代码块中罗列出的 11 个方法。

代码中的 E 就是泛型类型

/**
 * 清除所有元素
 */
public void clear()
/**
 * 元素的数量
 * @return
 */
public int size()
/**
 * 是否为空
 * @return
 */
public boolean isEmpty()
/**
 * 是否包含某个元素
 * @param element
 * @return
 */
public boolean contains(E element)
/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element)
/**
 * 获取index位置的元素
 * @param index
 * @return
 */
public E get(int index)
/**
 * 设置index位置的元素
 * @param index
 * @param element
 * @return 原来的元素ֵ
 */
public E set(int index, E element)
/**
 * 在index位置插入一个元素
 * @param index
 * @param element
 */
public void add(int index, E element)
/**
 * 删除index位置的元素
 * @param index
 * @return
 */
public E remove(int index)
/**
 * 删除元素
 * @param element
 */
public void remove(E element)
/**
 * 查看元素的索引
 * @param element
 * @return
 */
public int indexOf(E element)

数据结构

Array 的数据结构中主要包括构造函数、存放元素的成员变量、记录元素数量的成员变量等。

public class ArrayList<E> {
	/**
	 * 默认数组大小
	 */
	private static final int DEFAULT_CAPATICY = 10;
	
	/**
	 * 默认标示
	 */
	private static final int ELEMENT_NOT_FOUND = -1;
	/**
	 * 所有元素
	 */
	private E[] elements;
	
	/**
	 * 元素数量
	 */
	private int size = 0;
	
	/**
	 * 初始化数组
	 */
	public ArrayList(int capaticy) {
		
		elements = (E[]) new Object[capaticy];
	}
	
	/**
	 * 初始化数组（无参）
	 */
	public ArrayList() {
		this(DEFAULT_CAPATICY);
	}
}

如果看到定义的属性中，竟然还定义了一个elements数组属性，就发出“？”。

这里就简单说一下元素在内存中的如何存放，看构造函数中用 new 创建数组，本质就是在堆空间申请了一个连续的空间准备存放数组，elements 中每个 index 是指向内存空间的指针（和 C++ 中的内存空间不同）。

为什么要申请堆空间来存放数据？

在内存管理中，有栈空间和堆空间可以存放一些临时创建的数据，区别就是栈空间的创建和释放是系统管理的，但是堆空间就可以开发人员自己管理。咱们创建的数组，肯定不希望自己无法控制，所以堆空间是最好的选择。

那么为什么 new 就是申请堆空间？这是代码特性，没有什么道理的规定

实现方法

实现方法的思路是从简单到复杂

看 Array 中定义的属性，有元素数量size，size是记录数组中已经存在的元素数量，那么就可以先快速实现元素的数量和是否为空两个方法

/**
 * 元素的数量
 * @return
 */
public int size() {
  return size;
}

/**
 * 是否为空
 * @return
 */
public boolean isEmpty() {
  return size == 0;
}

因为元素是存放在 elements 这个数组中的，所以删除元素的方法就可以通过遍历方式快速实现

/**
 * 清除所有元素
 */
public void clear() {

  for (int i = 0; i < size; i++) {
    elements[i] = null;
  }
  size = 0;
}

获取 index 位置上的元素方法，可以使用数组索引的方法实现

/**
 * 获取index位置的元素
 * @param index
 * @return
 */
public E get(int index) {
  return elements[index];
}

设置 index 位置的元素方法，也可以直接在elements数组上直接操作。


/**
 * 设置index位置的元素
 * @param index
 * @param element
 * @return 原来的元素ֵ
 */
public E set(int index, E element) {

  E oldElement = elements[index];
  elements[index] = element;
  return oldElement;
}

添加元素

简单的方法实现完了，接下来就实现复杂的方法。那么在复杂的方法中首先实现基础的方法。

那么现在首要实现的方法是add(int index, E element)(在 index 位置插入一个元素)。为什么要首要实现呢？这个问题咱先放放，先实现

当在 index 位置插入元素时，index 位置的元素开始都要往后移动一个位置，然后把这个元素放到 index 位置。不要忘记把记录已经存放元素数量的size加 1 操作。

/**
 * 在index位置插入一个元素
 * @param index
 * @param element
 */
public void add(int index, E element) {

  for (int i = size; i > index; i--) {
    elements[i] = elements[i-1];
  }
  elements[index] = element;
  size++;
}

接下来在这个方法基础上实现add(E element)(添加元素到尾部)，就是在 size 位置上插入一个元素。这就是首要实现在 index 位置插入一个元素的原因。

/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element) {
  add(size, element);
}

查看元素

循着添加元素的实现逻辑，首要实现indexOf(E element)（查看元素的索引）方法。该方法需要分 element 不为 null 和为 null 两种情况处理。若 element 为 null，那么就没法进行比较

/**
 * 查看元素的索引
 * @param element
 * @return
 */
public int indexOf(E element) {

  if (element == null) {
    for (int i = 0; i < size; i++) {
      if (elements[i] == null) {
        return i;
      }
    }
  }
  else {
    for (int i = 0; i < size; i++) {
      if (element.equals(elements[i])) {
        return i;
      }
    }
  }
  return ELEMENT_NOT_FOUND; // 常量：-1，数组中没有该元素
}

在这基础上，可以实现contains(E element)（是否包含某个元素）。方法中直接判断 element 元素的 index 是否等于 -1 来判断返回。

/**
 * 是否包含某个元素
 * @param element
 * @return
 */
public boolean contains(E element) {
  return indexOf(element) != ELEMENT_NOT_FOUND;
}

删除元素

继续首要实现基础方法思路，先实现remove(int index)（删除 index 位置的元素）方法。

数组从 index 位置到尾部遍历，后面的元素不断覆盖前面的元素。然后把最后一个元素设置为 null。size 的大小也要减 1.

/**
 * 删除index位置的元素
 * @param index
 * @return
 */
public E remove(int index) {
  rangeCheck(index);

  E oldElement = elements[index];
  for (int i = index; i < size; i++) {
    elements[i] = elements[i+1];
  }
  size --;

  elements[size] = null;
  return oldElement;
}

接下来实现remove(E element)（删除元素）方法。它就可以先获取 element 元素的 index，然后再删除 index 位置的元素。通过这两个方法实现。

/**
 * 删除元素
 * @param element
 */
public void remove(E element) {
  remove(indexOf(element));
}

数组越界

截止到现在，动态数组的11个方法已经实现完了。畅快淋漓之后，要开始补补漏洞。

使用数组的方法，不怕元素不存在，就要坐标越界，所以就需要在传入 index 参数的方法中先要判断一下是否越界，如果越界，就不能再进行下面的代码实现。

/**
 * 判断坐标是否越界
 * @param index
 */
private void rangeCheck(int index) {
  if (index < 0 || index >= size) {
    outOfBound(index);
  }
}

private void outOfBound(int index) {
  throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
}

但是添加元素到尾部的时候，是把元素放到 size 的位置，那么就需要排除 index == size 的判断。

private void rangeCheckOfAdd(int index) {
  if (index < 0 || index > size) {
    outOfBound(index);
  }
}

扩容

补了数组越界的洞之后，但是 elements 开始设置容量是 10 个元素，如果添加元素时，超过 elements 的容量时，就需要进行扩容操作。

执行扩容方法时，先要判断容量是否够用，不够用时，就创建一个1.5倍之前 elements 容量的新数组，然后遍历老数组元素放置到新的数组中。

/**
 * 扩容
 * @param capacity
 */
private void ensureCapacity(int capacity) {
  int oldCapacity = elements.length;

  if (capacity <= oldCapacity) {
    return;
  }

  int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩大 1.5 倍
  E[] newElements = (E[]) new Object[newCapacity];
  for (int i = 0; i < size; i++) {
    newElements[i] = elements[i];
  }

相对的，需要进行缩容吗？如何实现缩容？这两个问题可以根据实际情况来进行，思路和扩容是相似的。

整体实现

动态数组已经完美实现了。接下来就完整的贴一下代码，整体的看一下代码实现，再品味品味动态数组的实现逻辑。

@SuppressWarnings({"unused","unchecked"})
public class ArrayList<E> {
	/**
	 * 默认数组大小
	 */
	private static final int DEFAULT_CAPATICY = 10;
	
	/**
	 * 默认标示
	 */
	private static final int ELEMENT_NOT_FOUND = -1;
	
	/**
	 * 所有元素
	 */
	private E[] elements;
	
	/**
	 * 元素数量
	 */
	private int size = 0;
	
	/**
	 * 初始化数组
	 */
	public ArrayList(int capaticy) {
		// 忘记
		capaticy = (capaticy < DEFAULT_CAPATICY ? DEFAULT_CAPATICY: capaticy);
		
		elements = (E[]) new Object[capaticy];
	}
	
	/**
	 * 初始化数组（无参）
	 */
	public ArrayList() {
		this(DEFAULT_CAPATICY);
	}

	/**
	 * 清除所有元素
	 */
	public void clear() {
		
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}

	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	public void add(E element) {
		add(size, element);
	}

	/**
	 * 获取index位置的元素
	 * @param index
	 * @return
	 */
	public E get(int index) {
		rangeCheck(index);
		return elements[index];
	}

	/**
	 * 设置index位置的元素
	 * @param index
	 * @param element
	 * @return 原来的元素ֵ
	 */
	public E set(int index, E element) {
		rangeCheck(index);
		
		E oldElement = elements[index];
		elements[index] = element;
		return oldElement;
	}

	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	public void add(int index, E element) {
		rangeCheckOfAdd(index);
		ensureCapacity(size+1); 
		
		for (int i = size; i > index; i--) {
			elements[i] = elements[i-1];
		}
		elements[index] = element;
		size++;
	}

	/**
	 * 删除index位置的元素
	 * @param index
	 * @return
	 */
	public E remove(int index) {
		rangeCheck(index);
		
		E oldElement = elements[index];
		for (int i = index; i < size; i++) {
			elements[i] = elements[i+1];
		}
		size --;
		
		elements[size] = null;
		return oldElement;
	}
	
	/**
	 * 删除元素
	 * @param element
	 */
	public void remove(E element) {
		remove(indexOf(element));
	}

	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element) {
		
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (elements[i] == null) {
					return i;
				}
			}
		}
		else {
			for (int i = 0; i < size; i++) {
				if (element.equals(elements[i])) {
					return i;
				}
			}
		}
		return ELEMENT_NOT_FOUND;
	}
	
	/**
	 * 扩容
	 * @param capacity
	 */
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		
		if (capacity <= oldCapacity) {
			return;
		}
		
		int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩大 1.5 倍
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
	}
	
	private void outOfBound(int index) {
		throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
	}
	
	/**
	 * 判断坐标是否越界
	 * @param index
	 */
	private void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfBound(index);
		}
	}
	
	private void rangeCheckOfAdd(int index) {
		if (index < 0 || index > size) {
			outOfBound(index);
		}
	}
	
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("size:").append(size).append(" ").append("[");
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				stringBuilder.append(",");
			}
			stringBuilder.append(elements[i]);
		}
		stringBuilder.append("]");
		return stringBuilder.toString();
	}
}

码农公寓