Improve performance while Traversing List I was trying to write a Java program to compare previous records while traversing. It returns true if element exists previously, else false.

e.g.


if elements are {"Raj","Jas","Kam","Jas"} then return true (since Jas element available previously)
if elements are {"Raj","Jas","Kam","Tas"} then return false


I have written the below code, but its complexity is n*n, which is not good.  How could I write clean code to improve the performance?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CompareList {
    private List&lt;String&gt; listNames;
    private List&lt;String&gt; listTempName = new ArrayList&lt;&gt;();

    public CompareList(String[] vListArray) {
        listNames = Arrays.asList(vListArray);
    }
    public CompareList(List&lt;String&gt; vListName) {
        listNames = vListName;
    }
    public boolean isPreviousNameExist() {
        String tempName = null;
        for (int i = 0; i &lt; listNames.size(); i++) {
            tempName = listNames.get(i);
            if (listTempName.contains(tempName)) {
                return true;
            } else {
                listTempName.add(tempName);
            }

        }
        return false;
    }
    public static void main(String[] args) {
        String[] nameArray = {"A", "B", "C", "D", "E", "F"};
        CompareList compareList = new CompareList(nameArray);
        System.out.println("==&gt;" + compareList.isPreviousNameExist());
    }
}


UPDATED

I have updated the code and tried using a recursive way, same way how we sort using MergeSort and find its performance better for a large number of records, compared to HashSet. I believe its complexity is O(log n).

public class NameComparator {

    private String[] listNames;

    private String[] listTempNames;

    private boolean compareFlag = false;

    private int size;
    public boolean isNameAlreadyExist(String[] vListNames) {
        this.listNames = vListNames;
        size = vListNames.length;
        this.listTempNames = new String[size];
        checkAndSort(0, size - 1);
        return compareFlag; 
    }
    private void checkAndSort(int low, int high) {

        //Use the merge sort
        }
    }
    ..............................
}
You can actually change the performance to O(n) by changing one line of code here (and adding a couple of imports):

import java.util.Set;
import java.util.HashSet;

...

private Set&lt;String&gt; listTempName = new HashSet&lt;&gt;();


Although this works, we can simplify the code a little bit. Effectively, you want to see if the list of elements in the given List are unique. There's a really easy way to do this: add them all to a Set. If the size of the set and the size of the list are equal, then there are no duplicates. If the sizes are different, then there must be 1 or more duplicate elements. With this, we can simplify your code to:

public boolean isPreviousNameExist() 
{
    for(String name : listNames) {
        listTempName.add(name);
    }
    return listNames.size() != listTempName.size();
}


A slight improvement based on comment by @bowmore:

public boolean isPreviousNameExist()
{
    for(String name : listNames) {
        if(!listTempName.add(name)) {
            return true;
        }
     }
     return false;
}