A few questions about adding an element to collection.mutable.LinkedList

On Wed, Jan 11, 2012 at 05:47, Christian M. wrote:
> According to the API, there is only the operator :+ which "Appends an
> element to this linked list", but returns "a new collection of type
> That consisting of all elements of this linked list followed by elem."
>
> My questions are:
>
> 1. Given that the list is mutable, why is this the default behavior of
> the "append" operator?

That behavior comes from scala.collection.Seq, and is inherited by
scala.collection.mutable.Seq and scala.collection.immutable.Seq. If
the semantics were different, it would make scala.collection.Seq
useless. So, why use the same name to mean different things when you
can have different names for it?

> 2. What is the way to append an element as in
> java.util.linked.LinkedList.add()?

See trait Growable.

> 3. If the method for 2. exists, why it's not listed in the API and if
> it does not exists - how is it justified?

LinkedList is mutable, not
growable.

Actually, LinkedList should really have been private, as it is used as
basis for more proper collections. Avoid it, and use one of the Buffer
collections if you want mutable collections.

Daniel, thank you for your answer -- I think I got it, I should use
ListBuffer.

But concerning your (actually rhetorical) question:

> So, why use the same name to mean different things when you
> can have different names for it?

Apart from the fact, that the same names can mean different things in
different contexts (see overloading, e.g.), I could revert your
question and ask, if it is the Scala-way of naming, then why does the
apparently different data structure collection.mutable.LinkedList has
the same name as java.util.LinkedList? That's exactly the root of my
problem. I could think, that ListBuffer relates to LinkedList just as
StringBuffer relates to String in Java, but String is immutable in
Java, which is not the case for c.m.LinkedList. So at the moment I
really don't see any logic behind splitting the types into
c.m.LinkedList and c.m.ListBuffer... Could you elaborate on it or
refer me to some literature?

Thanks in advance!

On Wed, Jan 11, 2012 at 9:15 AM, Christian M. <chrmllr@gmail.com> wrote:

Apart from the fact, that the same names can mean different things in
different contexts

Someone using scala.collection.Seq has no idea if Seq is mutable or immutable; the "context" is lost. If I don't know whether +: will mutate a list of not, then it means I either need to overload each method separately for mutable.Seq vs. immutable.Seq, create a defensive copy of the list, or write my code assuming the worst case (mutability).

With regard to +: and :+, they always return a new copy of the
collection. They do not mutate. For example:

scala> val ab = mutable.ArrayBuffer[String]("fsad")
ab: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer(fsad)

scala> "xxx" +: ab
res5: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer(xxx,
fasd)

scala> ab :+ "yyy"
res6: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer(fasd,
yyy)

scala> ab
res7: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer(fasd)

On Jan 11, 11:03 am, Tom Switzer wrote:
> On Wed, Jan 11, 2012 at 9:15 AM, Christian M. wrote:
> > Apart from the fact, that the same names can mean different things in
> > different contexts
>
> Someone using scala.collection.Seq has no idea if Seq is mutable or
> immutable; the "context" is lost. If I don't know whether +: will mutate a
> list of not, then it means I either need to overload each method separately
> for mutable.Seq vs. immutable.Seq, create a defensive copy of the list, or
> write my code assuming the worst case (mutability).

On Wed, Jan 11, 2012 at 12:15, Christian M. wrote:
> Daniel, thank you for your answer -- I think I got it, I should use
> ListBuffer.
>
> But concerning your (actually rhetorical) question:
>
>> So, why use the same name to mean different things when you
>> can have different names for it?
>
> Apart from the fact, that the same names can mean different things in
> different contexts (see overloading, e.g.), I could revert your

"Effective Java" specifically warns people not to add overloads where
the meaning is different, and, instead, use different method names.

> question and ask, if it is the Scala-way of naming, then why does the
> apparently different data structure collection.mutable.LinkedList has
> the same name as java.util.LinkedList? That's exactly the root of my
> problem. I could think, that ListBuffer relates to LinkedList just as
> StringBuffer relates to String in Java, but String is immutable in
> Java, which is not the case for c.m.LinkedList. So at the moment I
> really don't see any logic behind splitting the types into
> c.m.LinkedList and c.m.ListBuffer... Could you elaborate on it or
> refer me to some literature?

