Sorting a List alphabetically using compareTo() method

Question

I am writing a phonebook program in java and i need to list people in the list alphabetically and to do that i need to write a sorting algorithm for a list in java and it should use only compareTo() method. So can anyone help me to do that?

public void listAlpha()
 {
     Node tempNode = head;

     for(int i = 0; i <= size; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                int comparison = ((tempNode.getNext().getElement().getName()).compareTo(tempNode.getElement().getName()));
                if(comparison < 0)
                {
                    Person tempPerson =  tempNode.getElement();

                    tempNode.setElement(tempNode.getNext().getElement());
                    tempNode.getNext().setElement(tempPerson);
                    tempNode = tempNode.getNext();
                }
            }


        }

(By the way this is a homework and i am using my own data structures.)

This is the class that method i wrote above belongs:

import java.util.*;

/** Singly linked list implementation .*/
public class SLinkedList<E> implements LinkedList<E>, Iterable<E> {
  protected Node<E> head;       // head node of the list
  protected Node<E> tail;       // tail node of the list
  protected int size;       // number of nodes in the list

    public Iterator<E> iterator()
    {
        return new LinkedListIterator(head);
    }

  /** Default constructor that creates an empty list */
  public SLinkedList() {
    head = null;
    tail = null;
    size = 0;
  }

  public int size() { 
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public void addFirst(E newElement) {
    Node<E> newNode = new Node(newElement,null);
    if(size == 0) //if list is empty
        tail = newNode;

    newNode.setNext(head);
    head = newNode;
    size++;
  }

  public void addLast(E newElement) {
    Node<E> newNode = new Node(newElement,null);

    if(size == 0) //if list is empty
        head = newNode;

    if (size != 0) //if list is not empty
        tail.setNext(newNode);

    tail = newNode;
    size++;
  }

  public E removeFirst() {
    Node<E> tempNode = null;
    if (size != 0) {
        if(size == 1)
            tail = null;

        tempNode = head;
        head = head.getNext();
        tempNode.setNext(null);
        size--;
    }

    //if list is empty then return null
    return tempNode.getElement(); 

  }

  public E removeLast() {
    Node<E> tempNode = head;

    if(size == 0)
        return null;

    if(size == 1) {
        head = null;
        tail = null;
        size--;
        return tempNode.getElement();
    }

    //size is greater than 1
    for(int i=1; i<=size-2; i++) {
        tempNode = tempNode.getNext(); //go to element that before the tail
    }

    Node<E> tempNode2 = tail;
    tail = tempNode;
    tail.setNext(null);
    size--;
    return tempNode2.getElement();

  }

  public void remove(E element){
    int index = 0;
    boolean found = false;
    Node<E> temp = head;
    for(int i=1; i<=size; i++) {//find the node with element
        index++;
        if(temp.getElement().equals(element)){
            found = true;
            break;
        }
        temp = temp.getNext(); 
    }

    if(found){
        if(index == 1) 
            removeFirst();

        else if(index == size)
            removeLast();

        else{   
            //find the previous node
            Node<E> prev = head;
            for(int i=1; i<index-1; i++) {
                prev = prev.getNext(); 
            }

            prev.setNext(temp.getNext());
            temp.setNext(null);
            size--;
        }
    }
  }

  public int searchList(E searchKey) {
    if(size == 0)
        return -1;

    Node tempNode = head;
    for(int i=1; i<=size; i++) {
        if(tempNode.getElement().equals(searchKey))
            return i; //return index of the node
        tempNode = tempNode.getNext();
    }

    return -1; //not found
  }

  public void printList() {
    Node tempNode = head;
    for(int i=1; i<=size; i++) {
        System.out.print(tempNode.getElement());
        if(i!=size) //if it is not last element
            System.out.print(" - ");
        tempNode = tempNode.getNext();
    }
    System.out.println();

  }

Person class:

public class Person
{
    private String name;
    private String surname;
    private String address;
    private PhoneNumber phone1;
    private PhoneNumber phone2;
    private PhoneNumber phone3;

    public Person()
    {
        name = null;
        surname = null;
        address = null;
        phone1.setPhone(0);
        phone1.setType("");
        phone2.setPhone(0);
        phone2.setType("");
        phone3.setPhone(0);
        phone3.setType("");
    }

    public Person(String n, String s, String a,PhoneNumber p1, PhoneNumber p2, PhoneNumber p3)
    {
        name = n;
        surname = s;
        address = a;
        phone1 = p1;
        phone2 = p2;
        phone3 = p3;

    }

    public String getName()
    {
        return name;
    }

    public void setName(String n)
    {
        name = n;
    }
    public String getSur()
    {
        return surname;
    }

    public void setSur(String s)
    {
        surname = s;
    }

    public void insertPhone(PhoneNumber phone)
    {
        if(phone2 == null)
            phone2 = phone;
        else if(phone3 == null)
            phone3 = phone;
    }

    public PhoneNumber getPhone1()
    {
        return phone1;
    }

    public PhoneNumber getPhone2()
    {
        return phone2;
    }

    public PhoneNumber getPhone3()
    {
        return phone3;
    }

    public String getAdd()
    {
        return address;
    }

    public void setAdd(String a)
    {
        address = a;
    }

Solution 1

As everyone else has mentioned, compareTo is part of the Comparable interface.

How you implement it depends on whether you want to order by surname or name first and if you want them sorted ascending order.

For example, if you want to order by surname first, in ascending order:

public class Person implements Comparable<Person> {
    // the parts of Person you already have would go here
    public int compareTo(Person person) {
        if (person == null) {
            return -1;
        }

        if (surname != null && person.getSur() == null) {
            return -1;
        } else if (surname == null && person.getSur() != null) {
            return 1;
        } else if (surname != null && person.getSur() != null) {
            int compare = surname.compareToIgnoreCase(person.getSur());
            if (compare != 0) {
                return compare;
            }
        }
        // Note that we did nothing if both surnames were null or equal

        if (name == null && person.getName() == null) {
            return 0;
        } else if (name != null && person.getName() == null) {
            return -1;
        } else if (name == null && person.getName() != null) {
            return 1;
        } else {
            return name.compareToIgnoreCase(person.getName());
        }
    }
}

(I didn't actually test this code)

This relies on String's implementation of compareToIgnoreCase.

Note that this also moves all null objects and objects with null names and surnames to the end of the list.

Having said all that, if you implement Comparable, you can make the Collections API do the work for you using sort.

If you find that you need multiple different sort methods for an object, you can create a set of Comparator objects to do the sorting instead.

Solution 2

You can make your Person class implement Comparable, and define the following method:

    public class Person implements Comparable<Person> {

       // Your previous code

       public int compareTo(Person other) {
          if (other == null) {
             // throw exception for example
          }
          return this.name.toLowerCase().compareTo(other.name.toLowerCase());
       }
    }