Getting last of LinkedHashSet

Question

I'd like to store a list of numbers 1,2,3,4 - (lets start with List<Integer>)

I'd like to make sure numbers are unique (ok, fine, Set<Integer>)

I'd like to guarantee order (ok ... LinkedHashSet<Integer>)

I'd like to get the last element from the list ..

What would be the simplest way to get the last number inserted into the LinkedHashSet<Integer> please?

Hard to believe that java's LinkedHashSet offers you an iterator for the first, but not the last...but it appears to see also http://stackoverflow.com/questions/1936462 which lists some 3rd party libs — rogerdpack, Dec 09 '15 at 07:19

score 16 · Answer 1 · edited Feb 08 '21 at 23:33

16

There's no prebaked option for this. There's two off-the-cuff options, and neither are good:

The Order n approach:

public <E> E getLast(Collection<E> c) {
    E last = null;
    for(E e : c) last = e;
    return last;
}

Yuck! But there's also an Order 1 approach:

class CachedLinkedHashSet<E> extends LinkedHashSet<E> {
    private E last = null;

    @Override
    public boolean add(E e) {
        last = e;
        return super.add(e);
    }
    public E getLast() {
        return last;
    }

}

This is off the cuff, so there might be a subtle bug in it, and for sure this isn't thread safe or anything. Your needs may vary and lead you to one approach over another.

edited Feb 08 '21 at 23:33

talz

1,004
9
22

answered Dec 24 '12 at 17:19

corsiKa

81,495
25
153
204

5

The cached approach makes removal O(n). – SLaks Dec 24 '12 at 17:21
1

@SLaks Not really. The two approaches technically have a different contract. The `getLast` method just tells you the last element added. It makes no guarantee that element is still in the list. – corsiKa Dec 24 '12 at 17:23
3

But that's probably not what the OP wants. – SLaks Dec 24 '12 at 17:24
1

It is exactly what was asked for. "What would be the simplest way to get the last number inserted". I'm looking into a more developed solution anyway, since even if you document that fact it still may take users by surprise. – corsiKa Dec 24 '12 at 17:29
Guava offers a utility for the first approach: http://docs.guava-libraries.googlecode.com/git-history/v18.0/javadoc/com/google/common/collect/Iterables.html#getLast(java.lang.Iterable) – Brett Okken Apr 08 '15 at 19:39
1

unfortunately the second example doesn't compile ("method overriding collision after erasure" or what not) so I suppose you'd have to rolll your own that wraps some other data structures (as user2179737's answer) or possibly use 3rd party libs to do the same, as http://stackoverflow.com/questions/1936462/java-linkedhashmap-get-first-or-last-entry mentions) FWIW – rogerdpack Dec 09 '15 at 07:25
2

@rogerdpack if I had to guess, it's because I didn't `` the `extends LinkedHashSet` - like I said there's probably a subtle bug - I just wrote that off the top of my head... apparently on Christmas Eve haha... explains why I didn't compile it! :) – corsiKa Dec 09 '15 at 07:56
1

Change `extends LinkedHashSet` to `extends LinkedHashSet` and it compiles. As a possible improvement, update `last` only when add() returns true (i.e. the element is actually new). – Stefan Reich Feb 19 '19 at 10:30
This is a good option, but we lose `O(1)` the moment we also want to support deletes. – avp Sep 29 '22 at 00:14

score 9 · Answer 2 · answered May 24 '14 at 09:32

9

With java-8, you could get a sequential Stream of the LinkedHashSet, skip the first n-1 elements and get the last one.

Integer lastInteger = set.stream().skip(s.size()-1).findFirst().get();

answered May 24 '14 at 09:32

Alexis C.

91,686
21
171
177

4

As best I can tell, this would be no different than iterating over all the elements. – Brett Okken Apr 07 '15 at 22:10
According to the open jdk source, the spliterator is a default spliterator based on the iterator. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/LinkedHashSet.java?av=f#193 – Brett Okken Apr 08 '15 at 03:22
@BrettOkken I'm not very familiar with the source code yet, but I guess the interesting part is more there: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/stream/SliceOps.java#SliceOps.makeRef%28java.util.stream.AbstractPipeline%2Clong%2Clong%29 . It seems that a new Sink is initialized to the min(skip, size) before so I'm not sure if it iterates over all the elements. – Alexis C. Apr 08 '15 at 07:34
2

As best I can tell, the "skip" functionality is based on the trySplit method of the Spliterator. In the case of the LinkedHashSet, this uses the IteratorSpliterator, which simply iterates over the values. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/Spliterators.java?av=f#1784 – Brett Okken Apr 08 '15 at 18:31
@BrettOkken The doc states that skip is a cheap operation. This code source is quite a mess to read, but you're basically saying that skip is not a O(1) operation? Although the question there is what is the simplest way to get the last element, and I think this one is the simplest :-) – Alexis C. Apr 08 '15 at 18:58
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/74750/discussion-between-alexis-c-and-brett-okken). – Alexis C. Apr 08 '15 at 19:12
This is no different than iterating over all the elements, it is just a one-liner to do so, which is nicer in my opinion. – Simon Forsberg Mar 10 '16 at 15:13

score 5 · Accepted Answer · answered Dec 24 '12 at 17:22

5

First of all, I agree with corsiKa's solution which suggests an extended version of LinkedHashSet class that contains a pointer to the last element. However, you can use a traditional way by consuming some space for an array:

set.toArray()[ set.size()-1 ] // returns the last element.

answered Dec 24 '12 at 17:22

Juvanis

25,802
5
69
87

17

I am afraid this needs to go all the way down to `AbstractCollection.toArray()` which does hard copy of the whole set just because of getting last element. Very inefficient. – Vojtěch Feb 21 '14 at 08:52
2

This appears to offer no benefit over simply iterating over all the entries to get the last (as @corsiKa suggests below). – Brett Okken Apr 08 '15 at 19:39

score 3 · Answer 4 · answered Apr 29 '23 at 15:01

3

Since Java 21 LinkedHashSet has getLast() method:

jshell> var set = new LinkedHashSet<>(List.of(1,2,3,4,5));
set ==> [1, 2, 3, 4, 5]

jshell> set.getLast();
$2 ==> 5

answered Apr 29 '23 at 15:01

ZhekaKozlov

36,558
20
126
155

score -1 · Answer 5 · answered Jun 21 '15 at 20:52

-1

here is a implementation that adds method to access the last entry O(1):

LinkedHashSetEx.java

enjoy...

answered Jun 21 '15 at 20:52

user2179737

493
3
6

3

Please don't rely on third party links for answers. This link could stop working at any minute in which case your answer would be useless. – Simon Forsberg Mar 10 '16 at 15:12
Note that this example uses reflection to access private members of `java.util.LinkedHashMap` which may result in a security exception. – corsiKa Sep 20 '18 at 20:45

score -5 · Answer 6 · answered Dec 24 '12 at 17:19

-5

Sets are independent of order.We cannot access element by index.If you require last element,

1)create new ArrayList(Set)

The last element of an arrayList can be accessed easily

answered Dec 24 '12 at 17:19

Renjith

3,274
19
39

6

The question specifically mentions LinkedHashSet which does have an innate order (defined in the javadoc as the order in which unique items are added to the set) – Simon B May 10 '14 at 10:14

Getting last of LinkedHashSet

6 Answers6

Linked