The name linked list refers to a common data structure, which has
thousands of implementations (my preferred one is the one on linux
kernel :). To say something is a linked list imparts very little
meaning on the exact details, aside from the fact that there's a
pointer from one node to the other.

That said, I personally think LinkedList ought to be private. Almost
always when someone wants a mutable sequence, the answer will be
Array, *Buffer, Queue or Stack.

> Actually, LinkedList should really have been private, as it is used as
> basis for more proper collections. Avoid it, and use one of the Buffer
> collections if you want mutable collections.

But with ListBuffer, how do you insert or remove in the middle of the
buffer? For example, with LinkedList, here is how you remove every
second element:

val lst = scala.collection.mutable.LinkedList(1, -2, 7, -9)
var cur = lst
while (cur != Nil && cur.next != Nil) {
cur.next = cur.next.next
cur = cur.next
}

(Not very functional, I know, but it's a mutable list after all.)

What's the ListBuffer equivalent?

Thanks,

Cay

On Thu, Jan 12, 2012 at 13:34, Cay Horstmann wrote:
>> Actually, LinkedList should really have been private, as it is used as
>> basis for more proper collections. Avoid it, and use one of the Buffer
>> collections if you want mutable collections.
>
> But with ListBuffer, how do you insert or remove in the middle of the
> buffer? For example, with LinkedList, here is how you remove every
> second element:
>
> val lst = scala.collection.mutable.LinkedList(1, -2, 7, -9)
> var cur = lst
> while (cur != Nil && cur.next != Nil) {
>  cur.next = cur.next.next
>  cur = cur.next
> }
>
> (Not very functional, I know, but it's a mutable list after all.)
>
> What's the ListBuffer equivalent?

There isn't an equivalent, but, in my opinion, when you get to need
this kind of operation, you are better off writing it yourself instead
of depending on a collection. You can always extend or provide a
conversion to Traversable, Iterable or Seq to get extra functionality.
Traversable and Iterable, in particular, are very easy to implement.

Most use cases in my own experience (I'm not making global
generalizations, just providing an individual point) are handled by
PriorityQueue, SortedSet or SortedMap.

On Thu, Jan 12, 2012 at 11:15 AM, Daniel Sobral wrote:
> On Thu, Jan 12, 2012 at 13:34, Cay Horstmann wrote:
>>> Actually, LinkedList should really have been private, as it is used as
>>> basis for more proper collections. Avoid it, and use one of the Buffer
>>> collections if you want mutable collections.
>>
>> But with ListBuffer, how do you insert or remove in the middle of the
>> buffer? For example, with LinkedList, here is how you remove every
>> second element:
>>
>> val lst = scala.collection.mutable.LinkedList(1, -2, 7, -9)
>> var cur = lst
>> while (cur != Nil && cur.next != Nil) {
>>  cur.next = cur.next.next
>>  cur = cur.next
>> }
>>
>> (Not very functional, I know, but it's a mutable list after all.)
>>
>> What's the ListBuffer equivalent?
>
> There isn't an equivalent, but, in my opinion, when you get to need
> this kind of operation, you are better off writing it yourself instead
> of depending on a collection. You can always extend or provide a
> conversion to Traversable, Iterable or Seq to get extra functionality.
> Traversable and Iterable, in particular, are very easy to implement.
>
> Most use cases in my own experience (I'm not making global
> generalizations, just providing an individual point) are handled by
> PriorityQueue, SortedSet or SortedMap.

I agree with you. I can't remember the last time I actually wanted to
muck in the middle of a linked list. Except of course in our CS2
course where we subject the poor students to all sorts of linked list
internals, because we've always done it like that. Anyway, if a
convert from Java or C++ asks about the equivalent of
java.util.LinkedList or STL list (which I have never used either
outside that CS2 course), it seems legitimate to steer them to
LinkedList.

Cheers,

Cay