Adding to end of custom list

Question

I am doing a scala course and in one assignment I want to add to the end of a custom list.

trait EntityList {
  def head: Entity
  def tail: EntityList
  def isEmpty: Boolean
}

object Nil extends EntityList {
  def head = throw new java.util.NoSuchElementException("head of EmptyList")
  def tail = throw new java.util.NoSuchElementException("tail of EmptyList")
  def isEmpty = true
}

class Cons(val head: Entity, val tail: EntityList) extends EntityList {
  def isEmpty = false
}

I can add create a new element to the beginning of the list and create a new list by doing:

new Cons(myNewElement, myExistingList)

but how do I create a new list with a new element adding to the end of the custom list?

Randall Schulz · Accepted Answer · 2013-04-11 01:23:34Z

For a "Stock" (Standard Library) List

val l1 = List(1, 2, 3)
l1: List[Int] = List(1, 2, 3)

val l2 = l1 :+ 4
l2: List[Int] = List(1, 2, 3, 4)

val l3 = l2 ++ List(5, 6, 7, 8)
l3: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

However, you should consider carefully the consequences of trying to add new elements to the end of a cons-cell list such as List (and your "custom" list), since that's very inefficient. Often when you want this result you write a recursive algorithm that yields the list you want in backward order ('cause you do the efficient thing and add newly generated elements to the head of the accumulating list) and then when all that's done, reverse the backward list to get the correct sequence.

For your "Custom" List

For a elementary cons-cell list with none of the niceties of Scala's List, you can only build from the front. In that case, construct the list by adding new elements to the front (the only thing you can do) then write a reverse algorithm to get the list in the sequence you require.

Addendum

I guess I didn't really answer the question. If your goal / requirement is to append a new element to the end, then what you need to do is create a new list containing only that element and one by one (recursively) prepend each element of the existing list from last to first! Ideally you'd do this with a tail-recursive implementation. If you didn't understand the inefficiency of appending before you started, you will once you've done it.

Collectives™ on Stack Overflow

Adding to end of custom list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related