Scala newbie here. I'm trying to implement a mutable linked list in Scala. (there exists a library class for doing the same - I'm just trying this as a learning exercise). So far, I am only supporting the add() operation. Here's my stab at it:
class MutableList[T] {
class Node[T](val value: T) {
var next: Node[T] = null
def hasNext = (next != null)
}
var first, last: Node[T] = null
var size = 0
def add(value: T) = {
val newNode = new Node[T](value)
if (first == null) {
assert(size == 0)
first = newNode
} else {
last.next = newNode
}
last = newNode
size += 1
}
override def toString = {
def getValues() = {
var current = first
for (i <- 1 to size) yield {
val valStr = current.value.toString
current = current.next
valStr
}
}
getValues().mkString(",")
}
}
I know that a mutable data structure is not the best thing to use/implement in Scala. But I'm just experimenting and was wondering if there is a more functional Scala way of writing this?
EDIT:
Thanks everyone for all the comments. I have tried to remove nulls and use more native Scala constructs. Comments welcome.
class MutableLinkedList[T] {
private type Node = MutableLinkedList[T]#MutableListNode
class MutableListNode(val value: T) {
var next: Option[Node] = None
}
private var first, last: Option[Node] = None
private var _size = 0
def size = _size
def add(value: T) = {
val newNode = Some(new MutableListNode(value))
first match {
case None => {
assert(_size == 0)
first = newNode
}
case Some(x) => {
assert(last.isDefined)
last.get.next = newNode
}
}
last = newNode
_size += 1
}
def head: Option[T] = {
first match {
case None => None
case Some(x) => Some(x.value)
}
}
def tail: Option[MutableLinkedList[T]] = {
first match {
case None => None
case Some(x) => {
var l = new MutableLinkedList[T]
l.first = this.first.get.next
l.last = this.last
l._size = this.size - 1
Some(l)
}
}
}
def exists(value: T): Boolean = {
var current = first
var foundIt = false
while(current.isDefined && !foundIt) {
if(current.get.value == value)
foundIt = true
current = current.get.next
}
foundIt
}
def delete(value: T): Boolean = {
var previous: Option[Node] = None
var current = first
var deleted = false
while(current.isDefined && !deleted) {
if(current.get.value == value) {
if(!previous.isDefined)
first = current.get.next
else
previous.get.next = current.get.next
_size -= 1
deleted = true
}
previous = current
current = current.get.next
}
deleted
}
override def toString = {
var current = first
var output = ""
while(current.isDefined) {
output += current.get.value.toString
current = current.get.next
if(current.isDefined)
output += ","
}
output
}
}
null.varonly at the top-level, but have theNodeitself be immutable and b) either make use ofOption[T]or haveNodea sealed trait with implementationsEmptyNodeandFullNode.a,b,a,cyou can't delete the 3rd element (the 2nda).