问题:
What I am doing is concatenating dynamically generated linked lists, only 2 at a time. How to do this in constant time complexity O(1) in Kotlin or Java?
This similar que...
可以将文章内容翻译成中文,广告屏蔽插件会导致该功能失效:
问题:
What I am doing is concatenating dynamically generated linked lists, only 2 at a time. How to do this in constant time complexity O(1) in Kotlin or Java?
This similar question in Java tells me that java.util.LinkedList
doesn't support adding in constant time. And the Google Guava Iterators.concat
can only combine 2 or more iterators in one call, which causes multiple layers of wrapping and adds complexity when iterating in my case.
回答1:
In Kotlin you can combine multiple Iterator
s using the iterator {...}
function like this:
fun <T> combine(a: Iterator<T>, b: Iterator<T>, c: Iterator<T>): Iterator<T> {
return iterator {
yieldAll(a)
yieldAll(b)
yieldAll(c)
}
}
This function returns an Iterator
of type T
which lazily consumes a
then b
and finally c
The solution would be something like this:
fun <T> combine(vararg iterators: Iterator<T>): Iterator<T> {
return iterator {
iterators.forEach { yieldAll(it) }
}
}
This implementation takes n
iterators and combines them into one.
回答2:
I have implemented a simple version of singly linked list based on Java's LinkedList
only to support this concat function. For simplicity, it only implements Iterable
instead of List
:
class SimpleLinkedList<E> : Iterable<E> {
var first: Node<E>? = null
var last: Node<E>? = null
class Node<E>(var item: E, var next: Node<E>? = null)
class NodeIterator<E>(var node: Node<E>?) : Iterator<E> {
override fun hasNext(): Boolean = node != null
override fun next(): E {
val currentNode = node
if (currentNode === null) throw NoSuchElementException()
node = currentNode.next
return currentNode.item
}
}
override fun iterator(): Iterator<E> = NodeIterator(first)
fun add(element: E) {
// Copied from java.util.LinkedList
val l = last
val newNode = Node(element, null)
last = newNode
if (l == null)
first = newNode
else
l.next = newNode
}
infix fun concatWith(other: SimpleLinkedList<E>) {
last.run {
if (this !== null) next = other.first
else first = other.first
}
other.last?.let { last = it }
}
}