Связанные списки
Связанные списки реализованы в 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Ссылки: