Introduction to Linked Lists with Scala

Introduction to Linked Lists

Hello there! Today, we will explore Linked Lists, a core data structure crucial for organized data management and establishing relationships between data. We will mark some essential milestones: an introduction to Linked Lists, their real-world applications, their implementation in Scala, and the different operations you can perform on them. By the end of this lesson, you will be well-equipped to implement and operate Linked Lists using Scala. Let's get started!

Understanding the Concept

A Linked List is a linear data structure similar to arrays. However, unlike arrays, they are not stored in contiguous memory locations. Each element in a Linked List is part of a node . A node comprises data and a reference (or link) to the next node in the sequence. This structure facilitates efficient insertions and deletions. The head is also an essential concept in Linked Lists. It is the first node in the list and serves as a reference to the entire list. An empty Linked List can be represented by a null reference or, more safely in Scala, by None when using Option[Node] . Singly linked lists often come up in coding interviews. Interviewers from tech giants, start-ups, and just about every company testing your coding abilities will pose challenges based on this concept. Singly linked lists are quite common in real-world applications. In fact, Scala's immutable List — one of the most widely used collections in Scala projects — is implemented as a singly linked list. They form excellent foundational knowledge for understanding doubly linked lists, which are chosen when bidirectional traversal is needed. A singly linked list contains nodes with a single link pointing to the next node, whereas a doubly linked list has nodes with links to both the next and the previous nodes.

Implementing Linked Lists - Creating Node

To begin implementing Linked Lists, we first need to understand the structure of a node, the building block of a Linked List. In Scala, we'll use a case class to serve as a blueprint for a node . A Node class mainly consists of data (the data you want to store) and next (the reference to the next node). In our case, we'll create a case class Node to store integer data, with a default value of None for the next node. Scala case class Node(var data: Int, var next: Option[Node] = None) case class Node(var data: Int, var next: Option[Node] = None) Fantastic! You now know how to set up a node in a Linked List.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Scala

case class Node(var data: Int, var next: Option[Node] = None)

Scala

class LinkedList {
  private var head: Option[Node] = None

  def append(data: Int): Unit = {
    val node = Node(data)

    head match {
      case None => head = Some(node)
      case Some(h) =>
        def findLast(current: Node): Node =
          current.next match {
            case None => current
            case Some(nextNode) => findLast(nextNode)
          }

        val last = findLast(h)
        last.next = Some(node)
    }
  }
}

class LinkedList {
  private var head: Option[Node] = None

  def append(data: Int): Unit = {
    val node = Node(data)

    head match {
      case None => head = Some(node)
      case Some(h) =>
        def findLast(current: Node): Node =
          current.next match {
            case None => current
            case Some(nextNode) => findLast(nextNode)
          }

        val last = findLast(h)
        last.next = Some(node)
    }
  }
}

Scala

def addFirst(data: Int): Unit = {
  val node = Node(data, head)
  head = Some(node)
}

def addFirst(data: Int): Unit = {
  val node = Node(data, head)
  head = Some(node)
}

Scala

def delete(data: Int): Unit = {
  head match {
    case None => // Do nothing
    case Some(h) if h.data == data =>
      head = h.next
    case Some(h) =>
      def deleteFrom(node: Node): Unit =
        node.next match {
          case Some(nextNode) if nextNode.data == data =>
            node.next = nextNode.next
          case Some(nextNode) =>
            deleteFrom(nextNode)
          case None => ()
        }

      deleteFrom(h)
  }
}

def delete(data: Int): Unit = {
  head match {
    case None => // Do nothing
    case Some(h) if h.data == data =>
      head = h.next
    case Some(h) =>
      def deleteFrom(node: Node): Unit =
        node.next match {
          case Some(nextNode) if nextNode.data == data =>
            node.next = nextNode.next
          case Some(nextNode) =>
            deleteFrom(nextNode)
          case None => ()
        }

      deleteFrom(h)
  }
}

Scala

class LinkedList {
  private var head: Option[Node] = None

  def append(data: Int): Unit = {
    val node = Node(data)

    head match {
      case None => head = Some(node)
      case Some(h) =>
        def findLast(current: Node): Node =
          current.next match {
            case None => current
            case Some(nextNode) => findLast(nextNode)
          }

        val last = findLast(h)
        last.next = Some(node)
    }
  }
}

Scala

def addFirst(data: Int): Unit = {
  val node = Node(data, head)
  head = Some(node)
}

Scala

def delete(data: Int): Unit = {
  head match {
    case None => // Do nothing
    case Some(h) if h.data == data =>
      head = h.next
    case Some(h) =>
      def deleteFrom(node: Node): Unit =
        node.next match {
          case Some(nextNode) if nextNode.data == data =>
            node.next = nextNode.next
          case Some(nextNode) =>
            deleteFrom(nextNode)
          case None => ()
        }

      deleteFrom(h)
  }
}

Introduction to Linked Lists

Understanding the Concept

Implementing Linked Lists - Creating Node

Join the 1M+ learners on CodeSignal

Implementing Linked Lists - Append Method

Implementing Linked Lists - AddFirst Method

Implementing Linked Lists - Delete Method

Complexity Analysis

Summary and What's Next