Как мне вставить что-то в определенную позицию изменяемого LinkedList?

Question

Опять же, это кажется чем-то очевидным.

Я хотел бы вставить элемент в связанный список в определенной позиции.

В одном случае, это когда поле в элементе меньше определенного значения, поэтому я могу сделать это следующим образом:

def Add(act:Elem):Unit = {
    val (before, after) = myList.partition(elem.n >= _.n)
    myList = (before :+ act) ++ after
    }

... но это действительно неизменный подход, замаскированный под изменчивый. Я не думаю, что смогу добраться до узла LinkedList, который соответствует точке вставки, поэтому я не могу связываться с атрибутом «next».

Это не должно быть так сложно. Половина связанных списков состоит в том, что вы вставляете объекты посередине.

Я все еще работаю с генератором компилятора (как в этот вопрос ). Замена списков на копии просто не способ сделать это, так как существует много рекурсивных вызовов, во время которых списки изменяются преднамеренно, поэтому вы можете обнаружить, что некоторые из рекурсивных вызовов все еще используют списки, которые вы только что заменили.

Мне действительно нужны изменяемые списки и простые изменяемые операции. Я думаю, что могу написать свои собственные классы коллекций, но я не думаю, что это настолько необычно. Кто-нибудь уже реализовал "правильные" мультистабильные связанные списки?

EDIT

Немного подробнее

Возможно, я должен был выбрать другой пример. Как правило, у меня есть ссылка на элемент по какому-либо другому маршруту, и я хочу вставить новый элемент в один из связанных списков, в котором этот элемент включен (я был бы рад, если бы этот элемент был в одном связанном списке как старт)

В простой реализации Java, с которой я начинаю, сам элемент содержит поле next (которым я затем могу манипулировать).

В случае Scala LinkedList узел связанного списка содержит ссылку на элемент, и поэтому, учитывая элемент, я не могу легко найти узел LinkedList и, следовательно, следующее поле. Я снова могу просмотреть список, но он может быть очень длинным.

Это может помочь предположить DoublyLinkedList и удалить элемент в качестве операции, которую я хочу сделать, поскольку более ясно, что обход не требуется, и поэтому его следует избегать. Так что в этом случае, предположим, что я нашел элемент другими способами, чем обход связанного списка. Теперь я хочу удалить элемент. В случае Java / naive указатели назад и вперед являются частью элемента. В случае коллекций Scala где-то есть узел DoublyLinkedList, который содержит ссылку на мой элемент. Но я не могу перейти от элемента к этому узлу без повторного обхода списка.

Случайные мысли следуют: я добираюсь куда-то, смешивая в Черте, которая определяет следующее поле (для моего единственно связанного случая). Эта черта может поддерживать, например, перебор объектов в списке. Но это помогло бы мне только для элементов, которые находятся в одном списке за раз, и у меня есть объекты, которые находятся на трех (с, в настоящее время, тремя различными указателями «следующий», называемыми такими вещами, как «nezt», «поперек» и «вниз») .

Мне не нужен список узлов, указывающих на элементы, я хочу список элементов, которые являются узлами (т.е. имеют следующее поле).

Answer 1

К сожалению, LinkedList is не реализует Buffer, поэтому AFAIK не является хорошим способом сделать это из коробки. Однако на самом деле do имеет доступ к полю next, поэтому вы можете написать свой собственный. Примерно так (предупреждение, не проверено !; предупреждение, код низкого уровня!):

def Add(act: Elem) {
    var last = myList
    while (last.next ne null && last.next.n >= act.n) last = last.next
    var ins = LinkedList(act)
    ins.next = last.next
    last.next = ins
  }

(Возможно, вы захотите добавить специальный случай для myList пустым и для вставки перед первым элементом. Но вы поняли идею

Редактировать после уточнения: не хранить копии элементов; сохранить копии списка, начиная с этого элемента. (Вот что такое last.) Затем напишите неявное преобразование из списка ваших предпочтений в саму голову. Если вы не продублируете методы коллекций в своем элементе, вы получите всю мощь библиотеки коллекций и все синтаксическое удобство наличия элемента со следующим указателем, с дополнительным выделением объекта в качестве недостатка.

Конечно, вы всегда можете реализовать любую низкоуровневую структуру данных, если захотите заново изобрести колесо, чтобы оно лучше подходило вашему автомобилю (так сказать).

Answer 2

Почему люди идут на такие неприятности?

scala> LinkedList(1, 2, 3)
res21: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3)

scala> val ll = LinkedList(1, 2, 3)  
ll: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3)

scala> ll.next.insert(LinkedList(0))

scala> ll
res23: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 0, 3)

scala> ll.insert(LinkedList(-1, -2))

scala> ll
res25: scala.collection.mutable.LinkedList[Int] = LinkedList(1, -1, -2, 2, 0, 3)

Конечно, это не дает ответа на вопрос после разъяснения, но я думаю, что идея Рекс Керр о неявных преобразованиях могла бы быть здесь. Это, или просто добавьте .elem перед любым методом, использующим значение. На самом деле, вот неявное:

implicit def linkedListToA[A](ll: LinkedList[A]): A = ll.elem

Answer 3

Неполированная версия: вставляет other в l при первом использовании предиката p.

import scala.collection.mutable.LinkedList
import scala.annotation.tailrec

val list = LinkedList(1, 2, 3, 10, 11, 12)

def insertAfter[T](l: LinkedList[T], other: LinkedList[T], p: (T) => Boolean) {
  @tailrec
  def loop(x: LinkedList[T]) {
    if (p(x.head)) {
      other.next = x.next
      x.next = other
      return
    }
    if (x.next.isEmpty) {}
    else loop(x.next)
  }
  loop(l)
}

insertAfter(list, LinkedList(100), (_:Int) >= 10)