2 responded to comment
source | link

You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.

For your queue implementation in particular, you cannot simply rely on a mutable Java ArrayList. Take a look at some functional language and cons-cells for constructing immutable list datastructures. They allow you to simply keep track of start and end elements of your queue and derive a new queue object by reusing all cons-cells and simply adding a new one. The new object reuses the original cons-cells, but has a different end-pointer to the newly added cons cell.

Long story short: When writing immutable datastructures avoid copies and share structures instead.

In response to the comment about Java: All of this is language-agnostic. It is just that functional languages have been working with immutable datastructures for decades, whereas it is a relatively recent trend to add immutability to OO languages. All of this structure sharing, cons-cells, etc. is implementable in any programming language (well, Turing-complete that is).

You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.

For your queue implementation in particular, you cannot simply rely on a mutable Java ArrayList. Take a look at some functional language and cons-cells for constructing immutable list datastructures. They allow you to simply keep track of start and end elements of your queue and derive a new queue object by reusing all cons-cells and simply adding a new one. The new object reuses the original cons-cells, but has a different end-pointer to the newly added cons cell.

Long story short: When writing immutable datastructures avoid copies and share structures instead.

You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.

For your queue implementation in particular, you cannot simply rely on a mutable Java ArrayList. Take a look at some functional language and cons-cells for constructing immutable list datastructures. They allow you to simply keep track of start and end elements of your queue and derive a new queue object by reusing all cons-cells and simply adding a new one. The new object reuses the original cons-cells, but has a different end-pointer to the newly added cons cell.

Long story short: When writing immutable datastructures avoid copies and share structures instead.

In response to the comment about Java: All of this is language-agnostic. It is just that functional languages have been working with immutable datastructures for decades, whereas it is a relatively recent trend to add immutability to OO languages. All of this structure sharing, cons-cells, etc. is implementable in any programming language (well, Turing-complete that is).

1
source | link

You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.

For your queue implementation in particular, you cannot simply rely on a mutable Java ArrayList. Take a look at some functional language and cons-cells for constructing immutable list datastructures. They allow you to simply keep track of start and end elements of your queue and derive a new queue object by reusing all cons-cells and simply adding a new one. The new object reuses the original cons-cells, but has a different end-pointer to the newly added cons cell.

Long story short: When writing immutable datastructures avoid copies and share structures instead.