CODEWITHSUNDEEP
javaqueue
Bhagirath N Sai
Bhagirath N Sai

Reputation: 199

Fastest Way To Implement A Queue in Java

I wanted to know what changes should I be making 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;
    }   
}

Also I wanted to know is whether for implementing queues, LinkedList is faster or ArrayList or any other data structure.

Upvotes: 4

Views: 4952

Answers (5)

Nirmalya
Nirmalya

Reputation: 205

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

I think that will save the time wasted to sort the list.

Upvotes: 0

Joe
Joe

Reputation: 8042

It depends.

Actually, one thing most people answering/commenting don't realize is that Collections.sort gives about N performance on a nearly sorted list. (N log N is the performance if the list is not at all sorted.)

As others, have said, maybe you should be sorting when you change the list rather than read the list. Maybe you should be using an Ordered Set rather than list. (If you really need a list to hold multiple copies of an item, consider using a Ordered Map and making the number of occurrences the value.)

You can also consider making a an object that stores the Collection and keeps track of the min and max without sorting it. This would work well if finding medians is rare or if you can get away from needing the median.

Upvotes: 0

Oleksi
Oleksi

Reputation: 13097

This is a loaded question.

What operation do you want to speed up? Right now, your peekMin/Max/Mid code is quite slow because you have to sort each time. However, your insert code is fast. If you want, you can maintain a sorted data structure internally. This would slow down your insert method, but speed up your peek methods. There is often a tradeoff of speed between operations like this. It's rare to be able to just speed up ALL the operations on some data structure, so you need to pick what operations you think are common, and optimize those.

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

Upvotes: 3

brimborium
brimborium

Reputation: 9512

Currently you have O(1) for insertion and O(nlogn) for getMin/getMax/getMedian. You can move the logn from the getters to the insertion part by using a sorted data structure. Or you can leave the insertion as it is and optimize getMin/getMax by doing a linear search through the list and just storing the minimal value. For getMedian there is nothing to do as you need a sorted set for that.

A further optimization would be to store the min/max and update the two values during each insertion step. This will not have any (non-constant) change on insertion and will reduce your getMin/getMax to O(1). (thanks to Tedil)

The same applies for getMedian, where you would keep a sorted list in parallel to your linked list. You can then simply pick the median out of the middle of that list. Of course this will change insertion time to O(logn) or worse (depending on the list you use) and will also double the amount of storage space. So it is a more expensive optimization than the one for getMin/getMax.

Upvotes: 2

Sednus
Sednus

Reputation: 2113

To answer your latter question. please take a look at this topic to learn about the differences between using arrays or linked list in structures.

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

Upvotes: 0

Related Questions