Again, this seems like something that should be obvious.
I would like to insert an element into a linked list at a specific position.
In one case, this is where a field in the element is less than a certain value, so I can do it this way:
def Add(act:Elem):Unit = {
val (before, after) = myList.partition(elem.n >= _.n)
myList = (before :+ act) ++ after
}
... but this is really an immutable approach disguised as a mutable one. I don't think I can get at the LinkedList node that corresponds to the insertion point, so I can't mess with the "next" attribute.
It shouldn't be this difficult. Half the point of linked lists is so you insert things in the middle.
I'm still messing with a compiler generator (as in this question). Replacing lists with copies is just not the way to do this, as there are many recursive calls during which the lists are quite deliberately modified, so you may find that some of the recursive calls are still using the lists you just replaced.
I really want mutable lists, and straightforward mutable operations. I guess I can write my own collection classes, but I don't think the need is that unusual. Anyone implemented "proper" multable linked lists already?
EDIT
Some more detail
I should have perhaps chosen a different example. Typically, I've got a reference to the element by some other route, and I want to insert an new element in one of the linked lists this element is on (I'd be happy with the element being in one linked list as a start)
In the naive Java implementation I'm starting with, the element itself contains a next
field (which I can then manipulate).
In the Scala LinkedList case, the linked list node contains a reference to the element, and so, given the element, I cannot easily find the LinkedList node and so the next field. I can traverse the list again, but it might be very long.
It might help to assume a DoublyLinkedList and deleting the element as the operation I want to do, as it's clearer then that traversal isn't needed and so should be avoided. So in that case, assume I have found the element by some other means than traversing the linked list. I now want to delete the element. In the Java/naive case, the back and forward pointers are part of the element. In the Scala collections case, there's a DoublyLinkedList node somewhere that contains a reference to my element. But I can't go from element to that node without traversing the list again.
Random thoughts follow: I'm getting somewhere by mixing in a Trait that defines a next field (for my singly linked case). This trait might support iterating over the objects in the list, for example. But that would help me only for elements that are on one list at a time and I have objects that are on three (with, currently, three different "next" pointers called things like "nezt", "across" and "down").
I don't want a List of开发者_Python百科 Nodes pointing to Elements, I wanta List of Elements that are Nodes (ie. have a next field).
Unfortunately, LinkedList
is does not implement Buffer
, so there isn't AFAIK a good way to do this out of the box. You actually do have access to the next
field, however, so you can write your own. Something like this (warning, untested!; warning, low level code!):
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
}
(You might want to add a special case for myList
being empty, and for insertion before the first element. But you get the idea
Edit after clarification: Don't keep copies of the elements; keep copies of the list starting at that element. (That's what last
is.) Then write an implicit conversion from a list of your thingy of choice to the head thingy itself. Unless you duplicate the collections methods in your element, you get all the power of the collections library and all the syntactic convenience of having an element with a next pointer, with only an extra object allocation as drawback.
Of course, you can always implement any low-level data structure you want, if you want to reinvent the wheel so that it fits your car better (so to speak).
Why are people going to such trouble?
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)
Of course, this doesn't answer the question after clarification, but I think Rex Kerr's idea of implicit conversions might be the way to go here. That, or just add a .elem
before any method using the value. In fact, here's the implicit:
implicit def linkedListToA[A](ll: LinkedList[A]): A = ll.elem
Unpolished version: Inserts other
into l
the first time that the predicate p
is true.
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)
精彩评论