一、基本类型动态数组的实现
线性结构
几个概念
- e1即索引为0的是首节点，索引为n的是尾节点或尾元素
- e1是e2的前驱节点
- e2是e1的后继节点
线性表：数组，链表，队列，哈希表
Java中的数组是一种顺序存储数据的线性表，元素的内存地址是连续的，且数组的容量是在创建时就已经确定的，且无法修改的。那么如何创建一个动态数组？
动态数组实现
首先创建一个maven项目，增加test依赖,用于对接口或者方法进行单元测试
<dependencies> <dependency> <groupId>junit</groupId> <artifactId>junit</artifactId> <version>4.12</version> </dependency> </dependencies> 复制代码
动态数组肯定也是一个数组，也是基于数组的,所以成员变量包含一个数组elements以及数组中元素的数量size, 新建动态数组BasicArrayList，包含成员变量的定义,构造方法,toString()等，先设定动态数组只存放int类型的基本数据
public class BasicArrayList { private int size; private int[] elements; private static final int DEFAULT_CAPATICY = 10; public ArrayList(int capaticy){ // 如果capaticy < 10 就使用默认的容量，否则使用自定义的容量 capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy; elements = new int[capaticy]; } public ArrayList(){ elements = new int[DEFAULT_CAPATICY]; } @Override public String toString() { return "ArrayList{" + "size=" + size + ", elements=" + Arrays.toString(elements) + '}'; } } 复制代码
需要实现的方法如下：
void clear(); //清除所有元素 int size(); //返回数组中元素的数量 boolean isEmpty(); //判断数组是否为空 boolean contains(T element); //判断数组是否包含 void add(T element); // 在数组尾部添加元素 T get(int index); // 获取指定索引的元素 T set(int index, T element); // 设置指定位置的元素，并返回原来该位置的元素 void add(int index, T element); //在指定位置插入元素 T remove(int index); // 删除指定位置的元素，并返回该元素 int indexOf(T element); //获取指定元素的索引 复制代码
先实现简单的方法size(),isEmpty(),get(int index)
public int size(){ return size; } public boolean isEmpty(){ return size == 0; } public int get(int index){ // 需要对index进行校验 if (index < 0 || index >= size){ throw new IndexOutOfBoundsException("index=" + index + ",size=" + size); } return elements[index]; } 复制代码
新建一个测试类BasicArrayListTest,对size()和isEmpty进行测试
public class BasicArrayListTest { @Test public void size() { BasicArrayList arrayList = new BasicArrayList(10); Assert.assertEquals(0,arrayList.size()); } @Test public void isEmpty() { BasicArrayList arrayList = new BasicArrayList(10); Assert.assertTrue(arrayList.isEmpty()); } } 复制代码
实现set(),indexOf(),contains()和clear()方法
public int set(int index, int element){ // 对index进行校验 if (index < 0 || index >= size){ throw new IndexOutOfBoundsException("index=" + index + ",size=" + size); } int old = elements[index]; elements[index] = element; return old; } // 定义一个常量，当indexOf()方法找不到元素时返回 privare static int final ELEMENT_NOT_FOUND = -1; public int indexOf(int element){ // 遍历所有元素 for (int i = 0; i < size; i++) { if (elements[i] == element) return i; } return ELEMENT_NOT_FOUND; } public boolean contains(int element){ // 调用indexOf方法查看返回值是否为-1 return indexOf(element) != ELEMENT_NOT_FOUND; } public void clear(){ size = 0; } 复制代码
remove()方法实现
要注意删除成功后size减少一
public int remove(int index){ // 首先判断index if (index < 0 || index >= size){ throw new IndexOutOfBoundsException("index=" + index + ",size=" + size); } int old = elements[index]; // 只遍历需要挪动的部分，不需要遍历整个数组 for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } size --; return old; } 复制代码
add方法，默认添加到数组末尾,先不考虑容量的问题
public void add(int element){ elements[size++] = element; } 复制代码
测试以上实现的方法
public class BasicArrayListTest { BasicArrayList arrayList = null; @Before public void init(){ arrayList = new BasicArrayList(); arrayList.add(1); arrayList.add(2); arrayList.add(4); arrayList.add(3); arrayList.add(8); arrayList.add(5); arrayList.add(7); arrayList.add(6); } @Test public void size() { Assert.assertEquals(8,arrayList.size()); System.out.println("动态数组arrayList的size为：" + arrayList.size()); } @Test public void isEmpty() { Assert.assertFalse(arrayList.isEmpty()); System.out.println("动态数组arrayList是否为空：" + arrayList.isEmpty()); } @Test public void get() { int i = arrayList.get(1); Assert.assertEquals(2,arrayList.get(1)); System.out.println("arrayList中索引为1的元素是：" + arrayList.get(1)); } @Test public void set() { System.out.println("修改前," + arrayList.toString()); arrayList.set(1,10); System.out.println("将索引1位置的元素替换为10," + arrayList.toString()); } @Test public void indexOf() { Assert.assertEquals(7,arrayList.indexOf(6)); System.out.println("索引6位置的元素为：" + arrayList.indexOf(6)); } @Test public void contains() { Assert.assertTrue(arrayList.contains(1)); System.out.println("是否包含元素1：" + arrayList.contains(1)); } @Test public void clear() { System.out.println("清空前," + arrayList.toString()); arrayList.clear(); System.out.println("清空后,获取索引0的元素" + arrayList.get(1)); } @Test public void remove() { System.out.println("删除前," + arrayList.toString()); arrayList.remove(1); System.out.println("删除索引1的元素," + arrayList.toString()); } @Test public void add() { System.out.println(arrayList.toString()); arrayList.add(9); System.out.println(arrayList.toString()); } }
