ArrayList in reverse order

Question

I need to start with the first occurence of the first element argument and end with the next occurence of the second argument, putting them in reverse order.

I.e.:

ArrayList<String> food

tomato cheese chips fruit pie butter tea buns

and the two arguments are chips and buns

the new ArrayList should be

buns tea butter pie fruit chips

this is what I've got, but when printed the arraylist is empty

public static void main (String[] args){

       ArrayList<String> food = new ArrayList<String>(); 
       food.add(new String("tomato")); 
       food.add(new String("cheese")); 
       food.add(new String("chips")); 
       food.add(new String("fruit"));
       food.add(new String("pie"));
       food.add(new String("butter"));
       food.add(new String("tea"));
       food.add(new String("buns"));

       ArrayList<String> f1 = reverseOrder(food,"chips","buns");

    }

    public static ArrayList<String> reverseOrder(ArrayList<String> a, String w1, String w2){

        ArrayList<String> food = new ArrayList<String>();

        int startingPos = 0;
        int endingPos = 0;

        boolean startAdding = false;

        for(int i=0; i<a.size(); i++){
            String n = a.get(i);

            if(n.equals(w1)){
                endingPos = i;
            }

            if(n.equals(w2)){
                startingPos = i;
            }

        }


        for(int j = startingPos; j<=endingPos; j--){
            String p = a.get(j);
            food.add(p);
        }


        System.out.print(food);

        return food;
    }

Answer 1

The problem has two parts. First we need to find the sublist that satisfies the condition. Once we have the sublist, we can use Collections.reverse(List<?> list) to reverse it.

First, find the sublist between two elements, inclusive. The main idea is to identify the indices of these two elements using indexOf, then call subList on them. But we need to keep in mind the indices might be in a different order than we thought.

private static <T> List<T> inclusiveSublist(List<T> src, T from, T to) {
    int start = src.indexOf(from), stop = src.indexOf(to);

    if (start != -1 && stop != -1) {
        // Successfully located both! But they could be in the "wrong" order
        if (start <= stop) 
             // Element from could appear before to in the list (Plus one to include the second element)
            return src.subList(start, 1 + stop);
        else // Or the other way around
            return src.sublist(stop, 1 + start);
    }

    // Return empty list if we cannot find both elements
    return Collections.emptyList();
}

Now all we need is to reverse the result of inclusiveSublist:

public static <T> List<T> inclusiveReverseSublist(List<T> src, T from, T to) {
    List<T> l = inclusiveSublist(src, from, to);
    Collections.reverse(l);
    return l;
}

And the test:

public static void main(String [] args) {
    List<String> src = new ArrayList<>();
    src.addAll(Arrays.asList("tomato cheese chips fruit pie butter tea buns".split("\\s")));
    System.out.println(src);
    System.out.println(inclusiveReverseSublist(src, "fruit", "buns"));
    System.out.println(inclusiveReverseSublist(src, "cheese", "tomato"));
}

About subList()

From the Java API doc, subList

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the returned list is empty.) The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional list operations supported by this list.

So the above code will actually modify the original list, and moving the System.out.println(src); to the bottom will confirm this.

Answer 2

The problem you are trying to solve is really two. First, you need to identify the range (indices) that you care about. Then perform the reverse in place.

You have the first part. The 2nd part can be done by repeatedly removing and inserting values, but I would recommend swapping instead.

ArrayList l; 
int begin, end;
//reverse everything from "begin" to "end".
while(begin<end){
    Object tmp = l.get(begin);
    l.set(begin, l.get(end));
    l.set(end, tmp);
    begin++;end--;
}

You should also know that Java Collections already gives you easy ways to reverse a list.

Collections.reverse(list);

Also, if you need different lists and not modify the original as you did, you can grab a sublist like this.

list.subList(fromIndex, toIndex)

With this, you can easily perform your task with a combination of the above.

Answer 3

This part of the code is wrong:

for(int j = startingPos; j<=endingPos; j--){
    String p = a.get(j);
    food.add(p);
}

Why? Some examples:

• Imagine that you pass these arguments ("tomato", "cheese") => the starting position will be 1 and the ending position will be 0. In the validation of your loop you have "starting with j=1 do the loop while j<=0" meaning that it will never enter in the cycle

• Imagine that you pass these arguments ("cheese", "tomato") => the starting position will be 0 and the ending position will be 1. In the validation of your loop you have "starting with j=0 do the loop while j<=1 and in each iteration reduce 1 to j" meaning that after the first iteration j=-1 and you will have an an index out of bounds exception

