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

Question

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.

Do you really want to return a `LinkedList` ? Or would it be ok to implement a new List which would wrap several `LinkedList` and that would get elements in those underlying LinkedList ? — Arnaud Denoyelle, Mar 01 '19 at 14:16
I think both can work. The wrapping is fine as long as it doesn't add nonconstant complexity. — Shreck Ye, Mar 01 '19 at 15:11

score 4 · Accepted Answer · answered Mar 02 '19 at 09:55

4

In Kotlin you can combine multiple Iterators 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.

answered Mar 02 '19 at 09:55

functionaldude

682
6
14

I see but what this function does is the same to Google Guava `Iterators.concat`. It creates an iterator that wraps multiple iterators. In my case when such lists are dynamically generated, I concat lists 2 at a time. This can cause multiple layers of wrapping and adds complexity when iterating. – Shreck Ye Mar 03 '19 at 01:05
I think I was wrong about this iterator wrapping paradigm. If given the assumption that a combined iterator wrapper wraps at least 2 iterators, and each linked list iterator has at least 1 element, then it forms a tree data structure and iteration aka traversal can be completed in O(n) time, because the number of all elements >= the number of leaf nodes (linked list iterators) > 1/2 the number of all nodes (all iterator instances). Maybe you should edit your answer to 1. filter out empty iterators and 2. return the original iterator if there is only one left, then I will accept your answer. – Shreck Ye Oct 17 '19 at 10:30

Shreck Ye · Answer 2 · 2019-03-03T23:21:32.710

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:

Java implementation:

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 implementation:

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

The Kotlin implementation is actually a little bit slower than the Java one because getters and setters are used to access properties.

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

2 Answers2