Конкатные связанные списки в постоянной временной сложности O (1) в Kotlin или Java

Question

То, что я делаю, - это конкатенация динамически генерируемых связанных списков, только 2 одновременно.Как сделать это с постоянной сложностью O (1) в Kotlin или Java?

Этот похожий вопрос в Java говорит мне, что java.util.LinkedList не поддерживает добавление в постоянное время.А Google Guava Iterators.concat может объединять только 2 и более итераторов в одном вызове, что вызывает многоуровневую упаковку и добавляет сложности при итерации в моем случае.

Answer 1

Я реализовал простую версию односвязного списка, основанного на 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, потому что для доступа к свойствам используются геттеры и сеттеры.

Answer 2

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

Эта функция возвращает Iterator типа T, который лениво потребляет a затемb и, наконец, c

Решение будет примерно таким:

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

Эта реализация принимает n итераторов и объединяет их в один.