Reassurance on collections

[Tim Bant]

Hi all,

Just a quick query on collections....

Regarding the following code:

18: var list = new ArrayList˂String˃();
19: list.add(null);
20: list.add(null);
21: 
22: var set = new HashSet˂˃(list);
23: set.add(null);
24:
25: var queue = new LinkedList˂˃(set);
26: queue.add(null);
27:
28: var tree = new TreeSet˂˃(queue);
29: tree.add(null);

Am I right in thinking that:

- Line 22 is a Hashset of String type? So is the equivalent of doing the following?

HashSet˂String˃ set = new HashSet˂˃(list);

- Line 25: How can a linkedList take in a hashset, given that LinkedList is a sub type of List?

And LinkedList is basically an ArrayList but is quicker to add/remove but slower to read than ArrayList?

Thanks!

[Mike Simmons]

Tim Bant wrote:Am I right in thinking that:

- Line 22 is a Hashset of String type? So is the equivalent of doing the following?

HashSet˂String˃ set = new HashSet˂˃(list);

Yes, exactly.  Normally we'd actually prefer the declaration to be Set<String> rather than HashSet<String>, but the var declaration picks up the exact type that is known to the compiler.

Tim Bant wrote:- Line 25: How can a linkedList take in a hashset, given that LinkedList is a sub type of List?

Look at the constructor of LinkedList - it can take in any Collection.  It doesn't need to be the same type - the constructor will basically just iterate through all the entries and make a new LinkedList with those entries, regardless of where they came from, as long as it's some kind of Collection.

Tim Bant wrote:And LinkedList is basically an ArrayList but is quicker to add/remove but slower to read than ArrayList?

Roughly, yes.  Adding and removing from the end of an ArrayList is fast, but anywhere else is painfully slow.  And with LinkedList, get() and set() are very slow except at the beginning or end, but if you use an iterator (or a foreach loop) it's still quite fast.

To be fair, "vary slow" and "painfully slow" are relative.  In many cases they will still be quite fast enough for you to never notice a difference unless you measure carefully.  But if the list gets really big, they get slower and slower, for the operations I mentioned.

[Campbell Ritchie]

Tim Bant wrote:. . . And LinkedList is basically an ArrayList but is quicker to add/remove but slower to read than ArrayList?

Thanks!

No. It is basically a List, but is implemented completely differently from array lists.
A linked list allows very fast insertion and removal at the current location where you are looking at the moment (called the cursor position); unless you are at the ends of the List, the Java® LinkedList class uses its Iterator to do that insertion or removal. I think you need to use this method to get an Iterator that can insert elements.
Finding elements by index is much faster for an array list; a linked list has to traverse itself to find that index.
The documentation for ArrayList tells you that most of its operations run approximately in linear time.

[Paul Clapham]

If, in your future Java career, you find yourself using a List where you need to add and remove entries anywhere other than at the end, please post back here and let us know. I've been working in Java for over 20 years and that's never happened to me.

[Mike Simmons]

Yeah, it's pretty rare to actually need a LinkedList for anything, nowadays.  But in Java 1.5 they added java.util.Queue and various new implementations, and nowadays there's usually a better implementation available, if you need a queue.  I also think I might have used LinkedList once or twice when building a list and then needing to delete some elements, iterating through one at a time and deleting an element if it met some condition.  That sort of made sense back when memory was potentially a limitation.  Nowadays it's always simpler to just build a new list and throw away the old one.  Or use Streams and filter() to accomplish the same thing more elegantly.  The frequency I need LinkedList has gone from "very rare" to "nonexistent", pretty much.

[Campbell Ritchie]

Mike Simmons wrote:Yeah, it's pretty rare to actually need a LinkedList for anything, nowadays. . .

The only reason I can think of is that you are doing a Data Structures and Algorithms module and they tell  you to implement a linked list as an assignment.
Yes, LinkedList implements Queue, but in 2006 (Java6), they introduced ArrayDeque, which is a better implementation of Queue.

[Tim Bant]

Thanks guys - its just that the exam mentions about LinkedList. I guess like a lot of things in the exam, some is rarely used in reality.

[Piet Souris]

Well, here's one who uses linkedlists quite frequently. For instance with the scrolling graph of a function,  where many points are added at the start and superfluous points removed from the end. Performance problems? Never.

[Tim Bant]

Thanks all - so because Set List and Queue all come under Collection, you can mix and match those 3?

[Campbell Ritchie]

Tim Bant wrote:. . . Set List and Queue . . . you can mix and match those 3?

No; they all perform different functions and behave differently.

[Rob Spoor]

