Operating sublists efficiently

Question

In my Java program, I need to operate on the sublists a of ArrayList or LinkedList often, like removing a sublist, comparing two sublists.

For ArrayList or LinkedList, I didn't find any good APIs to do these. My current implementation is as below. Basically, it takes an input like:

u1234 u1236 u1236 u2def u1236 u1236 u2def

and outputs the following:

u1234 ( ( u1236 ) * u2def ) *

Core function:

ArrayList<String> toRegex(ArrayList<String> tokenArray)
{
    /* check different length of continuous duplication */
    for(int len=1; len<=tokenArray.size()/2; len++) 
    {
        boolean match = false;
        /* given a length, scan for duplication */
        for(int i=0; i<tokenArray.size()-(2*len-1); i++) 
        {                
            ArrayList<String> first = new ArrayList<String>();
            ArrayList<String> second = new ArrayList<String>();
            for(int j=i; j<i+len; j++)
                first.add(tokenArray.get(j));
            for(int j=i+len; j<i+2*len; j++)
                second.add(tokenArray.get(j));                               

            if(isSpecial(first)) {       /* skip the cases */
                continue;
            }

            while(isIdentical(first, second))
            {
                match = true;
                for(int j=i+len; j<i+2*len; j++)
                    tokenArray.remove(i+len);
                if(i+2*len > tokenArray.size())
                    break;
                second.clear();
                for(int j=i+len; j<i+2*len; j++)
                    second.add(tokenArray.get(j));
            }

            if(match == true) {
                tokenArray.add(i, "(");
                tokenArray.add(i+1+len, ")");
                tokenArray.add(i+2+len, "*");
                i = i+3+len;
                match = false;
            }  
       }
    }

    return tokenArray;
}

Currently, the performance is not good. Could you find the bad design or inappropriate usage of data structures/APIs? What are the good common ways of operating sublists?

Answer 1

Yes, this doesn't look pretty. Consider converting the list to sets or using RegEx.

ArrayList<String> A = new ArrayList<String>();
A.add("Z");
A.add("Z");
A.add("C");
A.add("X");
A.add("Z");

Set<String> set = new HashSet<String>(A);

for(String temp:set)
    System.out.println(temp);           

Sublists:

List<String> subList = alist.subList(2, 4);

Use retainAll to get intersections:

listOne.retainAll(listTwo) ;  
boolean areEqualNotSamePosition = listeOne.size();

Answer 2

public static void main(final String[] args) {
        final String[] tabS = "u1234 u1236 u1236 u2def u1236 u1236 u2def "
            .split(" ");
            // The same thing can be done/adapted with a String[]
        final ArrayList<String> al = new ArrayList<>();
        final ArrayList<String> alTmp = new ArrayList<>();
        for (final String s : tabS) {
            al.add(s);
        }
        // removing need to begin by end
        for (int i = al.size() - 1; i >= 0; i--) {
            final String string = al.get(i);
            if (!alTmp.contains(string)) {
                alTmp.add(string);
            } else {
                al.remove(i);
            }
        }
        // inserting decoration if result have 2 or more object
        final int j = al.size();
        final String ending = ")*";
        if (j > 1) {
            for (int i = 1; i < j; i++) {
                al.add(1, "(");
            }
            for (int i = al.size() - 1; i > j; i--) {
                al.add(i, ending);
            }
            al.add(ending);
        }
        System.out.println(al.toString());
    }

Output : [u1234, (, (, u1236, )*, u2def, )*]
You can use a StringBuilder to remove ''' and make the output as you like.