Single Linked List implementation in Scala

Single Linked List implementation in Scala

Linked list is linear data structure where elements are not sorted and there memory locations are not in sequence.So liked list has Struct called Node which hold data and reference to the next element.

Linked list

As shown in the above diagram linked list contain's node where first node will have data and reference of the second node and so on, only last node reference will be null. so lets see how do we construct node and Linked List in Scala.

case class LinkedList[T]() {
  var head: Node[T] = null;
}


sealed class Node[T](var data: T, var next: Node[T]) {
  def getData: T = this.data

  def getNext: Node[T] = this.next;

  def printList(): Unit = {
    print(data)

    if (next != null) {
      print(",")
      next.printList();
    }

  }

}

As we know we can store any data type in linked list so we shall make use of generic type in Scala, so that we can decide the data type during initialisation. so the class `LinkedList` will contain the head object of type Node.

The Node

As we know node is the integral part of LL, which holds the actual data and reference to the next Node. as same as linked list we shall implement its generic trait, and we have sealed this class by sealed keyword so the class is not accessible outside LinkedList class.

Feature Expansion.

So now we shall expand our LL class to provide traditional feature like print,push, prepend, delete an item,reverse the Linked list.

Note: Examples provided is implementation of the Queue FIFO order

  • Pushing and item to Linked List
 def push(data: T) = {
    head match {
      case null => head = new Node(data, null)

      case _ => {
        var last: Node[T] = head;

        while (last.next != null) {
          last = last.next;
        }

        last.next = new Node[T](data, null);
      }
    }
  }

so now we shall define a method called push instead of using traditional if else we shall use pattern matching feature of Scala, this is like switch statement in Java, first case statement check is the head element is null, if so it creates an new Node Instance with data and reference as null, and _ case statement like else condition is the Head is not null we are traversing till null reference and adding the data.

* Appending data

  def append(data:T) = {
    push(data);
  }

As append is process of attaching element at end.So our push function exhibit the same behaviour so i have just wrapped the append function with push function.

* Prepending the Data

 def prepend(data:T): Unit = {
    val tempHead:Node[T]  = new Node[T](data,head);
    head = tempHead;
  }

This process is exact opposite to append, we attach data to the start.so function is very simple create temp node with data and attach current head as reference and replace the head with temp node.

* Printing the elements

 def print() = {
    if (head != null) {
      head.printList();
    }
    println();
  }

* Delete an Item

  def delete(deleteItem: T) = {
    var previousNode: Node[T] = head
    var currentNode: Node[T] = head

    val loopBreak = new Breaks;

    loopBreak.breakable {
      while (currentNode != null) {
        if (currentNode.data.equals(deleteItem)) {
          if (currentNode.equals(previousNode)) {
            head = currentNode.next
          } else {
            previousNode.next = currentNode.next;

          }
          loopBreak.break();
        } else {
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
      }
    }

  }

so take aways from this function is we need breaks to break the loop, when the element is discovered we detach the reference and point the reference to previous, is not we change previous with current element and current to next for next iteration.

* Reversing the List

  def reverse(): Unit = {
    var previous:Node[T] = null;
    var current:Node[T] = head;
    var next:Node[T] = null;

    while (current != null) {
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    head = previous;
  }

so reverse the list we need 3 new variables previous, next , current of type Node where previous and next will null current will be head, while traversing reassign the node like we swap numbers.

* Get Item by Index

  def getDataByIndex(index: Int): T = {
    var currentNode = head
    var currentIndex = 0;

    while (!currentIndex.equals(index)) {
      currentNode = currentNode.next
      currentIndex += 1;
    }

    currentNode.data;
  }

}

Complete implementation of linked list class will be like this.

import scala.util.control.Breaks

case class LinkedList[T]() {
  var head: Node[T] = null;

  def push(data: T) = {
    head match {
      case null => head = new Node(data, null)

      case _ => {
        var last: Node[T] = head;

        while (last.next != null) {
          last = last.next;
        }

        last.next = new Node[T](data, null);
      }
    }
  }

  def append(data:T) = {
    push(data);
  }

  def prepend(data:T): Unit = {
    val tempHead:Node[T]  = new Node[T](data,head);
    head = tempHead;
  }

  def print() = {
    if (head != null) {
      head.printList();
    }
    println();
  }

  def delete(deleteItem: T) = {
    var previousNode: Node[T] = head
    var currentNode: Node[T] = head

    val loopBreak = new Breaks;

    loopBreak.breakable {
      while (currentNode != null) {
        if (currentNode.data.equals(deleteItem)) {
          if (currentNode.equals(previousNode)) {
            head = currentNode.next
          } else {
            previousNode.next = currentNode.next;

          }
          loopBreak.break();
        } else {
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
      }
    }

  }

  def reverse(): Unit = {
    var previous:Node[T] = null;
    var current:Node[T] = head;
    var next:Node[T] = null;

    while (current != null) {
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    head = previous;
  }

  def getDataByIndex(index: Int): T = {
    var currentNode = head
    var currentIndex = 0;

    while (!currentIndex.equals(index)) {
      currentNode = currentNode.next
      currentIndex += 1;
    }

    currentNode.data;
  }

}

sealed case class Node[T](var data: T, var next: Node[T]) {
  def getData: T = this.data

  def getNext: Node[T] = this.next;

  def printList(): Unit = {
    print(data)

    if (next != null) {
      print(",")
      next.printList();
    }

  }

}

Usage



object Main extends App {

  var list: LinkedList[Int] = new LinkedList();

  list.push(1);
  list.push(2);
  list.push(3);
  list.print()
  list.delete(1);
  list.print();
  list.reverse();
  list.print();
  println(list.getDataByIndex(1));
  list.prepend(23);
  list.print();
  list.reverse();
  list.print();


}