Is there a proper/best java structure to do 'last n things'

For a particular task I am working on, I want to keep track of the 'last 5 things' , where a thing is added when triggered.  Then, I will be comparing a difference between the 1st and last thing, as well as averaging something from each of the 5 things.

I would really love if there was a structure that let me just add a thing, and remove the first thing, so that the 6th thing added, then first removed, becomes an ordered arrangement of 5 things, a sliding window...

My existing solution looks like this, where i have an Array of "mythings".  I'm not interested in examining a difference if there are fewer than 5 things listed, just in pushing the old things out of the list as new ones are added once there are 5.

Is there a better structure to pull off this job, or better code (obviously a loop to shift the array items would be better than what is listed, anything else better?)   This same approach will be used elsewhere for looking at 'the last 30 things' and 'the last 100 things' at some point, so a solution that scales that way is desirable.

I dont believe that I nailed this one on my first shot at it, and would like to think some structure works better than a simple array with this code:

		public void addToListy(Thingy thing){
		int j
		if (listy.length <4){
		} else {

Open in new window

Who is Participating?
dpearsonConnect With a Mentor Commented:
It's quite different from an array where you replace the 5th element.

Let's make this concrete.  Let's assume it's a list of strings and they come in order A,B,C,D,E,F,G,H,I,J,K,L,M, etc.

With the array list the algorithm is
"add to the front of the list"
"if list too big, remove end of list"

So we get:
{ A }
{ B, A }            <-- added to front, so rest of list automatically "moves down"
{ C, B, A }
{ D, C, B, A }
{ E, D, C, B, A }
{ F, E, D, C, B }  <-- last 5 customers once F enters
{ G, F, E, D, C } <-- last 5 customers once G enters

If instead we just used an array and replace the 5th element we get:
{ A }
{ A, B }
{ A, B, C }
{ A, B, C, D }
{ A, B, C, D, E }
{ A, B, C, D, F } <-- Not the last 5 customers at all
{ A, B, C, D, G }

Is this making better sense now?

A Deque (or double ended queue) might meet your needs:

Deque<Thingy> listy = new ArrayDeque<Thingy>() ;

Then the code becomes:

int keep = 5 ;
listy.addFirst(thing) ;

if (listy.size() > keep)
    listy.removeLast() ;

Sounds more like you need a circular List or Queue
Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

GPrentice00Author Commented:
I think your size>keep part of the pseudocode idea might be backwards, if i understand what im reading elsewhere on Deque... If I understand this correctly, I would still be responsible for deleting the one end after adding to the other, but in using an array, does this mean that after thousands and thousands of calls, my actual indexes would be ie 5300 to 5304.  Or would it reinternalize to 0-n after deleting the first?  I dont actually need the indexes for doing a first-last comparison using the getfirst/getlast concepts, and i imagine an interator would be the way to traverse it to average the one set of data from the things...  but is an iterator faster or better than being able to for-loop from 0 to 4 every time ?? Could i hit a point where the actual indices grow to a out of control scenario and overflow regardless of choosing an indexless iterator process, just the underlaying structure itself not supporting adding one to the index anymore..

I tried to look at circular lists just now, but I dont see a connection to my example after a few minutes of hitting pages, or rather, they appear very involved codewise to keep track of the structure and im not sure i see how to make it a fixed size to otherwise just keep going around in otherwise some self-attending way of having an add(thing) that would just overwrite existing.   I will try looking some more, as it does seem possible to throw out an index incriment issue that might be in the deque array.  But thinking to a future application of this similar structure, I would at one point require the 'middle' element of an odd-number sized set.  With the arrays, I can jump to the middle directly if i new the endpoints - currently, by shuffling the array over, it would always be index 2 for me... or index 24 or index 49 etc...  but to find the middle would require traversing half of the list if I understand correctly.  and yes, thats not a qualification I wrote in the question, but, its a releated tie-to to help me try to connect an understanding to the structures, even though im still not really seeing a circular list example I can follow all the way with certainty...
I don't think the test is backwards.  It says "Once the deque has more than 5 members, drop the last one".

The indexes of the items in the queue won't grow.  In fact a queue is designed so you usually only get the items from the front or the back.

If you want to walk through all of the items you may be better off with just an ArrayList, which would be pretty similar code:

List<Thingy> listy = new ArrayList<Thingy>() ;

Then the code becomes:

int keep = 5 ;
listy.add(0, thing) ;   // Add to front of the list

if (listy.size() > keep)
    listy.remove(keep) ; // Remove the 5th item if the list gets too big

Then you can do things like:

Thingy first = listy.get(0) ;


// Iterate through the whole list - however long it currently is
for (Thingy thing : listy) {
    System.out.println(thing) ;


// More old school iterating by index
for (int i = 0 ;  i < listy.size() ; i++) {
     System.out.println(listy.get(i)) ;

GPrentice00Author Commented:
Perhaps our definition of first and last changes...

My definition of last is the new customer who walks into the bank and stands in line.  The first customer in line moves to the open teller.  The next customer in the bank becomes the new 'last'

I want to track the 5 "last" customers who walk through the door.
GPrentice00Author Commented:
thats why this is an issue, otherwise, a simple array would just work and keep replacing #5 for me, I would figure.  How is this dfiferent
GPrentice00Author Commented:
I see - if i pretend up is down, and left is right, then what is really last, would be the first.

I will try to shift my perspective and code this, see if it works.
Haha - yes the list is always showing "last 5 most recently seen in order" - which indeed means the most recent is first in the list, not last.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.