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

Question

Опять же, это похоже на то, что должно быть очевидным.

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ

Еще немного подробнее

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

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

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

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

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

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

Answer 1

К несчастью, LinkedList это не реализует Buffer так что AFAIK не является хорошим способом сделать это из коробки. У вас действительно есть доступ к 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 is.) Затем напишите неявное преобразование из списка ваших предпочтений в саму голову. Если вы не продублируете методы коллекций в своем элементе, вы получите всю мощь библиотеки коллекций и все синтаксическое удобство наличия элемента со следующим указателем, с дополнительным выделением объекта в качестве недостатка.

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

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)