Move specific items to the end of a list

Question

I have an ArrayList in Java:

{"deleteItem", "createitem", "exportitem", "deleteItems", "createItems"}

I want to move all string which contains delete to the end of the list, so I would get the next:

{"createitem", "exportitem", "createItems", "deleteItem", "deleteItems"}`

I can create two sublists - one for the words which contain the 'delete' word, and one for the others, and then merge them, but I search for a more efficient way.

Define "efficient"? Do you actually mean "elegant"? I have an inkling that performance is not important here, so perhaps maintainability is more important? If you really mean efficient, is space or time more important? — Duncan Jones, Apr 07 '14 at 07:31

score 13 · Accepted Answer · edited Jan 17 '19 at 16:34

13

Use custom Comparator:

List<String> strings = Arrays.asList(
        "deleteItem", "createitem", "exportitem", "deleteItems", "createItems"
        );
Comparator<String> comparator = new Comparator<String>() {
    @Override
    public int compare(final String o1, final String o2) {
        if (o1.contains("delete") && !o2.contains("delete")) {
            return 1;
        }else if (!o1.contains("delete") && o2.contains("delete")) {
            return -1;
        }
        return 0;
    }
};
Collections.sort(strings, comparator);
System.out.println(strings);

edited Jan 17 '19 at 16:34

Naman

27,789
26
218
353

answered Apr 07 '14 at 07:27

Kristjan Veskimäe

992
5
16

what if those `delete<>` strings should be sorted as well? i'm guessing since the author specified `deleteItem` before `deleteItems` – mangusta Apr 07 '14 at 07:42
I guess you can just replace return 0; in method compare with return o1.compareTo(o2); – Kristjan Veskimäe Apr 07 '14 at 07:49

score 3 · Answer 2 · answered Apr 07 '14 at 07:23

3

If you want something efficient and need to remove elements in the beginning and middle of a List I would suggest using a LinkedList instead of a array list. That would avoid rewriting the underlying array for each remove operation.

Then, you simply iterate on the list, calling remove and addLast for any string that contains delete.

Of course, this is only OK if there is nothing preventing you from replacing your ArrayList with a LinkedList.

answered Apr 07 '14 at 07:23

Pierre Rust

2,474
18
15

Ha, you are faster than me... :-) – Rong Nguyen Apr 07 '14 at 07:26
Sometime you need luck :) – Pierre Rust Apr 07 '14 at 07:27

Raul Guiu · Answer 3 · 2014-04-07T10:50:30.027

1

You only want to put the elements with delete at the end of the list so ordering is O(nlogn) while we could do this in one pass, in O(n) (although using a new list). We could create a new LinkedLIst and pass through the original list adding the elements with "delete" at the end and the others at the begginging.

    LinkedList<String> orderedList = new LinkedList<>();
    for(String e:originalList){
        if (e.indexOf("delete")>=0) {
            orderedList.addLast(e);
        } else {
            orderedList.addFirst(e);
        }
    }

This is faster than sorting.

edited Apr 07 '14 at 10:50

answered Apr 07 '14 at 07:22

Raul Guiu

2,374
22
37

How is it efficient than solution provided by OP ? – Jabir Apr 07 '14 at 07:23
Sorting, O(nlogn). We rely inthe sorting implementation of the JVM, is fairly good, we dont need to reinvent the wheel. – Raul Guiu Apr 07 '14 at 07:38
But searching is O(n) and is his solution 2 searches and a join make is 3N but in Big Oh notation its O(n) correct me if i am wrong – Jabir Apr 07 '14 at 08:25
True, and you only need one search. If you dont care of the order of anything else. – Raul Guiu Apr 07 '14 at 08:37

Move specific items to the end of a list

3 Answers3

Linked