本文共 6027 字,大约阅读时间需要 20 分钟。
本篇是的学习笔记, 使用JAVA语言
顺序存储
的线性表,所有元素的内存地址都是连续的int[] array = new int[]{11, 22, 33}复制代码
在很多编程语言中, 数组有个致命的缺点, 无法动态修改容量
实际开发中我们希望数组的容量是动态变化的
增删改查
操作// 元素的数量int size(); // 是否为空boolean isEmpty();// 是否包含某个元素boolean contains(E element); // 添加元素到最后面void add(E element); // 返回index位置对应的元素E get(int index); // 设置index位置的元素E set(int index, E element); // 往index位置添加元素void add(int index, E element); // 删除index位置对应的元素 E remove(int index); // 查看元素的位置int indexOf(E element); // 清除所有元素void clear(); 复制代码
ArrayList
如下图, 创建size
属性来管理数组中元素的个数, 创建elements
属性来管理存取的数据
public class ArrayList{ private int size; private E[] elements;}复制代码
elements
数组, 并指定elements
默认的容量public class ArrayList{ private int size; private E[] elements; // 设置elements数组默认的初始化空间 private static final int CAPACITY_DEFAULT = 10; public ArrayList(int capacity) { capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity; elements = (E[]) new Object[capacity]; } // 默认情况 public ArrayList() { this(CAPACITY_DEFAULT); }}复制代码
1、添加元素
新元素需要添加到的索引
等于当前数组元素的个数
, 在ArrayList
中size
属性就是当前数组元素的个数
, 所以就是将新元素添加到数组的size
位置上, 然后size
加1
public void add(E element) { elements[size] = element; size++;}复制代码
2、数组扩容
elements
最大的容量只有10
, 所以当数组存满元素时, 就需要对数组进行扩容
private void ensureCapacity() { // 获取数组当前容量 int oldCapacity = elements.length; // 如果 当前存储的元素个数 < 当前数组容量, 直接返回 if (size < oldCapacity) return; // 新数组的容量为原数组容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 创建新数组 E[] newElements = (E[]) new Object[newCapacity]; // 原数组中的元素存储到新数组中 for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } // 引用新数组 elements = newElements;}复制代码
add
方法的实现如下, 在添加新元素之前, 先判断是否需要扩容public void add(E element) { // 添加新元素之前, 先判断是否需要扩容 ensureCapacity(); elements[size] = element; size++;}复制代码
3、删除元素
指定位置的元素
, 并将后面的元素向前移动
3
的元素时, 只需要将后面的元素向前移动, 然后在去掉最后一个元素, size
减1
即可
public E remove(int index) { // 取出需要删除的元素 E element = elements[index]; // 通过循环, 将index后面的所有元素向前移动一位 for (int i = index; i < size - 1; i++) { elements[i] = elements[i + 1]; } // 删除最后一个元素 elements[--size] = null; // 将删除的元素返回 return element;}复制代码
不能小于0, 也不能大于等于size
private void rangeCheck(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); }}复制代码
remove
方法实现如下public E remove(int index) { // 判断索引是否越界 rangeCheck(index); // 取出需要删除的元素 E element = elements[index]; // 通过循环, 将index后面的所有元素向前移动一位 for (int i = index; i < size - 1; i++) { elements[i] = elements[i + 1]; } // 删除最后一个元素 elements[--size] = null; // 将删除的元素返回 return element;}复制代码
4、数组缩容
public void trim() { // 获取当前数组的容量 int capacity = elements.length; // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回 if (size >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return; // 计算新的容量 = 原有容量的一半 int newCapacity = capacity >> 1; // 创建新数组 E[] newElements = (E[]) new Object[newCapacity]; // 将原数组元素存入新数组 for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } // 引用新数组 elements = newElements;}复制代码
public E remove(int index) { // 判断索引是否越界 rangeCheck(index); // 取出需要删除的元素 E element = elements[index]; // 通过循环, 将index后面的所有元素向前移动一位 for (int i = index; i < size - 1; i++) { elements[i] = elements[i + 1]; } // 删除最后一个元素 elements[--size] = null; // 判断数组是否需要缩容 trim(); // 将删除的元素返回 return element;}复制代码
5、清空元素
null
, 然后size
置为0
public void clear() { // 清空存储的数据 for (int i = 0; i < size; i++) { elements[i] = null; } // 将size置为0 size = 0;}复制代码
6、修改元素
public E set(int index, E element) { // 判断索引是否越界 rangeCheck(index); // 取出被替换元素 E oldElement = elements[index]; // 替换元素 elements[index] = element; // 返回被替换元素 return oldElement;}复制代码
7、 查询元素
public E get(int index) { rangeCheck(index); return elements[index];}复制代码
8、插入元素
public void add(int index, E element) { // 从后向前的顺序, 将元素向后移动 for (int i = size - 1; i >= index; i--) { elements[i + 1] = elements[i]; } // 插入元素 elements[index] = element; // size+1 size++;}复制代码
public void rangeCheckForAdd(int index) { // 当索引小于0 或 大于 size时 抛出异常 if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); }}复制代码
add
方法如下public void add(int index, E element) { // 检查索引是否越界 rangeCheckForAdd(index); // 从后向前的顺序, 将元素向后移动 for (int i = size - 1; i >= index; i--) { elements[i + 1] = elements[i]; } // 插入元素 elements[index] = element; // size+1 size++;}复制代码
9、查看元素位置
null
, 而null
是不能调用equals
方法的, 所以需要对传入的元素进行判断, 如果查找的元素是null
, 需要单独处理ELEMENT_ON_FOUND
的值private static final int ELEMENT_ON_FOUND = -1;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_ON_FOUND;}复制代码
10、是否包含某个元素
ELEMENT_ON_FOUND
即可public boolean contains(E element) { // 查看元素的索引是否为ELEMENT_ON_FOUND即可 return indexOf(element) != ELEMENT_ON_FOUND;}复制代码
11、元素的数量
public int size() { return size;}复制代码
12、数组是否为空
size
的值是否为0
即可public boolean isEmpty() { return size == 0;}复制代码
13、动态数组打印
toString
方法, 来打印ArrayList
中的元素@Overridepublic String toString() { StringBuilder string = new StringBuilder(); string.append("size = ").append(size).append(", ["); for (int i = 0; i < size; i++) { if (i != 0) { string.append(","); } string.append(elements[i]); } string.append("]"); return string.toString();}
转载地址:http://jafsf.baihongyu.com/