Wie füge ich etwas an einer bestimmten Position einer veränderbaren LinkedList ein?

Question

Auch dies sollte eigentlich eine Selbstverständlichkeit sein.

Ich möchte ein Element an einer bestimmten Position in eine verknüpfte Liste einfügen.

In einem Fall ist dies der Fall, wenn ein Feld im Element einen bestimmten Wert unterschreitet, so dass ich es auf diese Weise tun kann:

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

... aber das ist in Wirklichkeit ein unveränderlicher Ansatz, getarnt als ein veränderlicher. Ich glaube nicht, dass ich auf den LinkedList-Knoten zugreifen kann, der dem Einfügepunkt entspricht, also kann ich das Attribut "next" nicht verändern.

Es sollte nicht so schwierig sein. Der halbe Sinn von verknüpften Listen ist, dass man Dinge in der Mitte einfügen kann.

Ich bin immer noch mit einem Compiler-Generator (wie in diese Frage ). Das Ersetzen von Listen durch Kopien ist einfach nicht der richtige Weg, da es viele rekursive Aufrufe gibt, bei denen die Listen ganz bewusst geändert werden, so dass Sie feststellen können, dass einige der rekursiven Aufrufe immer noch die Listen verwenden, die Sie gerade ersetzt haben.

Ich möchte wirklich veränderbare Listen und unkomplizierte veränderbare Operationen. Ich denke, ich kann meine eigenen Auflistungsklassen schreiben, aber ich glaube nicht, dass der Bedarf so ungewöhnlich ist. Hat jemand bereits "richtige" multable Linked Lists implementiert?

EDIT

Einige weitere Details

Ich hätte vielleicht ein anderes Beispiel wählen sollen. Normalerweise habe ich einen Verweis auf das Element über einen anderen Weg, und ich möchte ein neues Element in eine der verknüpften Listen einfügen, in denen sich dieses Element befindet (ich wäre mit dem Element in einer verknüpften Liste für den Anfang zufrieden)

In der naiven Java-Implementierung, mit der ich beginne, enthält das Element selbst eine next Feld (das ich dann manipulieren kann).

Im Fall von Scala LinkedList enthält der LinkedList-Knoten einen Verweis auf das Element, und so kann ich angesichts des Elements den LinkedList-Knoten und damit das nächste Feld nicht ohne weiteres finden. Ich kann die Liste erneut durchlaufen, aber das könnte sehr lang werden.

Es könnte helfen, eine DoublyLinkedList und das Löschen des Elements als die Operation, die ich tun möchte, anzunehmen, da es dann klarer ist, dass Traversal nicht erforderlich ist und daher vermieden werden sollte. Nehmen wir also an, dass ich das Element auf andere Weise gefunden habe, als durch die verknüpfte Liste zu traversieren. Nun möchte ich das Element löschen. Im Fall von Java/naive sind die Rück- und Vorwärtszeiger Teil des Elements. Im Fall der Scala-Sammlungen gibt es irgendwo einen DoublyLinkedList-Knoten, der einen Verweis auf mein Element enthält. Aber ich kann nicht vom Element zu diesem Knoten gehen, ohne die Liste erneut zu durchlaufen.

Es folgen zufällige Gedanken: Ich erreiche etwas, indem ich einen Trait einmische, der ein nächstes Feld definiert (für meinen einfach verknüpften Fall). Dieser Trait könnte z.B. die Iteration über die Objekte in der Liste unterstützen. Aber das würde mir nur für Elemente, die auf einer Liste zu einem Zeitpunkt und ich habe Objekte, die auf drei (mit, derzeit, drei verschiedene "nächste" Zeiger namens Dinge wie "nezt", "across" und "down") sind helfen.

Ich möchte keine Liste von Knoten, die auf Elemente verweisen, ich möchte eine Liste von Elementen, die Knoten sind (d.h. ein nächstes Feld haben).

Answer 1

Leider, LinkedList ist nicht implementiert Buffer AFAIK gibt es also keine gute Möglichkeit, dies direkt aus der Box heraus zu tun. Sie tatsächlich tun haben Zugang zu den next Feld, so dass Sie Ihr eigenes schreiben können. Etwa so (Achtung, ungetestet!; Achtung, Low-Level-Code!):

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
  }

(Möglicherweise sollten Sie einen Sonderfall für myList leer ist und vor dem ersten Element eingefügt werden soll. Aber Sie verstehen die Idee

Edit nach Klärung: Behalten Sie keine Kopien der Elemente, sondern Kopien der Liste, die mit diesem Element beginnt. (Das ist es, was last ist.) Schreiben Sie dann eine implizite Konvertierung von einer Liste des Dings Ihrer Wahl zum Kopf-Ding selbst. Es sei denn, Sie duplizieren die Sammlungen Methoden in Ihrem Element, erhalten Sie alle die Macht der Sammlungen Bibliothek und alle die syntaktische Bequemlichkeit, ein Element mit einem nächsten Zeiger, mit nur eine zusätzliche Objektzuweisung als Nachteil.

Natürlich können Sie jede beliebige Low-Level-Datenstruktur implementieren, wenn Sie das Rad neu erfinden wollen, damit es besser zu Ihrem Auto passt (sozusagen).

Answer 2

Warum machen sich die Menschen solche Mühe?

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)

Das beantwortet natürlich nicht die Frage nach der Klärung, aber ich denke, Rex Kerrs Idee der impliziten Konvertierung könnte hier der richtige Weg sein. Das, oder fügen Sie einfach eine .elem vor jeder Methode, die den Wert verwendet. In der Tat, hier ist die implizite:

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

Answer 3

Ungeschliffene Version: Einsätze other en l das erste Mal, dass das Prädikat p wahr ist.

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)