在 Kotlin 或 Java 中以恒定时间复杂度 O(1) 连接链表

Question

我正在做的是连接动态生成的链表，一次只有 2 个。如何在 Kotlin 或 Java 中的恒定时间复杂度 O(1) 中做到这一点？

Java 中的类似问题告诉我，java.util.LinkedList不支持添加常量时间。而且 Google GuavaIterators.concat只能在一次调用中组合 2 个或更多迭代器，这会导致多层包装，并在我的情况下增加迭代的复杂性。

Answer 1

在 Kotlin 中，您可以使用iterator {...}函数组合多个Iterator，如下所示：

fun <T> combine(a: Iterator<T>, b: Iterator<T>, c: Iterator<T>): Iterator<T> {
return iterator {
yieldAll(a)
yieldAll(b)
yieldAll(c)
}
}

此函数返回类型为T的Iterator，该延迟消耗a，然后b，最后c

解决方案是这样的：

fun <T> combine(vararg iterators: Iterator<T>): Iterator<T> {
return iterator {
iterators.forEach { yieldAll(it) }
}
}

此实现采用n迭代器并将它们组合为一个。

Answer 2

我已经实现了基于Java的LinkedList的单向链表的简单版本，只是为了支持这个concat函数。为简单起见，它只实现Iterable而不是List：

Java实现：

import java.util.Iterator;
import java.util.NoSuchElementException;
public class SimpleLinkedList<E> implements Iterable<E> {
Node<E> first;
Node<E> last;
static class Node<E> {
E item;
Node<E> next;
Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
static class NodeIterator<E> implements Iterator<E> {
private Node<E> node;
NodeIterator(Node<E> node) {
this.node = node;
}
public boolean hasNext() {
return node != null;
}
public E next() {
Node<E> currentNode = node;
if (currentNode == null) throw new NoSuchElementException();
node = currentNode.next;
return currentNode.item;
}
}
public Iterator<E> iterator() {
return new NodeIterator<>(first);
}
public void add(E element) {
// Copied from java.util.LinkedList
Node l = last;
Node<E> newNode = new Node<>(element, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
}
public void concatWith(SimpleLinkedList other) {
if (last != null) last.next = other.first;
else first = other.first;
if (other.last != null) last = other.last;
}
}

Kotlin 实现：

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 }
}
}

Kotlin 实现实际上比 Java 实现慢一点，因为 getter 和 setter 用于访问属性。