CODEWITHSUNDEEP
javaarraylist
Mangat Rai Modi
Mangat Rai Modi

Reputation: 5706

Find unique Arraylist in an ArrayList of ArrayLists

As I understand ArrayList class inherit equals() function of its parent 'List' class to find if two member objects are same. Does that mean that 'contains()' linear search(using 'equal') for a duplicate entry in the ArrayList? So the complexity of the 'contains' is O(n)?

If I am using ArrayList of Arraylist then the complexity of contains function will be O(n*m)? If yes, then is there any replacement of contains function which can get some hash(Based on contents) of the member ArrayList and confirm that two ArrayList objects are equal?

Edit: I am just trying to find number of unique elements in an ArrayList of ArrayList. Like {{0,0,3},{1,2,3},{0,0,3}} should give {{0,0,3},{1,2,3}}.

Upvotes: 0

Views: 93

Answers (2)

C.B.
C.B.

Reputation: 8326

If you already have an ArrayList<ArrayList<Integer>> you can pass it to HashSet<ArrayList<Integer>>'s constructor and have a unique set of ArrayLists

List<ArrayList<Integer>> mylist_list = new ArrayList<ArrayList<Integer>>(); 
ArrayList<Integer> mylist = new ArrayList<Integer>();
...
for(ArrayList<Integer> list : mylist_list)
{
    System.out.println(Arrays.toString(list.toArray()));
}
Set<ArrayList<Integer>> mylist_set = new HashSet<ArrayList<Integer>>(mylist_list);

for(ArrayList<Integer> list : mylist_set)
{
    System.out.println(Arrays.toString(list.toArray()));            
}

Yielded output of 

[0, 1, 2]
[0, 1, 2]
[0, 1, 2]

When passing duplicates to the ArrayList<ArrayList<Integer>>

Upvotes: 1

Sergii Zagriichuk
Sergii Zagriichuk

Reputation: 5399

Complexity is O(N). Implementation next :

 public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

yes, contains calls indexOf method.

Upvotes: 0

Related Questions