Kotlin 或 Java 中恒定时间复杂度 O(1) 的 Concat 链表

Question

我正在做的是连接动态生成的链表，一次只有 2 个。如何在 Kotlin 或 Java 中以恒定时间复杂度 O(1) 做到这一点？Java中的这个类似问题告诉我java.util.LinkedList不支持在恒定时间内添加。而且 Google GuavaIterators.concat只能在一次调用中组合 2 个或更多迭代器，这会导致多层包装并在我的情况下迭代时增加复杂性。

Answer 1

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

fun <T> combine(a: Iterator<T>, b: Iterator<T>, c: Iterator<T>): Iterator<T> {

  return iterator {

    yieldAll(a)

    yieldAll(b)

    yieldAll(c)

  }

}

这个函数返回一个Iterator类型，然后和最后T延迟消耗abc

解决方案是这样的：

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 用于访问属性。