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

Floozy

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

Coolidge

Thanks, but I think I've misdirected you with my example. Please see my edit to the question – Floozy

@Paul - I think there's a better way to achieve what you want (see my modified answer). – Coolidge

Hmm. Implicit conversions sound promising. Let me go off and cogitate for a bit... – Floozy

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

Yung

When I run ll.next.insert(LinkedList(0)), ll is set to LinkedList(1, 2, 3, 0). (Scala 2.8.1; it works in 2.8.0, though.) – Himes

@Himes Good call. I opened a ticket: lampsvn.epfl.ch/trac/scala/ticket/4080. – Yung

Thanks, Daniel. By the way: Shouldn’t insert insert before the current position, e.g. ll.next.insert(LL(0)) give you a LL(1, 0, 2, 3)? Otherwise there wouldn’t be a way to insert at front. — OTOH, this is called prepend on ListBuffer whereas LB.insert takes an index… They really should give the LinkedList a complete API overhaul. – Himes

@Himes Actually that doesn't make any sense. When ll is pointing to the node whose value is 1. It is impossible for a method to change the value of ll, and an insert operation doesn't change values, only links, so even if you prepended the list to ll, ll would not be able to see the prepended part. – Yung

@Himes As for Buffer, that is a very different data structure, which enables a different set of methods. DoubleLinkedList, on the other hand, could certainly use a prepend method. As for overhaul, the major set of methods of all collections is defined by Traversable, Iterable, Set, Seq and Map. Class-specific methods aren't really a focus, and a few changes to them would certainly not qualify as "complete API overhaul". – Yung

@Daniel: Thanks for clarification; I think I believed that LinkedList was sentinel-headed for the very reason to ease this operation. Still, elem is mutable, so would be possible. (And shouldn’t that be the reason to use a mutable linked list? To have a container which you can pass around and on which you can easily insert and remove stuff at front?) – Himes

And, of course, a Buffer is different but for two data structures in the same package, I’d at least expect that they have the same behaviour in insert and not that one inserts before and the other inserts after the element. (Complete overhaul is too much, sure, but then, LinkedListLike.scala is not very long either…) – Himes

@Himes Ah, I understand your point now. Yes, that much is true, it would certainly be MUCH preferable if insert has the same behavior. Unfortunately, it is not possible. – Yung

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)

Himes

Thanks. I might have just moved the golf posts, but please see my edit to the question. – Floozy