Complexity of linked-lists concatenation

Question

I'm still pretty much new to functional programming and experimenting with algebraic data types. I implemented LinkedList as follows:

sealed abstract class LinkedList[+T]{
  def flatMap[T2](f: T => LinkedList[T2]) = LinkedList.flatMap(this)(f)
  def foreach(f: T => Unit): Unit = LinkedList.foreach(this)(f)
}

final case class Next[T](t: T, linkedList: LinkedList[T]) extends LinkedList[T]
case object Stop extends LinkedList[Nothing]

object LinkedList{
  private def connect[T](left: LinkedList[T], right: LinkedList[T]): LinkedList[T] = left match {
    case Stop => right
    case Next(t, l) => Next(t, connect(l, right))
  }

  private def flatMap[T, T2](list: LinkedList[T])(f: T => LinkedList[T2]): LinkedList[T2] = list match {
    case Stop => Stop
    case Next(t, l) => connect(f(t), flatMap(l)(f))
  }

  private def foreach[T](ll: LinkedList[T])(f: T => Unit): Unit = ll match {
    case Stop => ()
    case Next(t, l) =>
      f(t)
      foreach(l)(f)
  }
}

The thing is that I wanted to measure complexity of flatMap operation.

The complexity of flatMap is O(n) where n is the length of flatMaped list (as far as I could prove by induction).

The question is how to design the list that way so the concatenation has constant-time complexity? What kind of class extends LinkedList we should design to achieve that? Or maybe some another way?

Answer 1

One approach would be to keep track of the end of your list, and make your list nodes mutable so you can just modify the end to point to the start of the next list.

I don't see a way to do it with immutable nodes, since modifying what follows a tail node requires modifying everything before it. To get constant-time concatenation with immutable data structures, you need something other than a simple linked list.