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

Answer 1

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"

• Knows Not Much: 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.