Kotlin动态数组的泛型实现

Question

我正在学习数据结构，并尝试使用泛型在Kotlin中从头开始实现动态数组。我使用MutableList实现了以下内容，但这感觉像是作弊。我这样做正确吗？还是有其他/更好的方法可以让我通过手动执行单个操作来学习？其他人通常怎么做？

class DynamicArray<T>(
private var values: MutableList<T>
) {
var length: Int = values.size
private set
var isEmpty: Boolean = length > 0
private set
fun getValues() = values
// O(1) time complexity
fun lookup(index: Int) = values[index]
// O(1) time complexity
fun push(item: T): MutableList<T> {
values.add(length, item)
length++
return values
}
// O(n) time complexity because we have to shift remaining items
fun remove(item: T): MutableList<T> {
values.remove(item)
length--
return values
}
}

Answer 1

具体地说，为了使DynamicArray存在，您需要一个已经实现的可变列表(动态数组)结构来依赖。

因此，如果你想了解这些数据结构是如何构建的，你应该尝试构建一个，而不是使用一个。现在你只是把困难的部分交给别人做。

请尝试仅使用Array类型来实现ArrayList样式的实现，或者尝试完全不使用Array来实现LinkedList类型的结构。

Answer 2

下面是一个使用Array作为底层DS的快速实现。它实现了一个MutableIterable，它基本上是一个允许您在迭代时移除元素的Iterable。

@Suppress("UNCHECKED_CAST")
class DynamicArray<T>(
private var size: Int,
private val expansionFactor: Float = 2f,
private val init: (Int) -> T) : MutableIterable<T> {
var capacity: Int = size
private set
private var arr: Array<Any?> = Array(size, init)
inner class DynamicArrayIterator: MutableIterator<T>{
val iterator = arr.iterator()
var index = -1
override fun hasNext(): Boolean {
return index<size-1
}
override fun next(): T {
if(iterator.hasNext()) index++
else throw NoSuchElementException()
return iterator.next() as T
}
override fun remove() {
removeAt(index--)
}
}
override fun iterator(): MutableIterator<T> = DynamicArrayIterator()
fun size(): Int = size
//O(1)
fun get(index: Int): T {
if(index > size-1) throw IndexOutOfBoundsException()
return arr[index] as T
}
//O(1)
fun set(index: Int, element: T) {
if(index > size-1) throw IndexOutOfBoundsException()
arr[index] = element
}
//O(1) amortized
fun add(element: T){
if(size == capacity){
capacity = (expansionFactor*size).toInt()
val newArr = Array<Any?>(capacity, init = init)
arr.forEachIndexed { index, any -> newArr[index] = any as T }
arr = newArr
}
arr[size] = element
size++
}
//O(n)
fun removeAt(index: Int): T{
if(index > size-1) throw IndexOutOfBoundsException()
val element = arr[index] as T
for( i in index until size){
arr[i] = arr[i+1]
}
size--
return element
}
//O(n)
fun remove(element: T): Boolean{
for(i in 0 until size){
if(arr[i] == element) {
removeAt(i)
return true
}
}
return false
}
//O(n)
override fun toString(): String {
val stringBuilder = StringBuilder()
stringBuilder.append("[")
var index = 0
do{
if (index in 1 until size)
stringBuilder.append(", ")
stringBuilder.append(arr[index])
index++
} while (index < size)
return stringBuilder.append("]").toString()
}
}