Jak wstawić coś w określonej pozycji z mutable LinkedList?

Question

Ponownie, wydaje się, że to coś, co powinno być oczywiste.

Chciałbym wstawić element do połączonej listy w określonej pozycji.

W jednym przypadku, to jest, gdy pole w elementu jest mniejsza niż określona wartość, więc mogę zrobić to w ten sposób:

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

... ale to jest naprawdę niezmienne podejście przebraniu zmienny. Nie sądzę, mogę uzyskać w węzeł LinkedList, który odpowiada punkt wstawiania, więc nie mogę zepsuć z "następny" atrybut.

To nie powinno być takie trudne. Połowa punktu połączonych list jest taka, że ​​wstawiasz rzeczy w środku.

Ciągle mam kłopot z generatorem kompilatorów (jak w this question). Zastępowanie list kopiami nie jest po prostu sposobem na to, ponieważ istnieje wiele wywołań rekursywnych, podczas których listy są celowo modyfikowane, więc niektóre rekurencyjne wywołania wciąż używają właśnie zamienionych list.

Naprawdę chcę listy zmienne i proste operacje zmienne. Myślę, że mogę napisać własne zajęcia z kolekcji, ale nie sądzę, że potrzeba jest taka niezwykła. Ktoś zaimplementował już "właściwe" listy z linkami wielostronnymi?

EDIT

Niektóre bardziej szczegółowo

I powinny być może wybrany inny przykład. Zazwyczaj mam odwołanie do elementu inną trasą i chcę wstawić nowy element na jednej z połączonych list, na których ten element jest włączony (byłbym zadowolony z elementu znajdującego się na jednej połączonej liście jako start)

W naiwnej implementacji języka Java, od której zaczynam, sam element zawiera pole next (które następnie można modyfikować).

W przypadku Scala LinkedList, połączony węzeł listy zawiera odniesienie do elementu, a zatem, biorąc pod uwagę element, nie mogę łatwo znaleźć węzła Lista odnośników, a więc następnego pola. Mogę ponownie przejść przez listę, ale może to być bardzo długa.

Pomocne może być założenie Podwójnej Linii Linii i usunięcie elementu jako operacji, którą chcę wykonać, ponieważ jest bardziej jasne, że przemieszczenie nie jest potrzebne i dlatego powinno się go unikać. W takim przypadku załóżmy, że znalazłem element w inny sposób niż przechodzenie przez połączoną listę. Teraz chcę usunąć ten element. W przypadku Java/naiwność wskaźniki tylny i przedni są częścią elementu. W przypadku kolekcji Scala istnieje gdzieś węzeł DoublyLinkedList zawierający odniesienie do mojego elementu. Ale nie mogę przejść od elementu do tego węzła bez ponownego przeglądania listy.

Losowe myśli następują: Dostaję się gdzieś poprzez zmieszanie cechy, która definiuje kolejne pole (dla mojej pojedynczo połączonej sprawy). Ta cecha może na przykład wspierać iterację obiektów na liście. Ale to pomogłoby mi tylko dla elementów znajdujących się na jednej liście na raz i mam obiekty, które są na trzech (z, obecnie, trzema różnymi "następnymi" wskaźnikami nazywanymi takimi jak "nezt", "w poprzek" i "w dół") .

Nie chcę listy węzłów wskazujących na elementy, chcę listę elementów, które są węzłami (tj. Mają następne pole).

Answer 1

Niestety, LinkedList nie implementuje Buffer, więc nie ma AFAIK dobrego sposobu na zrobienie tego po wyjęciu z pudełka. W rzeczywistości masz dostęp do pola , więc możesz pisać własne. Coś jak ten (ostrzeżenie, niesprawdzonych ostrzeżenia !;, niski poziom kodu!):

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 
    } 

(Możesz też dodać szczególny przypadek dla myList jest pusty, a do wstawiania przed pierwszym elemencie ale masz. pomysł

Edytuj po wyjaśnieniu: Nie przechowuj kopii elementów, zachowaj kopie listy zaczynając od tego elementu. (Taka jest last.) Następnie wpisz niejawną konwersję z listy twoich rzeczy do wyboru heady sam siebie, chyba że duplikujesz metody kolekcjonowania w swoim elemencie, otrzymujesz całą moc biblioteki zbiorów i całą syntaktyczną wygodę posiadania elementu z kolejnym wskaźnikiem, o na przykład dodatkowy przydział obiektu jako wady.

Oczywiście, zawsze możesz zaimplementować dowolną strukturę danych niskiego poziomu, jeśli chcesz odświeżyć koło tak, aby lepiej pasowało do Twojego samochodu (że tak powiem).

Answer 2

Wersja niepolakierowana: wstawia other w l po raz pierwszy, gdy predykat p jest prawdziwy.

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

Dlaczego ludzie mają takie kłopoty?

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) 

Oczywiście, to nie jest odpowiedź na pytanie, po wyjaśnienia, ale myślę, że pomysł Rex Kerr z ukrytych konwersji może być do zrobienia tutaj. To lub po prostu dodaj .elem przed jakąkolwiek metodą używającą tej wartości. W rzeczywistości mamy tu ukryte:

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