Связанные списки

Связанные списки реализованы в Scala в виде класса List

Однонаправленные связанные списки используются в тех случаях, когда необходимо эффективно добавлять элемент в начало списка, а также разделять список на головной элемент и "хвост" - временная сложность выполнения этих операций равна константе. Сложность большинства остальных операций - это O(N), включая вычисление размера списка.

Для того чтобы вычислить размер списка или добавить элемент в конец списка необходимо пройтись по всему списку. Временная сложность добавления или удаления элемента в заданном индексе может доходить до O(N) в случае индекса, близкого N.

Оценка:

• Заглавный элемент (headOption
  )
  • Время - O(1)
  • Память - O(1)
• Остаток списка без начального элемента (tailOption
  )
  • Время - O(1)
  • Память - O(1)
• Проверка списка на пустоту (isEmpty
  )
  • Время - O(1)
  • Память - O(1)
• Вычисление длины списка (length
  )
  • Время - O(n)
  • Память - O(n)
• Добавление в начало (prepend
  )
  • Время - O(1)
  • Память - O(1)
• Добавление в конец списка (append
  )
  • Время - O(n)
  • Память - O(n)
• Получение элемента по заданному индексу (get
  )
  • Время - O(n)
  • Память - O(n)
• Проверяет, содержит ли список заданный элемент (contains
  )
  • Время - O(n)
  • Память - O(n)
• Объединение двух списков (concat
  )
  • Время - O(n)
  • Память - O(n)
• Фильтрация элементов списка (filter
  )
  • Время - O(n)
  • Память - O(n)
• Преобразование элементов списка (map
  )
  • Время - O(n)
  • Память - O(n)
• Объединение элементов списка (fold
  )
  • Время - O(n)
  • Память - O(n)

Код:

enum LinkedList[+A]:
  case Nil
  case Cons(head: A, tail: LinkedList[A])

  lazy val headOption: Option[A] = this match
    case Nil        => None
    case Cons(h, _) => Some(h)

  lazy val tailOption: Option[LinkedList[A]] = this match
    case Nil           => None
    case Cons(_, tail) => Some(tail)

  lazy val isEmpty: Boolean = this match
    case Nil => true
    case _   => false

  lazy val length: Int = this match
    case Nil           => 0
    case Cons(_, tail) => 1 + tail.length

  def prepend[B >: A](b: B): LinkedList[B] = Cons(b, this)

  def append[B >: A](b: B): LinkedList[B] = this match
    case Nil              => Cons(b, Nil)
    case Cons(head, tail) => Cons(head, tail.append(b))
    
  def get(i: Int): Option[A] =
    if i < 0 then None
    else if i == 0 then headOption
    else tailOption.flatMap(_.get(i - 1))
    
  def contains[B >: A](x: B): Boolean = this match
    case Nil                        => false
    case Cons(head, _) if head == x => true
    case Cons(_, tail)              => tail.contains(x)    
    
  def concat[B >: A](list: LinkedList[B]): LinkedList[B] = this match
    case Nil              => list
    case Cons(head, tail) => Cons(head, tail.concat(list))  
    
  def filter(p: A => Boolean): LinkedList[A] = this match
    case Nil                         => Nil
    case Cons(head, tail) if p(head) => Cons(head, tail.filter(p))
    case Cons(_, tail)               => tail.filter(p)

  def map[B](f: A => B): LinkedList[B] = this match
    case Nil              => Nil
    case Cons(head, tail) => Cons(f(head), tail.map(f))

  def fold[B](init: B)(op: (B, A) => B): B = this match
    case Nil              => init
    case Cons(head, tail) => tail.fold(op(init, head))(op)    
end LinkedList

Пример:

val emptyList: LinkedList[Int] = LinkedList.Nil
val nonEmptyList: LinkedList[Int] = LinkedList.Cons(2, LinkedList.Cons(1, LinkedList.Nil))

emptyList.headOption    // None
nonEmptyList.headOption // Some(2)

emptyList.tailOption    // None
nonEmptyList.tailOption // Some(Cons(1,Nil))

emptyList.isEmpty       // true
nonEmptyList.isEmpty    // false

emptyList.length        // 0
nonEmptyList.length     // 2

emptyList.prepend(5)    // Cons(5,Nil)
nonEmptyList.prepend(5) // Cons(5,Cons(2,Cons(1,Nil)))

emptyList.append(5)     // Cons(5,Nil)
nonEmptyList.append(5)  // Cons(2,Cons(1,Cons(5,Nil)))

emptyList.get(0)        // None
nonEmptyList.get(0)     // Some(2)
  
emptyList.contains(0)    // false
nonEmptyList.contains(2) // true
  
emptyList.concat(nonEmptyList)    // Cons(2,Cons(1,Nil))
nonEmptyList.concat(nonEmptyList) // Cons(2,Cons(1,Cons(2,Cons(1,Nil))))

emptyList.filter(_ % 2 == 0)    // Nil
nonEmptyList.filter(_ % 2 == 0) // Cons(2,Nil)

emptyList.map(_ + 1)            // Nil
nonEmptyList.map(_ + 1)         // Cons(3,Cons(2,Nil))

emptyList.fold(100)(_ + _)      // 100
nonEmptyList.fold(100)(_ + _)   // 103

Ссылки:

• Род Стивенс - Алгоритмы. Теория и практическое применение. Глава 3. Связанные списки
• Связанный список - Wikipedia
• Bhim P. Upadhyaya - Data Structures and Algorithms with Scala
• Scalacaster - List