如何在可變鏈表的特定位置插入某些內容？

Question

再次，這似乎是應該是顯而易見的事情。

我想插入一個元素到鏈接列表的特定位置。

在一種情況下，這就是在元件的區域小於一定的值，所以我可以這樣來做：

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

...但是這確實是僞裝成一個不可變的方法一個可變的。我不認爲我可以得到與插入點相對應的LinkedList節點，所以我不能混淆「下一個」屬性。

它不應該這麼難。鏈表的一半是你插入中間的東西。

我還在搞編譯器生成器（如在this question）。用副本替換列表並不是做這件事的方法，因爲有許多遞歸調用，在這些調用期間列表被非常謹慎地修改，因此您可能會發現某些遞歸調用仍在使用剛剛替換的列表。

我真的想要可變列表和直接的可變操作。我想我可以寫自己的收藏課，但我不認爲這種需求是不尋常的。任何人都已經實施了「適當的」可變錶鏈表？

EDIT

一些更詳細

我應該也許選擇了不同的例子。通常情況下，我已經通過其他路由引用了該元素，並且想要在此元素所在的鏈接列表之一中插入一個新元素（我很高興元素在一個鏈表中作爲開始）

在我開始的天真Java實現中，元素本身包含一個next字段（然後我可以操作）。

在Scala LinkedList的情況下，鏈表節點包含對元素的引用，所以，給定元素後，我無法輕鬆找到LinkedList節點，因此下一個字段。 我可以再次遍歷列表，但可能會很長。

它可能有助於假設一個DoublyLinkedList並刪除元素作爲我想要做的操作，因爲它更清楚，那麼遍歷是不需要的，所以應該避免。所以在這種情況下，假設我已經通過除遍歷鏈表之外的其他方法找到元素。我現在想要刪除元素。在Java /天真的情況下，後向和前向指針是元素的一部分。在Scala集合的情況下，有一個DoublyLinkedList節點包含對我的元素的引用。但是如果不再遍歷列表，我無法從元素轉到該節點。

隨機想法如下：我通過混合定義下一個字段的特徵（用於單個鏈接的情況）來獲得某處。例如，此特徵可能支持迭代列表中的對象。但是，這樣做只會幫助我一次處理一個列表中的元素，而且我有三個對象（目前有三個不同的「下一個」指針，稱爲「nezt」，「across」和「down」）。 。

我不想要一個指向元素的節點列表，我想要一個元素列表是節點（即有下一個字段）。

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是。）然後寫一個從你選擇的列表中的隱式轉換到除非你在你的元素中複製集合方法，否則你將獲得集合庫的所有能力，並且擁有帶有下一個指針的元素的所有語法上的便利，o最後一個額外的對象分配作爲缺點。

當然，如果你想重新發明車輪以便它更適合你的車（可以這麼說），你總是可以實現你想要的任何低級數據結構。

Answer 2

未拋光版本：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) 

Answer 3

爲什麼人們會這麼麻煩？

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