scala – 如何在可变LinkedList的特定位置插入内容？
|
同样,这似乎应该是显而易见的.
我想将一个元素插入到特定位置的链表中. 在一种情况下,这是元素中的字段小于某个值的位置,所以我可以这样做： def Add(act:Elem):Unit = {
val (before,after) = myList.partition(elem.n >= _.n)
myList = (before :+ act) ++ after
}
……但这实际上是一种伪装成可变的方法.我不认为我可以到达与插入点对应的LinkedList节点,所以我不能搞乱“next”属性. 这应该不是那么困难.链表的一半是你在中间插入的东西. 我还在搞乱编译器生成器(如this question).用副本替换列表并不是这样做的方法,因为有很多递归调用,在这些调用期间,列表被故意修改,因此您可能会发现某些递归调用仍在使用您刚刚替换的列表. 我真的想要可变列表和直接的可变操作.我想我可以编写自己的集合类,但我认为不需要那么不寻常.任何人已经实施了“适当的”可交换链接列表了吗？ 编辑 更多细节 我应该选择一个不同的例子.通常情况下,我通过其他路径获得了对元素的引用,并且我想在此元素所在的链接列表之一中插入一个新元素(我很高兴将元素放在一个链接列表中作为开始) 在我开始的朴素Java实现中,元素本身包含一个下一个字段(然后我可以操作). 在Scala LinkedList的情况下,链表节点包含对元素的引用,因此,给定元素,我不能轻易找到LinkedList节点,因此下一个字段. 假设DoublyLinkedList并删除元素作为我想要的操作可能会有所帮助,因为它更加清晰,因此不需要遍历,因此应该避免.所以在这种情况下,假设我通过其他方式找到了元素,而不是遍历链表.我现在想删除该元素.在Java / naive的情况下,后向和前向指针是元素的一部分.在Scala集合的情况下,有一个DoublyLinkedList节点,其中包含对我的元素的引用.但是,如果不再遍历列表,我就无法从元素转到该节点. 随机的想法如下：我通过混合定义下一个字段的Trait来获得某个地方(对于我单独链接的案例).例如,该特征可能支持迭代列表中的对象.但这对我来说只有一次列在一个列表上的元素有帮助,而且我有三个对象(目前有三个不同的“下一个”指针称为“nezt”,“across”和“down”) . 我不希望指向元素的节点列表,我想要一个节点元素列表(即有一个下一个字段). 解决方法
不幸的是,LinkedList没有实现Buffer,因此没有AFAIK是开箱即用的好方法.但是,您实际上可以访问下一个字段,因此您可以编写自己的字段.像这样的东西(警告,未经测试！;警告,低级代码！)：
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添加一个特殊情况为空,并在第一个元素之前插入.但您明白了 澄清后编辑：不要保留元素的副本;保留从该元素开始的列表副本. (这就是最后的结果.)然后从你选择的东西列表到头部东西本身写一个隐式转换.除非您复制元素中的集合方法,否则您将获得集合库的所有功能以及具有下一个指针的元素的所有语法便利,只有额外的对象分配作为缺陷. 当然,如果你想重新发明轮子以便它更适合你的汽车(可以这么说),你总是可以实现你想要的任何低级数据结构. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |