The fastest way to implement a queue in Java

Question

I wanted to know what changes should be made to this code to reduce its execution time.

import java.util.*; public class ExamPeekableQueueImpl <E extends Comparable<E>> implements ExamPeekableQueue<E> { LinkedList<E> li = new LinkedList<E>(); public ExamPeekableQueueImpl(){ } public void enqueue(E e){ if(li.isEmpty()){ li.add(0, e); } else li.add(e); } public E dequeue(){ li.pollFirst(); return null; } public void printlist(){ System.out.println(li.toString()); } public E peekMedian(){ int var = (((li.size())/2)+1); Collections.sort(li); //Integer var2 = li.get(var); System.out.println("the median is:" + li.get(var-1)); return null; } public E peekMaximum(){ Collections.sort(li); System.out.println("the maximum is:" + li.getLast()); return null; } public E peekMinimum(){ Collections.sort(li); System.out.println("the minimum is:" + li.getFirst()); return null; } public int size(){ li.size(); return 0; } } 

I also wanted to know if queues , LinkedList or ArrayList implementation queues , or any other data structure.

Answer 1

You currently have O (1) for insertion and O (nlogn) for getMin/getMax/getMedian . You can move the log file from the getters to the insertion part using a sorted data structure. Or you can leave the insert as it is and optimize getMin/getMax by doing a linear search on the list and just keeping the minimum value. For getMedian you have nothing to do, as you need a sorted set for this.

Further optimization will consist in saving min / max and updating two values ​​at each insertion stage. This will not have a (not permanent) change on insertion and will reduce your getMin/getMax to O (1). (thanks to Tedil )

The same goes for getMedian , where you will store a sorted list in parallel with your linked list. Then you can simply select the median middle of this list. Of course, this will change the insert time to O (logn) or worse (depending on the list you use), and also double the amount of storage space. Thus, this is a more expensive optimization than for getMin/getMax .

Answer 2

This is a busy question.

What operation do you want to speed up? Your peekMin / Max / Mid code is pretty slow right now because you have to sort every time. However, your embed code is fast. If you want, you can save the sorted data structure inside. This will slow down your insertion method, but speed up your search methods. It is often so fast that this happens between operations. It is rarely possible to simply speed up ALL operations on a certain data structure, so you need to choose which operations you consider common and optimize them.

It's about what operations you want to speed up.

Answer 3

To answer your last question. check out this topic to learn about the differences between using arrays or a linked list in structures.

Also, as a recommendation when declaring structures, always use the interface as a type so that you can change the implementation without affecting the functionality.

Answer 4

It depends.

In fact, most of the people answering / commenting do not realize that Collections.sort gives N performance in an almost sorted list. (N log N is performance if the list is not sorted.)

As others have said, perhaps you should sort when you change the list, rather than reading the list. Perhaps you should use an ordered set rather than a list. (If you really need a list to store multiple copies of an element, consider using an ordered map and make the number of occurrences a value.)

You can also consider creating an object that stores the collection and keeps track of the minimum and maximum value without sorting it. This will work well if searching for medians is rare or if you can get away from having a median.

Answer 5

In the peekMaximum () and peekMinimum () methods, instead of sorting the LinkedList, you can directly use the Collections.max(li) and Collections.min(li) methods.

I think that this will save time spent sorting the list.