Equality (== structural vs === referential) in Kotlin - Performance Comparison

Time Complexity: Equality (== structural vs === referential)

O(n)

Understanding Time Complexity

When checking if two things are equal in Kotlin, there are two ways: structural and referential equality.

We want to understand how the time it takes to check equality changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val list1 = listOf(1, 2, 3, 4, 5)
val list2 = listOf(1, 2, 3, 4, 5)

// Structural equality check
val structuralEqual = list1 == list2

// Referential equality check
val referentialEqual = list1 === list2

This code compares two lists using structural equality (==) and referential equality (===).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Structural equality (==) compares each element one by one.
• How many times: It checks elements up to the size of the lists.
• Referential equality (===) just checks if both variables point to the same object once.

How Execution Grows With Input

Structural equality checks each element, so more elements mean more work.

Input Size (n)	Approx. Operations
10	10 element comparisons
100	100 element comparisons
1000	1000 element comparisons

Pattern observation: The work grows directly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to check structural equality grows in a straight line with the size of the data.

Common Mistake

[X] Wrong: "Checking structural equality is always as fast as referential equality."

[OK] Correct: Structural equality compares each element, so it takes longer as data grows, unlike referential equality which just checks if two variables point to the same object.

Interview Connect

Understanding how equality checks work helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if the lists contain other lists inside? How would that affect the time complexity of structural equality?"

Practice

1. In Kotlin, what does the operator == check when comparing two variables?

easy

A. If the two variables are the exact same object (referential equality)

B. If the two variables have the same content (structural equality)

C. If the two variables are of the same type

D. If the two variables are both null

Solution

1. Step 1: Understand the meaning of == in Kotlin

   The == operator checks if two variables have the same content, meaning their values are equal.

2. Step 2: Differentiate from ===

   The === operator checks if two variables point to the exact same object in memory, which is different from ==.

3. Final Answer:

   If the two variables have the same content (structural equality) -> Option B

4. Quick Check:

   == means structural equality [OK]

Hint: Remember: == compares values, not object identity [OK]

Common Mistakes:

• Confusing == with ===
• Thinking == checks object identity
• Assuming == checks type equality

2. Which of the following Kotlin expressions correctly checks if two variables refer to the exact same object?

easy

A. a === b

B. a != b

C. a.equals(b)

D. a == b

Solution

1. Step 1: Identify the operator for referential equality

   In Kotlin, === checks if two variables point to the exact same object in memory.

2. Step 2: Confirm other options

   == and .equals() check structural equality, and != checks inequality, so they don't check referential equality.

3. Final Answer:

   a === b -> Option A

4. Quick Check:

   === means referential equality [OK]

Hint: Use === to check if two variables are the same object [OK]

Common Mistakes:

• Using == instead of === for object identity
• Confusing .equals() with ===
• Assuming != checks referential equality

3. What will be the output of the following Kotlin code?

val a = "hello"
val b = String(charArrayOf('h', 'e', 'l', 'l', 'o'))
println(a == b)
println(a === b)

medium

A. true\nfalse

B. false\nfalse

C. true\ntrue

D. false\ntrue

Solution

1. Step 1: Evaluate a == b

   Both strings contain the same characters "hello", so a == b is true because it checks structural equality.

2. Step 2: Evaluate a === b

   They are two different String objects in memory, so a === b is false because it checks referential equality.

3. Final Answer:

   true\nfalse -> Option A

4. Quick Check:

   == true, === false [OK]

Hint: == checks content, === checks if same object [OK]

Common Mistakes:

• Assuming === is true because contents match
• Confusing == with ===
• Thinking different objects with same content are ===

4. Consider this Kotlin code snippet:

val x = listOf(1, 2, 3)
val y = listOf(1, 2, 3)
if (x === y) {
    println("Same object")
} else {
    println("Different objects")
}

What is the output and why?

medium

A. Same object

B. Compilation error

C. Different objects

D. Runtime exception

Solution

1. Step 1: Understand listOf creates new objects

   Each call to listOf(1, 2, 3) creates a new list object, so x and y are different objects.

2. Step 2: Check referential equality with ===

   Since x and y are different objects, x === y is false, so the else branch runs.

3. Final Answer:

   Different objects -> Option C

4. Quick Check:

   === false for different list objects [OK]

Hint: listOf creates new objects; === checks identity [OK]

Common Mistakes:

• Assuming lists with same content are ===
• Confusing structural and referential equality
• Expecting compilation or runtime errors

5. You want to check if two variables a and b in Kotlin either have the same content or are the exact same object. Which code snippet correctly prints "Equal" if either condition is true, and "Not Equal" otherwise?

hard

A. if (a === b) {
println("Equal")
} else if (a == b) {
println("Not Equal")
} else {
println("Equal")
}

B. if (a === b && a == b) {
println("Equal")
} else {
println("Not Equal")
}

C. if (a == b) {
println("Not Equal")
} else if (a === b) {
println("Equal")
} else {
println("Not Equal")
}

D. if (a == b || a === b) {
println("Equal")
} else {
println("Not Equal")
}

Solution

1. Step 1: Understand the condition needed

   We want to print "Equal" if either a == b (same content) OR a === b (same object) is true.

2. Step 2: Check each option's logic

   if (a == b || a === b) {
       println("Equal")
   } else {
       println("Not Equal")
   }

   uses logical OR (||) correctly.

   if (a === b && a == b) {
       println("Equal")
   } else {
       println("Not Equal")
   }

   requires both to be true (AND), which is too strict.

   if (a == b) {
       println("Not Equal")
   } else if (a === b) {
       println("Equal")
   } else {
       println("Not Equal")
   }

   incorrectly prints "Not Equal" when a == b is true.

   if (a === b) {
       println("Equal")
   } else if (a == b) {
       println("Not Equal")
   } else {
       println("Equal")
   }

   prints "Not Equal" incorrectly when a == b is true but a === b is false.

3. Final Answer:

   if (a == b || a === b) -> Option D

4. Quick Check:

   Use || to combine == and === checks [OK]

Hint: Use || to check either structural or referential equality [OK]

Common Mistakes:

• Using && instead of ||
• Confusing order of conditions
• Printing wrong messages for conditions