Fixed size double linked list in Scala

Question

I have written a double linked list in Scala. The list should be fixed in size and items are always added to the head. if the list reaches max size then the tail is dropped.

This is my code. I want to review this for brevity and functional approach.

sealed trait List {
    var prev : List
    var next : List
}

case object Empty extends List {
    var prev : List = Empty
    var next : List = Empty
}
case class Node(v: Int, p: List, n: List) extends List {
    var prev = p
    var next = n
}

class DoubleLinkedList(maxSize: Int) {
    private var head : List = Empty
    private var tail : List = Empty
    private var currentSize = 0
    def print() : Unit = {
        var temp = head 
        while(temp != Empty) {
            temp match {
                case Empty => println("Empty")
                case Node(v, _, _) => println(v)
            }
            temp = temp.next
        }
    }
    def add(i: Int) : List = {        
        if (head == Empty || tail == Empty) {
            val n = new Node(i: Int, Empty, Empty)
            head = n
            tail = n
            currentSize += 1
            Empty
        } else {
            val n = new Node(i, null, head)
            head.prev = n
            head = n
            currentSize += 1
            if (currentSize > maxSize) {
                val retVal = tail
                tail = tail.prev
                tail.next = Empty
                currentSize -= 1
                retVal
            } else Empty
        }
    }
}

jwvh · Accepted Answer · 2018-07-04 21:01:44Z

A few things I've noticed.

while(temp != Empty) {
  temp match {
    case Empty => println("Empty")
    . . .

That will never print "Empty".

case object Empty extends List {
  var prev : List = Empty
  var next : List = Empty
}

That looks like a reasonable definition of an empty end-point, but the member elements are both mutable variables which means that some code later on could modify the Empty object to have real prev and/or next values.

What you're after is a set of references to prev and next nodes if the node exists, otherwise it should be a meaningless, or "empty", reference. To me that suggests Option[Node].

You say you seek "brevity and functional approach," and there's room for improvement on both fronts, but the basic design, class instances that maintain mutable state, goes against the fundamental FP concept of referential transparency.

What's more, the add() method returns a List instance that can allow code outside of the DoubleLinkedList definition to modify its state and introduce hard-to-find bugs.

val dll = new DoubleLinkedList(3)
dll.print()
dll.add(9)
dll.add(8)
dll.add(7)
dll.add(6).prev = Empty
dll.print()  // dll has been corrupted

Here's an implementation of your basic design that is a bit more concise and needs fewer vars. It still exposes mutable nodes to the outside world, but that seems to be an inescapable aspect of your design.

class DoubleLinkedList[A](maxSize: Int) {
  class Node(val v :A, var prev :Option[Node], var next :Option[Node]) {
    def print() :Unit = {
      Predef.print(s"$v <-> ")
      next.fold(println("End"))(_.print())
    }
  }
  private var head :Node = _
  private var tail :Node = _
  private var currentSize = 0
  def print() :Unit = Option(head).fold(println("Empty"))(_.print())
  def add(i :A) :Option[Node] = {
    head = new Node(i, None, Option(head))
    head.next.fold(tail = head)(_.prev = Some(head))
    if (currentSize < maxSize) {
      currentSize += 1
      None
    } else {
      val retVal = tail
      tail = tail.prev.get
      tail.next = None
      Option(retVal)
    }
  }
}

usage:

val dll = new DoubleLinkedList[Int](3)
dll.print()  // "Empty"
dll.add(9)
dll.add(8)
dll.add(7)
dll.add(6)
dll.print()  // "6 <-> 7 <-> 8 <-> End"

Thank you so much. I can write immutable code in my daily programming life. but when I take an algorithms class somehow every line I write is mutable. — Knows Not Much
– Knows Not Much, Commented Jul 5, 2018 at 22:12

Stack Exchange Network

Fixed size double linked list in Scala

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Fixed size double linked list in Scala

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions