How do I insert something at a specific position of a mutable LinkedList?

Question

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 Nodes pointing to Elements, I wanta List of Elements that are Nodes (ie. have a next field).

Answer 1

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).

Answer 2

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

Answer 3

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)