Here's a code, based on yours (for your better understanding), that will give you the result that you want:

      //this code is case sensitive
      public ArrayList<String> reverseOrder(ArrayList<String> food, String w1, String w2) {
        String startingEl = null;
        String endingEl = null;

        for(int i=0; i<food.size(); i++){
            String n = food.get(i);

            //verify if it's equal and if it's really the first occurrence
            if(n.equals(w1) && endingEl==null){
                endingEl = n;
            }

            //verify if it's equal and if it's really the first occurrence
            if(n.equals(w2) && startingEl==null){
                startingEl = n;
            }

            //if both are found, save some time by interrupting the loop
            if(startingEl!=null && endingEl!=null) break;
        }

        //Protect here your code in case of the first or last elements is not found

        ArrayList<String> food_reversed = new ArrayList<String>();
        food_reversed.add(0, startingEl);

        for(int j = (food.size()-1); j>=0; j--){
            String p = food.get(j);
            if(p==startingEl || p==endingEl) continue;
            food_reversed.add(p);
        }

        food_reversed.add(endingEl);


        System.out.println(food_reversed);

        return food_reversed;
    }

If I understood correctly the challenge, here's a different example of code to solve your problem:

    //this code is case sensitive, is not prepared for repeated string elements
    //and is not prepared if both arguments are exactly the same string
    //is not prepared in cases that the any of the string arguments doesn't exist in the food array
    //this code doesn't insert the same element reference on first and last element
    //This code is not the perfect solution cause as you see it has a lot of ails, but it's probably a good start for your to learn more about the subject
    import java.util.ArrayList;
    import java.util.Collections;

    public class QuestionOrderChallenge {
        ArrayList<String> food = new ArrayList<String>(); 

        public QuestionOrderChallenge() {
            food.add(new String("tomato")); 
            food.add(new String("cheese")); 
            food.add(new String("chips")); 
            food.add(new String("fruit"));
            food.add(new String("pie"));
            food.add(new String("butter"));
            food.add(new String("tea"));
            food.add(new String("buns"));

            ArrayList<String> a1 = reverseOrder(food,"chips","buns");
            ArrayList<String> a2 = reverseOrder(food,"pie","tea");
            ArrayList<String> a3 = reverseOrder(food,"tomato","cheese");

        }

        public ArrayList<String> reverseOrder(ArrayList<String> food, String last, String first) {
            ArrayList<String> reversed_food = new ArrayList<String>(food);
            reversed_food.remove(first);
            reversed_food.remove(last);
            Collections.reverse(reversed_food);
            reversed_food.add(0, first);
            reversed_food.add(last);

            System.out.println("Array ordered according to challenge: " + reversed_food);

            return reversed_food;
        }

        public static void main(String[] args) {
            new QuestionOrderChallenge();
        }

    }

If you want to have the same base challenge but then order Alphabetically, here's the code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class AlphabeticOrderChallenge {
    ArrayList<String> food = new ArrayList<String>(); 

    public AlphabeticOrderChallenge() {
        food.add(new String("tomato")); 
        food.add(new String("cheese")); 
        food.add(new String("chips")); 
        food.add(new String("fruit"));
        food.add(new String("pie"));
        food.add(new String("butter"));
        food.add(new String("tea"));
        food.add(new String("buns"));

        ArrayList<String> f1 = reverseOrder(food,"chips","buns");
        System.out.println("Array ordered according to challenge: " + f1);
    }

    public ArrayList<String> reverseOrder(ArrayList<String> food, String end, String begin) {
        Collections.sort(food, new ComparatorChallenge(end, begin));
        return food;
    }


    private class ComparatorChallenge implements Comparator {
        String endarg;
        String beginarg;

        public ComparatorChallenge(String beginarg, String endarg) {
            this.beginarg = beginarg.toUpperCase();
            this.endarg = endarg.toUpperCase();
        }

        @Override
        public int compare(Object arg0, Object arg1) {
            String a = ((String)arg0).toUpperCase();
            String b = ((String)arg1).toUpperCase();

            if(a.compareTo(endarg)==0 || b.compareTo(beginarg)==0) return -1;
            if(b.compareTo(endarg)==0 || a.compareTo(beginarg)==0) return 1;

            return b.compareTo(a);
        }
    }


    public static void main(String[] args) {
        new AlphabeticOrderChallenge();
    }

}

Answer 4

You can use indexOf and lastIndexOf to get the proper positions of the elements.

Those methods will return -1 if the element cannot be found, though, so just be aware of that.

public static void main(String[] args) throws Exception {
    List<String> food = Arrays.asList("tomato", "cheese", "chips", "fruit", "pie", "butter", "tea", "buns");

    ArrayList<String> lst = reverseOrder(food, "chips", "buns");
    System.out.println(lst);
}

private static ArrayList<String> reverseOrder(List<String> food, String start, String end) throws Exception {
    int startIndex = food.indexOf(start);
    if (startIndex < 0) {
        throw new Exception(start + " not found");
    }

    int endIndex = food.lastIndexOf(end);
    if (endIndex < 0) {
        throw new Exception(end + " not found");
    }

    ArrayList<String> lst = new ArrayList<>();
    while (endIndex >= startIndex) {
        lst.add(food.get(endIndex--));
    }
    return lst;
}

Output [buns, tea, butter, pie, fruit, chips]