But the constructors of most collection implementations do support any type of collection, so you can easily create a list from a set and a set from a deque, etc.

[Mike Simmons]

[Written before seeing Rob's last post above - I'm replying to Campbell, really.]

Well, they have some things in common, and other things that are different.  The stuff that they have in common is what's described in the Collection interface.  Or Iterable, or the Object class.  Their differences are described in the specific interfaces List, Queue, Set and in the specific implementations like ArrayList, LinkedList,  ArrayDeque, ArrayBlockingQueue,  HashSet, etc.

In this specific case, if you're looking at the constructor

LinkedList(Collection<? extends E> c)

then since it says the argument is a Collection, in order to use that constructor you can use [i]any[i] collection.  So right there, as the argument to the LinkedList constructor, all your Lists and Sets and Queues are pretty much interchangeable - you could use any of them.  But in other places you may need a List or Set or a more specific type - if that's what the API says you need.

Note also that even where they are "interchangeable", they may behave differently.  A List or a TreeSet and a HashSet will all put their elements in different orders, so a new LinkedList(list) will hav a different order than a new LinkedList(hashSet) or a new LinkedList(treeSet).  That's consistent with the fact that the documentation for Collection doesn't guarantee any articular order, while the docs for List and TreeSet do make specific (conflicting) guarantees.

[Campbell Ritchie]

Mike Simmons wrote:. . . if you're looking at the constructor . . .

I wasn't.

. . . even where they are "interchangeable", they may behave differently. . . .

You use a List as a List (sometimes also called a Sequence), you use a Set as a Set, and you use a Queue as a Queue. The Java™ Tutorials should explain the differences. Or your course should so do. Yes, there are instances where different types are interchangeable; you can make a Set from a Queue, a Queue from a List, and a List from a Set. Just as you can take all the people on a bus and put them on a ferry, put all the people from a ferry onto a train, or all the people from a train onto a bus (well, a very big bus). But trains aren't buses and buses aren't ferries and ferries aren't trains.

[Tim Holloway]

The old Commodore Amiga computer's kernel was so heavily invested in linked lists that there were doubly-linked list functions built in as part of the kernel code. They pointed to executable tasks, to libraries, and well, any other sort of resource that might have multiple instances. The Amiga Exec was in effect, the first commercially popular OOP OS, although it predated OOP languages such as C++. I had a nice talk with Carl Sassenrath at a convention once where I asked him about that, and he admitted that OOP wasn't a specific design goal, but it worked well for him.

A Sequence is any collection that has a native ordering. That is, there exists an operation that, when applied repeatedly, always returns elements of the collection in a repeatable way. Arrays and Lists are 2 Sequences that are basic to Java, Basic Maps (hashes) are not.

Sequences can thus generally have any element retrievable by an integral index as the sequence key* and be sources for enumeration functions such as the foreach operator.

===
* with greater or lesser efficiency.

[Campbell Ritchie]

The earliest OO language was Simula67, which came out in, would you believe, 1967.

[Tim Holloway]

Campbell Ritchie wrote:The earliest OO language was Simula67, which came out in, would you believe, 1967.

And, f just for giggles you'd like to play with it, apparently you can run it on the Hercules IBM mainframe emulator program:

https://www.edelweb.eu/Simula/

I strongly suspect that Hercules on a Raspberry Pi could outperform native IBM mainframes used in the US Space program.

[Carey Brown]

Campbell Ritchie wrote:The earliest OO language was Simula67, which came out in, would you believe, 1967.

The earliest one I knew of was SmallTalk.

[Mike Simmons]

Campbell Ritchie wrote:

Mike Simmons wrote:. . . if you're looking at the constructor . . .

I wasn't.

But original poster Tim Bant was, clearly.  I didn't think I needed to quote the whole previous thread.  I made the partly-informed guess that this was the reason he thought they were interchangeable - and in that specific place, they are.  Mostly. . In many other places, they are not.

[Tim Holloway]

Carey Brown wrote:

Campbell Ritchie wrote:The earliest OO language was Simula67, which came out in, would you believe, 1967.

The earliest one I knew of was SmallTalk.

Simula preceded Smalltalk.

I used Smalltalk to help prototype a scripting language for a project I was working on in the late 1980's (or was it 1680's? ).

One of the reasons I was at the convention where I met Sassenrath was to find Beta testers for a Smalltalk I was creating for the Amiga. Alas, the whole Amiga market was soon to collapse, so I never got further.


Wirth's book carried the same weight for its day as the GoF book has done more recently. In fact, one wag suggested a parody edition: Programs - Algorithms = Data Structures.