Comment insérer quelque chose à une position spécifique d'une liste LinkedList mutable?

Question

Encore une fois, cela semble être quelque chose qui devrait être évident.

Je voudrais insérer un élément dans une liste liée à un emplacement spécifique.

Dans un cas, c'est là un champ dans l'élément est inférieure à une certaine valeur, donc je peux le faire de cette façon:

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

... mais ce qui est vraiment une approche immuable déguisée en un mutable. Je ne pense pas que je puisse obtenir le noeud LinkedList qui correspond au point d'insertion, donc je ne peux pas jouer avec l'attribut "next".

Cela ne devrait pas être si difficile. La moitié du point des listes chaînées est si vous insérez des choses au milieu.

Je suis encore en train de jouer avec un générateur de compilateur (comme dans this question). Remplacer des listes avec des copies n'est pas la solution, car il y a beaucoup d'appels récursifs au cours desquels les listes sont délibérément modifiées, vous pouvez donc constater que certains des appels récursifs utilisent toujours les listes que vous venez de remplacer. Je veux vraiment des listes mutables, et des opérations mutables simples. Je suppose que je peux écrire mes propres cours de collection, mais je ne pense pas que le besoin soit aussi inhabituel. Quelqu'un a-t-il déjà mis en place des listes de liens multilingues «appropriées»?

EDIT

Un peu plus en détail

j'aurais peut-être choisi un autre exemple. Généralement, j'ai une référence à l'élément par un autre chemin, et je veux insérer un nouvel élément dans l'une des listes chaînées sur lesquelles cet élément est activé (je serais content que l'élément soit dans une liste chaînée en tant que start)

Dans l'implémentation Java naïve que je commence, l'élément lui-même contient un champ next (que je peux ensuite manipuler). Dans le cas Scala LinkedList, le noeud de la liste liée contient une référence à l'élément, et donc, étant donné l'élément, je ne trouve pas facilement le noeud LinkedList et donc le champ suivant. Je peux à nouveau parcourir la liste, mais cela pourrait être très long.

Il peut être utile de supposer une liste DoublyLinkedList et de supprimer l'élément en tant qu'opération, car il est plus clair que cette traversée n'est pas nécessaire et doit donc être évitée. Dans ce cas, supposons que j'ai trouvé l'élément par d'autres moyens que de parcourir la liste chaînée. Je veux maintenant supprimer l'élément. Dans le cas Java/naïf, les pointeurs avant et arrière font partie de l'élément. Dans le cas des collections Scala, il existe un noeud DoublyLinkedList quelque part qui contient une référence à mon élément. Mais je ne peux pas passer de l'élément à ce nœud sans avoir à parcourir à nouveau la liste. Les pensées aléatoires suivent: Je vais quelque part en mélangeant un trait qui définit un champ suivant (pour mon cas singulièrement lié). Ce trait peut prendre en charge l'itération sur les objets de la liste, par exemple. Mais cela m'aiderait seulement pour les éléments qui sont sur une liste à la fois et j'ai des objets qui sont sur trois (avec, actuellement, trois différents "prochains" pointeurs appelés des choses comme "nezt", "across" et "down") .

Je ne veux pas une liste de nœuds pointant vers des éléments, je veux une liste d'éléments qui sont des nœuds (c'est-à-dire qui ont un champ suivant).

Answer 1

Malheureusement, LinkedList n'implémente pas le Buffer, donc il n'y a pas AFAIK un bon moyen de le faire dès la sortie de la boîte. En réalité, vous avez accès au champ next, vous pouvez donc écrire le vôtre. Quelque chose comme ça (avertissement, avertissement !; non testé, code de bas niveau!):

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 
    } 

(Vous pouvez ajouter un cas particulier pour myList être vide, et pour l'insertion avant le premier élément mais vous obtenez le. idée

Modifier après clarification: Ne pas conserver les copies des éléments, garder des copies de la liste commençant par cet élément (c'est ce que last est.) Ensuite, écrivez une conversion implicite d'une liste de votre truc de choix à la Si vous ne dupliquez pas les méthodes de collections dans votre élément, vous obtenez toute la puissance de la bibliothèque de collections et toute la commodité syntaxique d'avoir un élément avec un pointeur suivant, avec o nly une allocation d'objet supplémentaire comme inconvénient.

Bien sûr, vous pouvez toujours implémenter n'importe quelle structure de données de bas niveau si vous voulez réinventer la roue pour qu'elle corresponde mieux à votre voiture (pour ainsi dire).

Answer 2

Version non polie: Insère other dans l la première fois que le prédicat p est vrai.

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) 

Answer 3

Pourquoi les gens vont à ce problème?

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) 

Bien sûr, cela ne répond pas à la question après la clarification, mais je pense que l'idée de Rex Kerr des conversions implicites pourrait être la voie à suivre ici. Cela, ou simplement ajouter un .elem avant toute méthode utilisant la valeur. En fait, voici l'implicite:

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