如何在可变 LinkedList 的特定位置插入内容？

Question

同样，这似乎是显而易见的事情。

我想将一个元素插入链表中的特定位置。

在一种情况下，元素中的字段小于某个值，所以我可以这样做：

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

...但这实际上是一种伪装成可变方法的不可变方法。我认为我无法获取与插入点相对应的 LinkedList 节点，因此我不能弄乱“next”属性。

不应该这么困难。链表的一半意义在于你可以在中间插入东西。

我仍在搞乱编译器生成器（如 这个问题）。用副本替换列表并不是执行此操作的方法，因为有许多递归调用期间列表被故意修改，因此您可能会发现某些递归调用仍在使用您刚刚替换的列表。

我真的想要可变列表和简单的可变操作。我想我可以编写自己的集合类，但我不认为这种需要是不寻常的。有人已经实现了“正确的”多链表吗？

编辑

更多细节

我也许应该选择一个不同的例子。通常，我通过其他途径获得了对该元素的引用，并且我想在该元素所在的链接列表之一中插入一个新元素（我很高兴该元素作为一个链接列表位于一个链接列表中） start)

在我开始的简单 Java 实现中，元素本身包含一个 next 字段（然后我可以对其进行操作）。

在 Scala LinkedList 情况下，链表节点包含对元素的引用，因此，给定元素，我无法轻松找到 LinkedList 节点以及下一个字段。 我可以再次遍历该列表，但它可能会很长。

假设一个 DoublyLinkedList 并删除元素作为我想要执行的操作可能会有所帮助，因为更清楚的是不需要遍历，因此应该避免。因此，在这种情况下，假设我通过遍历链表之外的其他方式找到了该元素。我现在想删除该元素。在 Java/naive 情况下，后向和前向指针是元素的一部分。在 Scala 集合的情况下，某处有一个 DoublyLinkedList 节点，其中包含对我的元素的引用。但如果不再次遍历列表，我就无法从元素转到该节点。

随机的想法如下：我通过混合定义下一个字段的特征（对于我的单链接案例）来达到某个目的。例如，此特征可能支持迭代列表中的对象。但这只会对一次位于一个列表上的元素有帮助，并且我的对象位于三个列表上（目前，三个不同的“下一个”指针称为“nezt”、“across”和“down”） 。

我不需要指向元素的节点列表，我想要一个作为节点的元素列表（即有一个下一个字段）。

Answer 1

不幸的是，LinkedList 没有实现 Buffer，因此据我所知，没有一个开箱即用的好方法。然而，您实际上确实可以访问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。）然后从您的事物列表中编写隐式转换。除非您在元素中复制集合方法，否则您将获得集合库的所有功能以及具有下一个指针的元素的所有语法便利，只有额外的对象分配作为缺点

。当然，如果您想重新发明轮子以使其更好地适合您的汽车（可以这么说），您始终可以实现您想要的任何低级数据结构。

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)

当然，这并不能回答澄清后的问题，但我认为 Rex Kerr 的隐式转换想法可能是解决这个问题的方法。或者在使用该值的任何方法之前添加一个 .elem 。事实上，这是隐含的：

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

Answer 3

未完善版本：当谓词 p 第一次为 true 时，将 other 插入到 l 中。

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)