data structures - Stack - scala implementation/performance issue -

i've been looking @ scala-lang notes on various data structures , performance characteristics.

i have noticed immutable.stack has c (const.) complexity both appending , prepending, while mutable.stack stack has c complexity prepending , l (linear) complexity appending. surprised me bit.

i take it, "appending" means push() top of stack. , since complexities prepending , appending different, mean "prepending" in fact putting on bottom of stack? why perform better (c mutable) appending (l mutable)? , also, how can prepend stack? can't see method suitable in scaladoc.

edit.

as @Łukasz noted in comments, can prepend , append stack +: , :+ operators. question remains though - why prepending work better (faster) appending stack? should add bottom instead of pushing top?

it looks there mistake in table, or not something. if @ implementation, push both mutable , immutable stack takes constant time, , :+ both mutable , immutable takes linear time, because :+ coming seqlike in linear time, reasonable stack data structure

both mutable , immutable stacks using immutable list inside , using :: operation, constant. list has it's append operation l, it's no way stack can better

for immutable stack is:

def push[b >: a](elem: b): stack[b] = new stack(elem :: elems) 

and mutable is:

def push(elem: a): this.type = { elems = elem :: elems; } 

also please notice immutable stack deprecated since 2.11

p.s. checked latest sources of 2.12, seems code didn't change since 2.11

p.p.s. couldn't find insert implementation stack, , looking @ table seems weird stack among immutable structures can insert data, i'd guess l column should have been in append column