Comparable and Comparator interface in Java

It is one of the popular interview question for Java developers, "What is difference between Comparable and Comparator". Sometimes it is asked in different form, We have a list of Employee objects(with name, employeeId, salary) and we want to sort this list based on salary- can you write sample code for the same ?. Solution to such problem lies in understanding of Comparable and Comparator interface. 
Both Comparable and Comparator interfaces are used to sort Objects in Java. There are visible difference between them.Let's list out the differences followed by sample program to illustrate the differences:

1. Package details:-  Comparable interfaces is part of java.lang package, however
   Comparator interfaces are part of java.util package.
2.  Sorting method: Comparable interfaces uses compareTo(Obj) for comparing objects, however Comparator uses compare(Obj1, Obj2). See syntactical differences below:888

int compare(Object obj1,Object obj2){ }
obj1 and obj2 is compared and returns positive, zero and negative values.

Positive: obj1 is greater than obj2

Zero : obj1 is equal to obj2

Negative: obj1 is smaller than obj2

int compareTo(Object obj){ }
Object obj(passed as parameter above) is compared with the object calling compareTo method (i.e: this) and returns (Positive, zero and  negative value) depending on the implementation

Positive: this is greater than obj

Zero : this is equal to obj

Negative: this is smaller than obj

3. Sorting logic and implementation strategy:-  Sorting logic and implementation strategy is different for both of them.
   Comparable interface: Object which is sorted must implement Comparable interface and sorting logic should be written in compareTo(obj) method.For example, if sorting of Employee object is carried out, the declaration of Employee class will look like this:
class Employee implements Comparable<Employee> {
  public int compareTo(Employee o) { }
}//compareTo of Employee class defines sorting logic
Comparator interface: It gives more flexibility in terms of sorting logic implementation. It allows to write sorting logic in different class or classes and object of these classes can be plugged in depending upon, based on which object we want to sort/compare objects.
i.e: Separation of concern is observed in Comparator interface (Object which are sorted need not implement Comparator interface and write sorting logic in compare(oj1,obj2) method) and because of this decoupled strategy it provides more flexibility.For example, suppose we want to sort Employee object based on salary then we can create separate class and it looks like this:
class EmployeeSortBySalary implements Comparator<Employee> {
    public int compare(Employee arg0, Employee arg1) {  }
}//Here compare method of EmployeeSortBySalary(a custom class) defines  sorting logic.
If you did not got the bigger picture, do not worry, we will revisit it again while writing complete sample program.  

4. Comparable interface provides natural ordering is by default, however Comparator interface requires custom implementation.Natural ordering means, alphabetic ordering of Strings, numerical order(ascending/descending) for Numbers, etc. By default, collections algorithm uses Comparable interface to sort (Collections.sort(<collection>)) and similarly, Arrays.sort() also uses the same.Collections algorithm also take comprator instance and sort in some alternate way. Collections.sort(<collection>,<comprator instance> )

Let's write a sample program to understand how we can use Comparable interface to sort list of Employee based in salary.

Hide code lines

