CODEWITHSUNDEEP
javaarraylist
Fiery Phoenix
Fiery Phoenix

Reputation: 1166

Removing Sublist from ArrayList

For simplicity, let's say I have an ArrayList whose indices contain exactly one single-digit integer. For instance:

6 4 5 6 0 6 3 4 1 6 1 6 0 6 8 3

I would like to filter out all occurrences of the sublist 6 0 6, such that the new list becomes:

6 4 5 3 4 1 6 1 8 3

Is there any way of doing this? Using ListIterator doesn't seem to work for me, because I have to consider three consecutive elements collectively and I'm honestly not sure how to do that.

Here's a skeleton of the method I have implemented: 

public static void filterList(ArrayList<Integer> list) {
    ListIterator<Integer> iterator = list.listIterator();
    int elem; 
    while (iterator.hasNext()) {
        // Remove any sublist of 6 0 6
    }
}

Edit: Again, for simplicity, let's assume there won't be cases where we have 60606 or similar.

Upvotes: 5

Views: 10707

Answers (5)

Christian Oliver
Christian Oliver

Reputation: 142

    //if
    List<String> originalList = new ArrayList<>();
    originalList.add("A");
    originalList.add("B");
    originalList.add("C");
    originalList.add("D");
    //and
    List<String> subList = new ArrayList<>();
    subList.add("A");
    subList.add("C");
    //then
    originalList = originalList.stream().filter(x -> !subList.contains(x)).collect(Collectors.toList());
    
    //originalList should now contain {"B","D"}

Upvotes: 2

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

[Edited - better, single pass approach]

Custom, enhanced indexOfSublist starting the search from offset; therefore, we don't restart from 0 each time we removed something (as we did when using Collections.indexOfSublist see bottom of this answer). 

static <T> int indexOfSublist(List<T> haystack, List<T> needle, int offset){
  int toRet=-1;
  int needleLen=needle.size();
  if(needleLen>0) {
    // it makes sense to search
    int haystackLen=haystack.size();
    for(;offset+needleLen<haystackLen && toRet<0; offset++) {
      int compIx;
      for(
          compIx=0; 
          (
                 compIx<needleLen 
              && false==haystack.get(offset+compIx).equals(needle.get(compIx))
          ); 
          compIx++
      );
      if(compIx==needleLen) { // found
        toRet=offset;
      }
    }
  }
  return toRet;
}

public static void filterList(List<Integer> haystack, List<Integer> needle) {
  for(
      int offset=0, ixOfNeedle=indexOfSublist(haystack, needle, offset);
      ixOfNeedle>=0;
      ixOfNeedle=indexOfSublist(haystack, needle, offset)
  ) {
    // found one place. We'll continue searching from here next time
    offset=ixOfNeedle;
    //////////////////////////////////////////
    // for a better removal sequence, see the 
    // 4castle's answer using sublists 
    for(int i=needle.size(); i>0; i--) {
      haystack.remove(ixOfNeedle);
    }
  }
}

Collections.indexOfSublist is what you are after. 

public static void filterList(ArrayList<Integer> haystack, List<Integer> needle) {
    for(
       int ixOfNeedle=Collections.indexOfSublist(haystack, needle);
       ixOfNeedle>=0;
       ixOfNeedle=Collections.indexOfSublist(haystack, needle)
    ) {
      for(int i=needle.size(); i>0; i--) {
        haystack.remove(ixOfNeedle);
      }
    }
}

Upvotes: 3

castletheperson
castletheperson

Reputation: 33466

You can create an efficient and concise O(nm) solution by using Collections.indexOfSubList:

public static void removeAllSubList(List<?> list, List<?> subList) {
    // find first occurrence of the subList in the list, O(nm)
    int i = Collections.indexOfSubList(list, subList);
    // if found
    if (i != -1) {
        // bulk remove, O(m)
        list.subList(i, i + subList.size()).clear();
        // recurse with the rest of the list
        removeAllSubList(list.subList(i, list.size()), subList);
    }
}

Ideone Demo

Upvotes: 2

Matthew
Matthew

Reputation: 3234

What I would recommend is to search your ArrayList before you make it into a ListIterator.

public static void filterList(ArrayList<Integer> list) {
    bool firstInstance = false; //Saying we having found our first instance of our sub list
    for(int i=0;i<list.size();++i) {
       if(list.get(i) == 6) //Checks to see if our first index is a 6 or it pointless to check the next two numbers i.e. wasting resources
         if(list.get(i+1) == 0 && list.get(i+2) == 6 && !firstInstance) { //Make sure it a 6 0 6 list
           list.remove(i); //Removes first one
           list.remove(i); //Removes second one which now became our current index number
           list.remove(i); //Removes third one which now became our current index number
         } else
             firstInstance = true; //Our first instances has been found and will now remove duplicate ones!
    }
    ListIterator<Integer> iterator = list.listIterator();
    int elem; 
    while (iterator.hasNext()) {
        // Remove any sublist of 6 0 6-- Already Done
    }
}

Upvotes: 1

Vickyexpert
Vickyexpert

Reputation: 3167

You can use array and list combination for this as find below solution, hope it will help you.

    public void testData()
    {
        int tempArray[] = {6, 4, 5, 6, 0, 6, 3, 4, 1, 6, 1, 6, 0, 6, 8, 3};
        List<Integer> resultArray = new ArrayList<>();

        for(int i = 0; i < tempArray.length; i++)
        {
            if(tempArray[i] == 6 && tempArray[i+1] == 0 && tempArray[i + 2] == 6) 
            {
                i += 2;
            }
            else
            {
                resultArray.add(tempArray[i]);
            }
        }

        for(int tempInt : resultArray)
        {
            System.out.print("\t" + tempInt);
        }
    }

Note: You can pass array from your side or return result as per your requirement in above function.

Upvotes: 0

Related Questions