How can I implement inserting element in the middle of DoubleLinkedList without coping it? In general I want to find some element in the collection and then insert a new one after it.
There is method DoubleLinkedList.insert but I'm not quite sure how it works. In the documentation it's described this way:
Insert linked list that at current position of this linked list
But what is the current position in the linked list? How can I set it?
I want to have O(1) insertion time.
To insert element in the middle of DoubleLinkedList you first to find your 'middle' and then make insertion:
val list = mutable.DoubleLinkedList(...)
list.next.next....insert(insertion)
For the first, you can't use insert to insert element, because it takes a DoubleLinkedList as parameter
def insert(that: DoubleLinkedList[A]): Unit
just use indexWhere and apply methods, for example replacing 30 with 3:
yourlist(yourlist.indexWhere(_ == 30)) = 3
Use span for separating the collection into the initial elements that hold a condition and those where the first item does not hold; e.g
val (l,r) = DoubleLinkedList(1,2,3,4,5).span(_ != 3)
l = DoubleLinkedList(1, 2)
r = DoubleLinkedList(3, 4, 5)
Then replace value 3 with 33 like this
l ++ DoubleLinkedList(33) ++ r.tail
Note In Scala 2.11.6 run the REPL with -deprecation to notice a deprecation warning such as
warning: object DoubleLinkedList in package mutable is deprecated:
Low-level linked lists are deprecated.
