2
\$\begingroup\$

I have three ways of reordering a list (think baseball order) and I am sure you can come up with more. What is a the best way?

For example if input is list is 1,2,3,4 and current is 3 then the output should be 3,4,1,2. Another example list: 1,2,3,4 and current 4 output is 4,1,2,3.

public void reOrder(List<String> list, String current) {

        if (list.size() > 1) {
            for (int i = 0; i < list.size(); i++) {
                String host = list.remove(0);
                if (host.equals(current)) {
                    list.add(0, host);
                    break;
                }
                list.add(host);

            }
        }
    }

   public void reOrder2(List<String> list, String current) {

        if (list.size() > 1) {
            int indexOfWorkingHost = list.indexOf(current);
            if (indexOfWorkingHost != -1) {
                for (int i = 0; i < indexOfWorkingHost; i++) {
                    list.add(list.remove(0));
                }
            }
        }
    }

public void reOrder3(List<String> list, String current) {

    if (list.size() > 1) {
        List<String> tmpServers = new ArrayList<String>();
        tmpServers.addAll(list);
        for (String host : tmpServers) {
            if (host.equals(current)) {
                break;
            }
            String first = list.remove(0);
            list.add(first);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ You might consider other data structures, e.g. a ring buffer. \$\endgroup\$ – Landei Oct 14 '11 at 7:44
2
\$\begingroup\$

The first thing you need to do is define what you mean with "best". Fastest to execute? Most readable? Best Java-ness?

In any case neither solution is very "nice". The first one unecessarily removes the "current" item und re-adds it, the second one uses indexOf, thus indirectly has two loops, and finally the third one makes a copy of the list, which is even slower.

When using "low level" removing/adding and modification of the original list, I guess I'd do it like this (untested):

public void reOrder(List<String> list, String current) {
   int i = list.length;
   while (i-- > 0 && list.get(0) != current)
      list.add(list.remove(0));
}

(BTW, consider making use of the generics: public <T> void reOrder(List<T> list, T current) {...)

There is also a Java API function that does this (Collections.rotate), but it requires the index of the "current" element. If you have a "better" or more optimized why to get the index, other than the "left to right" search of indexOf (such as a binary search, or a map), then that would be a better solution.

In any case, using the current item's index instead of the item itself is something you should consider (depending on the the architecture of your project), because it generally not a good idea to have to search for the index of an item every time you do something with the list.

If speed is really a practical problem for you, then another thing you should check, is if you really need to reorder the actual list. There are ways just to create a "view" of the list in the desired order which would basically take virtually no additional time (especially it would be independently from the length of the list) to create and use.

\$\endgroup\$
1
\$\begingroup\$

Since there is a current, I'd imagine it's done via iterator.

Something among the lines:

for (Iterator<T> i = list.iterator(); i.hasNext(); ){
  if (current.equals(i.next()){
    i.remove();
    list.add(0, current);
    break;
  }
}

The code works perfectly for LinkedList, yet LinkLists do suck very bad b/c of the indirection on each iteration (heavily cache miss prone). ArrayList (and array back ones) will exhibit 2 times System.arrayCopy but they are the better type of List most of the time, and last but not least you might wish to have a look at ArrayDequeu.

Either way this is the best way to do in terms of speed and readability.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.