import java.util.Collections; import java.util.LinkedList; import java.util.List; public class ComparableExample {   public static void main(String[] args) {     Employee e1 = new Employee("Nikhil", "744", 745);     Employee e2 = new Employee("Ranjan", "746", 234);     Employee e3 = new Employee("Adam", "746", 999);     List<Employee> list = new LinkedList<Employee>();     list.add(e1);     list.add(e2);     list.add(e3);     System.out.println("List Before sort: In the order of insertion: " + list);     Collections.sort(list);     System.out.println("List After sort: Sorting based on salary: " + list);   } } class Employee implements Comparable<Employee> {   private String name;   private long salary;   private String employeeId;   public Employee(String name, String employeeId, long salary) {     this.name = name;     this.employeeId = employeeId;     this.salary = salary;   }   public String getName() {     return name;   }   public void setName(String name) {     this.name = name;   }   public long getSalary() {     return salary;   }   public void setSalary(long salary) {     this.salary = salary;   }   public String getEmployeeId() {     return employeeId;   }   public void setEmployeeId(String employeeId) {     this.employeeId = employeeId;   }   public int compareTo(Employee o) {     Employee emp = (Employee) o;     // if salary of calling Object is greater then returns 1,     // else compare for equality and less than and returns accordingly     return (this.salary > emp.salary) ? 1 : (this.salary > emp.salary) ? 0         : -1;   }   public String toString() {     return getName() + " " + this.getSalary() + " " + this.getEmployeeId();   } }

 ============Sample output: =============
 List Before sort: In the order of insertion: [Nikhil 745 744, Ranjan 234 746, Adam 999 946]
List After sort: Sorting based on salary: [Ranjan 234 746, Nikhil 745 744, Adam 999 946]
=====================================
In above program, sorting of list of Employee is carried out so, Employee class is implementing comparable interface and write sorting logic in compareTo() method (it returns 1, 0 , -1 comparing salary component of employee object). From the sample output, we can notice that before calling Collections.sort(list)- list is displayed and it maintains insertion order. After calling sort method, it displays employee object in the order of increasing salary component.
Now we will write sample code implementing Comparator interface. Here we will sort our list of Employee based on salary and name, using two different custom class which implements Comparator interface. Remember, we can plug different comprator object and sort collections.

Hide code lines

import java.util.Collections; import java.util.Comparator; import java.util.LinkedList; import java.util.List; public class ComparatorExample {   public static void main(String[] args) {     Employee e1 = new Employee("Nikhil", "744", 745);     Employee e2 = new Employee("Ranjan", "746", 234);     Employee e3 = new Employee("Adam", "946", 999);     List<Employee> list = new LinkedList<Employee>();     list.add(e1);     list.add(e2);     list.add(e3);     System.out.println("List before sort: In the order of insertion: " + list);     Collections.sort(list, new EmployeeSortByName());     System.out.println("1st call sorted outcome: Plug EmployeeSortByName comprator "         + list);     Collections.sort(list, new EmployeeSortBySalary());     System.out.println("2nd call sorted outcome: Plug EmployeeSortByName comprator "         + list);   } } class EmployeeSortBySalary implements Comparator<Employee> {   public int compare(Employee obj1, Employee obj2) {     return (obj1.getSalary() > obj2.getSalary()) ? 1         : (obj1.getSalary() > obj2.getSalary()) ? 0 : -1;     // comment above return and un-comment below one, then same outcome     // will come because in below case fundamental of natural ordering of     // number is explored- returns +ve, -ve and zero.     /* return (int) (obj1.getSalary() - obj2.getSalary()); */   } } class EmployeeSortByName implements Comparator<Employee> {   public int compare(Employee obj1, Employee obj2) {     // String class implements Comparable interface and implements     // compareTo method - Compares two strings lexicographically     // natural ordering after sort is maintained.     return obj1.getName().compareTo(obj2.getName());   } } class Employee {   private String name;   private long salary;   private String employeeId;   public Employee(String name, String employeeId, long salary) {     this.name = name;     this.employeeId = employeeId;     this.salary = salary;   }   public String getName() {     return name;   }   public void setName(String name) {     this.name = name;   }   public long getSalary() {     return salary;   }   public void setSalary(long salary) {     this.salary = salary;   }   public String getEmployeeId() {     return employeeId;   }   public void setEmployeeId(String employeeId) {     this.employeeId = employeeId;   }   public String toString() {     return getName() + " " + this.getSalary() + " " + this.getEmployeeId();   } }

 ============Sample output: =============
List Before sort: In the order of insertion: [Nikhil 745 744, Ranjan 234 746, Adam 999 946]
1st call sorted outcome: Plug EmployeeSortByName comprator [Adam 999 746, Nikhil 745 744, Ranjan 234 946]
2nd call sorted outcome: Plug EmployeeSortBySalary comprator [Ranjan 234  746, Nikhil 745 744, Adam 999 946]
=======================================
In above program unit, we have two different class's(EmployeeSortBySalary and EmployeeSortByName) implementing Comparator interface and writing sorting logic in compare method.  In first call "Collections.sort(list, new EmployeeSortByName());" - instance of EmployeeSortByName is passed and list is sorted based on name. First sorted output reflects that Employee object is sorted based on name(Adam, Nikhil then Ranjan). Remember, natural ordering of strings - alphabetical order. In second call "Collections.sort(list, new EmployeeSortBySalary());" - instance of EmployeeSortBySalary is passe and sorted output is in ascending order of salary.
Please note, here we have implemented out custom logic for natural ordering - returning 1, 0 and -1.
This is all about, Comparable and Comparator interfaces.

==============End of the article====================

Find middle node of a linked list

Problem statement :- Middle element of linked list can be at even or odd position(depending on length of linked list).If size of list is 2n, even no of elements, middle node is at position n+1 and if size of list is n,odd no of elements, then middle element is  (n+1)/2.
Solution 1(Two iteration of list) - Find the length of linked list and traverse again from beginning of list up to half of the linked list(as described above). It is not an efficient approach, because of two iteration.

Solution 2(One iteration of list) - Use two reference, one fast reference and another one slower one. Fast reference moves with twice speed as slow reference. Traverse the linked list with both and the moment fast reference reaches at end of list , slow reference will be at middle of list.

Below is sample code which uses two references and find middle element of list(fast references - 2x  and slow references - x):-

private Node findMiddleElement(Node head) {   Node fast2Xreference = head;   Node slowXRefernce = head;   /* Loop until fast2xReference reaches end of list or last node */   while (fast2Xreference != null && fast2Xreference.next != null) {     slowXRefernce = slowXRefernce.next;     /* check whether, fast reference can go to next to next node */     if (fast2Xreference.next != null)       fast2Xreference = fast2Xreference.next.next;   }   return slowXRefernce; }

Time and space complexity :- Since each node is traversed only once so time complexity is O(n). Space complexity is constant O(1).

Below is complete sample program for finding middle of linked list-

package com.devinline.linkedlist;

public class FindMiddleElementOflInkedList {

private Node findMiddleElement(Node head) {
 Node fast2Xreference = head;
 Node slowXRefernce = head;
 /* Loop until fast2xReference reaches end of list or last node */
 while (fast2Xreference != null && fast2Xreference.next != null) {
  slowXRefernce = slowXRefernce.next;
  /* check whether, fast reference can go to next to next node */
  if (fast2Xreference.next != null)
   fast2Xreference = fast2Xreference.next.next;
 }
 return slowXRefernce;
}

 class Node {
  public int data;
  public Node next; // reference(handler) for next Node.

  public Node(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {
  Node head1;
  Node head2;
  /* First linked list formation - odd number of elements */
  FindMiddleElementOflInkedList fml = new FindMiddleElementOflInkedList();
  Node node1 = fml.new Node(12);
  head1 = node1;
  Node node2 = fml.new Node(18);
  Node node3 = fml.new Node(172);
  Node node4 = fml.new Node(62);
  head1.next = node2;
  head1.next.next = node3;
  head1.next.next.next = node4;
  System.out.println("Even number of elements:-  "
    + "Middle element of linked list [12 18 172 62] is  "
    + +fml.findMiddleElement(head1).data);

  /* Second linked list formation - Even number of elements */
  FindMiddleElementOflInkedList fm2 = new FindMiddleElementOflInkedList();
  Node node12 = fm2.new Node(121);
  head2 = node12;
  Node node22 = fm2.new Node(8);
  Node node32 = fm2.new Node(72);
  Node node42 = fm2.new Node(162);
  Node node52 = fm2.new Node(32);
  Node node62 = fm2.new Node(245);
  head2.next = node22;
  head2.next.next = node32;
  head2.next.next.next = node42;
  head2.next.next.next.next = node52;
  head2.next.next.next.next.next = node62;
  System.out.println("Odd number of elements:-  "
    + "Middle element of linked list [8 72 162 32 245] is "
    + fml.findMiddleElement(head2).data);

 }

}

=============Sample output=================
Even number of elements:-  Middle element of linked list [12 18 172 62] is  172
Odd number of elements:-  Middle element of linked list [8 72 162 32 245] is 162
========================================

Another linked list problems which uses fast and slow references :-
1. To check, linked list has even or odd number of elements.