Single Linked List implementation in Scala
Also published in
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.
As 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.
- Pushing and item to Linked List implementation is FIFO order. Generally we see implementation in Stack LIFO order
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.Breakscase 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();
}