Comparing two lists in kotlin

Question

I came across with kotlin equals function to compare two list of same type. It works fine for pure Kotlin with data classes.

I'am using a Java library in Kotlin project in which a callback method returns a list of objects for a time interval of X seconds. Trying to compare the old list with new list for every call, but equals returns false even the items are same and equal.

val mOldList: MutableList<MyObject>()? = null

override fun updatedList(list: MutableList<MyObject>){
    // other code
    if (mOldList.equals(list)) // false everytime
}

Is this because of Java's equals method from library?

Alternative suggestions for list compare would be appreciative.

Hexastich

Both lists are java List? – Vereen

Is the list of different type perhaps? For example ArrayList vs LinkedList. – Kandykane

Yes both are java list. And they are not different types; I am comparing the list with the new updated list after x seconds. – Hexastich

When you say "items are same and equal", what do you mean? Referential equality or structural equality? I.e. does MyObject override the equals() method? – Baumgardner

I meant for structural equality. Not sure about equals() method is override'd in library. – Hexastich

Cannot have structural equality without overriding equals(). – Baumgardner

In Java, "In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface." So if it returns false, there must be different elements. (And different List types shouldn't matter.) – Empyema

Answer 1

Just fyi you can call list1 == list2 without any extra work, if your custom object is based off of a data class (which automatically overrides equals for you).

Baun

Thanks. And for the people who wonder about this listOfdataClass1.map { it.string } == listOfdataClass2.map { it.string } also works as expected. – Warhead

This won't work if the elements don't have the same order, an option is to sort both lists before to compare them. – Ablation

@SalimMazariBoufares Sort and check is totally wrong approach. Let's say we sort by id and A1 and A2 has the same id. list1 = [A1, A2] after the sort this list will still be [A1, A2]. list1 = [A2, A1] after the sort the list will still be [A2, A1] and if equals method contains any other param than id, then you are f*cked. – Mikvah

@Mikvah wdym by id? Id means identifier, by definition id is unique, so A1 and A2 can't have the same id only if they're the same, and this won't cause problems. – Ablation

wdym by id? Id means identifier, it is unique and then both objects are the same. But I got your point, it depends on the sorting strategy, if two different objects are having the same value on which the sorting is done then they can have switched positions in two lists having same elements. In case of literals it will not cause problems. – Ablation

@SalimMazariBoufares Write a simple test case for my example and you will see the problem – Mikvah

@Farid, I already did write tests before to write the comment, first I told you that you're using a wrong terminology, then I did say you're right, except if the two objects are the same. – Ablation

Lists are ordered by definition; they're not sets. Two lists with the same elements in a different order are not equal. If you want to make that kind of comparison, either name the function something else besides equals() or use the correct datatype instead of List. Rene's answer is 100% correct for equals(). – Trotman

Answer 2

If you don't bother about order of elements in both lists, and your goal is to just check that two lists are of exactly same elements, without any others, you can consider two mutual containsAll calls like:

var list1 = mutableListOf<String>()
var list2 = mutableListOf<String>()

if(list1.containsAll(list2) && list2.containsAll(list1)) {
    //both lists are of the same elements
}

Mestee

That's the most logical answer. – Defensive

I'm downvoting this - this is definitely not the best way to do it. – Giuliana

@Giuliana Could you please state what is wrong about this way? – Mestee

@Mestee because instead of O(n) comparisons you basically calling containsAll twice and this just can not have better performance than linear comparison per index. - check this for instance - #10200272 – Giuliana

Instead of List, Set should be used. HashSet (not TreeSet - it is important) collections have O(1) lookup complexity (list have O(N)). So just replace both mutableListOf to mutableSetOf. – Tunesmith

If there are no duplicates in your list, you can compare the sizes first, then one containsAll() will be enough. – Spastic

Performance wise, containsAll() is very slow. Sort and check equals is way faster. – Frodi

@Giuliana so your solution would be what? – Mikvah

Answer 3

Java lists implement equals method and two lists are defined to be equal if they contain the same elements in the same order. I guess, you are missing equals method in your MyObject class.

Speight

MyObject is a class from library, so I cannot override equals() method. – Hexastich

You could always extend MyObject and then override equals(), if possible. – Stiffnecked

Yeah, easy-peasy. What happens if MyObject is final? – Mikvah

Use a decorator? – Speight

Answer 4

Using zip

zip returns a list of pairs built from the elements of this array and the other array with the same index. The returned list has length of the shortest collection.

fun listsEqual(list1: List<Any>, list2: List<Any>): Boolean {

    if (list1.size != list2.size)
        return false

    val pairList = list1.zip(list2)

    return pairList.all { (elt1, elt2) ->
        elt1 == elt2       
    }
}

Thalassa

This method allocates several unnesesary objects: at least one new list and new Pair per each element from the longest list. In addition several enumerators are allocated, however JIT can put them on stack. So this method requires O(N) additional memory in heap. – Tunesmith

Good point. In that regard, @XIII-th 's answer below is better https://mcmap.net/q/329669/-comparing-two-lists-in-kotlin – Thalassa

Answer 5

You can use implementations below for comparing of two Collection:

infix fun <T> Collection<T>.deepEqualTo(other: Collection<T>): Boolean {
    // check collections aren't same
    if (this !== other) {
        // fast check of sizes
        if (this.size != other.size) return false
        val areNotEqual = this.asSequence()
            .zip(other.asSequence())
            // check this and other contains same elements at position
            .map { (fromThis, fromOther) -> fromThis == fromOther }
            // searching for first negative answer
            .contains(false)
        if (areNotEqual) return false
    }
    // collections are same or they are contains same elements with same order
    return true
}

Or order ignore variant:

infix fun <T> Collection<T>.deepEqualToIgnoreOrder(other: Collection<T>): Boolean {
    // check collections aren't same
    if (this !== other) {
        // fast check of sizes
        if (this.size != other.size) return false
        val areNotEqual = this.asSequence()
            // check other contains next element from this
            .map { it in other }
            // searching for first negative answer
            .contains(false)
        if (areNotEqual) return false
    }
    // collections are same or they are contains same elements
    return true
}

Note: both function compare only first level of deep

Genie

Second answer has O(N^2) complexity. Statement it in other has O(N) complexity for list and it is called N times. Right solution for second case is something like return this.toSet() == other.toSet() – Tunesmith

@ManushinIgor yes, your solution is better the thаn my. Thanks – Genie

Answer 6

Here's a short version using a extension function:

fun <T> List<T>.deepEquals(other: List<T>) =
    size == other.size && asSequence()
        .mapIndexed { index, element -> element == other[index] }
        .all { it }

And you can use it like this:

listOf("Hola", "Mundo").deepEquals(listOf("Hello", "World"))

Derosa

To break early and avoid iterating over the whole list, you should use this.asSequence().mapIndexed {...} – Outsail

Answer 7

Best way to compare 2 lists

Create Extension function as below. This will be useful if order doesn't matters

fun <T> List<T>.isEqualsIgnoreOrder(other: List<T>) = this.size == other.size && this.toSet() == other.toSet()

Use Extension function in your classes to compare lists as below.It returns boolean.

list1.isEqualsIgnoreOrder(list2)

Trager

When choosing this approach, it is worth keeping in mind that the method will consider lists ["a", "a", "b"] and ["a", "b", "b"] equal. – Devonadevondra

Answer 8

You could use arrays and contentDeepEquals:

infix fun <T> Array<out T>.contentDeepEquals(
    other: Array<out T>
): Boolean
JVM
1.1
@JvmName("contentDeepEqualsInline") infix fun <T> Array<out T>.contentDeepEquals(
    other: Array<out T>
): Boolean

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/content-deep-equals.html

Smoko

Please note, that this function requires the same elements order for true answer. – Tunesmith

Answer 9

The questions and answers so far are primarily focused on equals/!equals, but since the title talks about comparing, I'll give a slightly more generic answer that implements compareTo returning -1,0,1 for <, =, >

fun <T: Comparable<T>> Iterable<T>.compareTo(other: Iterable<T>): Int {
    val otherI = other.iterator()
    for (e in this) {
        if (!otherI.hasNext()) return 1 // other has run out of elements, so `this` is larger
        val c = e.compareTo(otherI.next())
        if (c != 0) return c // found a position with a difference
    }
    if (otherI.hasNext()) return -1 // `this` has run out of elements, but other has some more, so other is larger
    return 0 // they're the same
}

Fortenberry

Answer 10

I know it's not a good solution but it works.

val list1 = listOf<String>()
val list2 = listOf<String>()

fun <T> isSame(list1: List<T>, list2: List<T>): Boolean {
    if (list1.size != list2.size) return false

    val hash1 = list1.map { it.hashCode() }.toSet()
    val hash2 = list2.map { it.hashCode() }.toSet()

    return (hash1.intersect(hash2)).size == hash1.size
}

Implement the hasCode() method if you use objects other than String.

Furculum

Answer 11

You can iterate through one list and check the corresponding position value from second list. Take the example below for reference.

var list1 = mutableListOf<String>()
var list2 = mutableListOf<String>()

list1.forEachIndexed { i, value ->
    if (list2[i] == value)
    {
        // your implementaion
    }  
}

Additionally you can filter list for the changed values.

var list1 = mutableListOf<String>()
var list2 = mutableListOf<String>()

val changedList = list1.filterIndexed { i, value -> 
    list2[i] != value)
}

