CODEWITHSUNDEEP
scala
Aashish Dattani
Aashish Dattani

Reputation: 131

Mutable Linked List in Scala

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

Upvotes: 1

Views: 100

Answers (2)

francoisr
francoisr

Reputation: 4585

A functional version of this would be immutable. The implementation is very easy a and efficient if you append at the start of the List (O(1) time). Removals will take O(i) time, with i being the index where the removal occurs.

If you don't specifically need fast addition in the middle or at the end of the list, and you don't need to know the size in constant time, sticking to the immutable version is a good bet. The implementation is even easier, and you can read it in collection.immutable.List.

A simpler implementation, without all the standard collection library fluff, is described here.

Upvotes: 1

jwvh
jwvh

Reputation: 51271

First off, you really don't need or want the type parameter in both locations:

class MutableList[T] { //type parameter T

  class Node[T](val value: T) {...
          //^^^ a new type parameter T, shadowing the 1st

I'd keep the 1st and drop the 2nd, but it could go either way.

A common means to avoid null is to use Option.

class Node(val value: T) {
  var next: Option[Node] = None //no hasNext needed
}

With that in place your toString can simply start at the first, and iterate until it runs out of non-None nodes.

override def toString :String =
  Stream.iterate(Option(first))(_.flatMap(_.next))
        .takeWhile(_.nonEmpty)
        .map(_.get.value.toString)
        .mkString(",")

There are likely more ways to eliminate the use of null in the code but, so far, you haven't implemented any methods that requires last (or size) so it's hard to recommend suitable solutions.

I have to agree with Brian McCutchon's comment, this is probably a better fit over at Code Review.

Upvotes: 3

Related Questions