跳到主要内容

01、数据结构与算法 - 基础:动态数组

摘要

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

本文结构先总结 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 中定义的属性,有元素数量sizesize是记录数组中已经存在的元素数量,那么就可以先快速实现元素的数量是否为空两个方法

/**
 * 元素的数量
 * @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();
	}
}