Как вставить что-то в определенную позицию изменяемого списка LinkedList?

Опять же, это кажется чем-то очевидным.

Я хочу вставить элемент в связный список в определенную позицию.

В одном случае, когда поле в элементе меньше определенного значения, я могу сделать это так:

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

... но это действительно неизменяемый подход, замаскированный под изменяемый. Я не думаю, что смогу добраться до узла LinkedList, соответствующего точке вставки, поэтому я не могу работать с атрибутом "next".

Это не должно быть так сложно. Половина смысла связных списков в том, чтобы вставлять вещи в середину.

Я все еще вожусь с генератором компилятора (как в этом вопросе). Замена списков копиями - это просто не тот способ, которым можно это сделать, поскольку есть много рекурсивных вызовов, во время которых списки вполне сознательно модифицируются, так что вы можете обнаружить, что некоторые из рекурсивных вызовов все еще используют списки, которые вы только что заменили.

Мне действительно нужны изменяемые списки и простые изменяемые операции. Наверное, я могу написать свои собственные классы коллекций, но я не думаю, что эта потребность настолько необычна. Кто-нибудь уже реализовал "правильные" многосвязные списки?

EDIT

Еще немного деталей

Возможно, мне следовало выбрать другой пример. Как правило, у меня есть ссылка на элемент каким-то другим путем, и я хочу вставить новый элемент в один из связных списков, в которых этот элемент находится (для начала меня устроит, если элемент будет в одном связном списке)

В наивной реализации Java, с которой я начинаю, элемент сам содержит поле next (которым я могу затем манипулировать).

В случае Scala LinkedList узел связанного списка содержит ссылку на элемент, и поэтому, получив элемент, я не могу легко найти узел LinkedList и, соответственно, поле next. Я могу снова пройти по списку, но это может быть очень долго.

Возможно, поможет предположение о двойном списке LinkedList и удалении элемента в качестве операции, которую я хочу выполнить, так как тогда становится ясно, что обход не нужен и поэтому его следует избегать. Итак, в этом случае предположим, что я нашел элемент каким-то другим способом, кроме обхода связного списка. Теперь я хочу удалить этот элемент. В случае Java/naive указатели назад и вперед являются частью элемента. В случае коллекций Scala где-то есть узел DoublyLinkedList, который содержит ссылку на мой элемент. Но я не могу перейти от элемента к этому узлу без повторного обхода списка.

Далее следуют случайные мысли: У меня что-то получается, если я добавлю трейт, определяющий следующее поле (для моего односвязного случая). Этот трейт может поддерживать, например, итерацию по объектам в списке. Но это помогло бы мне только для элементов, которые находятся в одном списке одновременно, а у меня есть объекты, которые находятся в трех (с тремя различными указателями "next", которые называются "nezt", "across" и "down").

Я не хочу список узлов, указывающих на элементы, я хочу список элементов, которые являются узлами (т.е. имеют следующее поле).