# 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<String> listNames;
private List<String> listTempName = new ArrayList<>();

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

}
return false;
}
public static void main(String[] args) {
String[] nameArray = {"A", "B", "C", "D", "E", "F"};
CompareList compareList = new CompareList(nameArray);
System.out.println("==>" + 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;
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<String> listTempName = new HashSet<>();


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) {
}
return listNames.size() != listTempName.size();
}


A slight improvement based on comment by @bowmore:

public boolean isPreviousNameExist()
{
for(String name : listNames) {
return true;
}
}
return false;
}

• thanks Yuushi, Is it any other way without using hashing? – sun007 Jan 29 '14 at 7:07
• Well, you can use a TreeSet, which (by default) uses natural ordering to search for elements (which is O(log n) instead of amortized O(1)). Is there any real reason you want to avoid hashing? – Yuushi Jan 29 '14 at 7:11
• thanks Yuushi, I only have doubt if it support large datas? – sun007 Jan 29 '14 at 7:14
• You can break early from the loop if Set.add()returns false – bowmore Jan 29 '14 at 7:21
• O(n), not that I can think of. There is an O(n log n) solution: sort the original array, and then loop through it, checking adjacent elements. This could potentially be better if memory is an issue. – Yuushi Jan 29 '14 at 7:57

Your complexity is indeed O(n2) because you traverse a list bounded by n for each n elements of your list.

You can reduce this list to O(n * log(n)) quite easily:

• Sort your array -> O(n * log(n))
• Compare each element with the next one listNames.get(i).equals(listNames.get(i+1)) -> O(n)

Total is O(n * log(n))

### Edit:

If you are really interested on the true/false result, there is a pretty one-liner solution :

return listNames.size() == new HashSet(listNames).size();


The HashSet will filter duplicate elements, hence will be smaller if there are any duplicates. It runs in O(n), as insertion in a HashSet is O(1)

• thanks njZk2 and sybOrg. I did just small modification in sorting approach. I sort through merge sort(recursive approach) as considering large data and while sorting i compare the element with flag. I updated the code. Please review the same and provide suggestion. – sun007 Jan 30 '14 at 7:20