Adalbertoadalheid

This method can fail if lists have different sizes. Also this method allocates new list in memory. – Tunesmith

Answer 12

Another answer in case you want to compare two lists, that have the same number of the same elements, and no care about the order:

infix fun <T> List<T>.elementEquals(other: List<T>): Boolean {
  if (this.size != other.size) return false

  val tracker = BooleanArray(this.size)
  var counter = 0

  root@ for (value in this) {
    destination@ for ((i, o) in other.withIndex()) {
      if (tracker[i]) {
        continue@destination
      } else if (value?.equals(o) == true) {
        counter++
        tracker[i] = true
        continue@root
      }
    }
  }

  return counter == this.size
}

Thalamencephalon

Answer 13

When I want to compare to list on kotlin I like this way:

data class Element(val id: String, val name: String)
var list1 = mutableListOf<Element>()
var list2 = mutableListOf<Element>()
fun deleteRepeated(
        list1: List<Element>,
        newElementsList: List<Element>
    ): List<FileInfo> {
        return list2.filterNot { isTheSameID(it, list1) }
 }
 private fun isTheSameID(element: Element, list1: List<FileInfo>): Boolean {
     list1.forEach {
         if (element.id == it.id){
             return true
         }
     }
     return false
 }

Example usage:

list1 = [(id=1, name=Eva),(id=2, name=Ana), id=3, name=Abraham)]

list2 = [(id=2, name=Ana), id=3, name=Abraham)]

deleteRepeated(list1, list2)

// [(id=1, name=Eva)]

Euh

Answer 14

Want to say that containsAll() is way slower than just sort and check equal.

I have tested it using an online Kotlin console, and here is the result:

But the fastest way is probably using Set instead. (But, set does not allow duplicate elements. So be careful of your use case)

Frodi