中国城乡建设协会网站/产品软文范例

前言

上次面试时，手写ArrayList竟然翻车，忘了里面的扩容与缩容的条件，再次实现一次，加深印象

源码讲了什么

1. 实现了List列表和RandomAccess随机访问接口
2. List具有增删改查功能，RandomAccess支持下标访问
3. 内部是一个扩容数组，默认大小是10，size=size+size/2

如何实现

1. 实现List的add，remove，set，get
2. 实现RandomAccess的下标访问
3. 实现集合的基本size，isEmpty，toString
4. 实现扩容grow，每一增到1.5倍，size=size+size/2
5. 缩容方法需要手动调用（内部不会再remove自动调用），使数组容量等于当前元素个数，array=Array(size)，size元素个数，array.size时容量

fun main() {val list = MyArrayList()list.add(1)list.add(2)list.add(3)list.add(0, 2)list.set(list.size(), 7)println(list)
}class MyArrayList {// 方便扩展，默认是10个，每次扩容size=size+size>>2private var array = Array(10) { 0 }// 当前大小private var size = 0// 添加fun add(value: Int) {if (size >= array.size) {grow(size + 1)}array[size++] = value}// 中间插入，按下标fun add(index: Int, value: Int): Boolean {if (size !in 0..size) {return false}if (size >= array.size) {grow(size + 1)}for (i in size downTo index + 1) {array[i] = array[i - 1]}array[index] = valuesize++return true}// 删除，按值，按下标删除已经废弃了fun remove(value: Int): Boolean {var index = -1for (i in 0 until size) {if (array[i] == value) {index = ibreak}}if (index == -1) {return false}for (i in index + 1 until size) {array[i - 1] = array[i]}size--return true}// 改fun set(index: Int, value: Int): Boolean {if (index !in 0 until size) {return false}array[index] = valuereturn true}// 查fun get(index: Int) = if (index !in 0 until size) -1 else array[index]// toStringoverride fun toString() = StringBuilder().apply {append("[")for (i in 0 until size) {append(if (i == 0) array[i] else ", ${array[i]}")}append("]")}.toString()// 扩容，添加大量元素时会使用minCapacityprivate fun grow(minCapacity: Int) {var newCapacity = Math.max(minCapacity, array.size + array.size / 2)val newArray = Array<Int>(newCapacity) { 0 }for (i in 0 until size) {newArray[i] = array[i]}array = newArray}// 缩容方法不用，不写// 用来判断的emptyfun isEmpty() = size == 0fun isNotEmpty() = size > 0fun size() = size
}