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

问题: 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 que...

问题:

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.


回答1:

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.


回答2:

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:

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 }
    }
}
  • 发表于 2019-03-03 19:12
  • 阅读 ( 200 )
  • 分类:sof

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除