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

Question

我正在做的是连接动态生成的链表，一次只有 2 个。如何在 Kotlin 或 Java?

中以恒定时间复杂度 O(1) 执行此操作

This similar question in Java tells me that java.util.LinkedList doesn't support adding in constant time. And the Google Guava Iterators.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)
  }
}

这个函数 returns 一个 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 用于访问属性。

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

Concat linked lists in constant time complexity O(1) in Kotlin or Java

java

concat

linked-list

concatenation

kotlin