Java Linked List Question

Question

Hello,

Using a Comparator and Iterator, I am trying to add objects into a linked list in order. So far, I have the following:

public class ComparatorClass implements Comparator<Integer> {
    public int compare(Integer int1, Integer int2) {
     return int1.compareTo(int2);
    }
}

and:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;

public class OrderedListInheritance implements LinkedList {

    ArrayList<Object> myList = new ArrayList<Object>();

    Comparator comp = new ComparatorClass();

    OrderedListInheritance(Comparator c) {
     this.comp = c;
    }

    @Override
    public void add(Object o) {
     addLast(o);
    }

    @Override
    public void addAtIndex(int index, Object o) {
     Iterator it = getIterator();
     while (it.hasNext()) {
      Object element = it.next();
      if (comp.compare(element, o) < 0) {

  }else if (comp.compare(element, o) == 0) {

  }else{
   myList.add(o);
  }
     }
    }

    @Override
    public void addFirst(Object o) {
     addAtIndex(0, o);
    }

    @Override
    public void addLast(Object o) {
     addAtIndex(myList.size(), o);
    }

    @Override
    public Object get(int index) {
     return myList.get(index);
    }

    @Override
    public Iterator getIterator() {
     Iterator iter = myList.iterator();
     return iter;
    }

    @Override
    public int indexOf(Object o) {
     return myList.indexOf(o);
    }

}

I am unsure how to use the Iterator in conjunction with the comparator to add each element to the Linked List in order. Can somebody help me with the logic?

Thanks!

Answer 1

Your comparator is wrong.

Part of the general contract for a comparator is that if compare(a, b) is positive, compare(b, a) is negative.

If you pass in a comparator that does not fulfil the comparator contract, you're going to get undefined behaviour.

Answer 2

Is there any reason that you can't just use a normal ArrayList and then call Collections.sort(list) or Collections.sort(list, comparator)?

Answer 3

I would write it like this:

public class IntegerComparator 
    implements Comparator<Integer> 
{
    public int compare(final Integer a, final Integer b) 
    {
        return (a.compareTo(b));
    }
}

I was going to comment more on the code... but what you have given won't work... you declare an ArrayList but then want to use a Comparator and you are not casting... so that won't compile.

The other issue is that you should not use == 1 you should use < 0 and > 0 since the comparator may not return 1, 0, -1 but other numbers as well. Also you are not handling all cases a < b, a == b, and a > b.

Answer 4

Are we doing your homework? Your problem seems to be not so much with the comparator interface as a clear understanding of what you want it to do. This sounds to me like a perfect place to advocate a test driven development style. Start by writing tests to insert into an empty list, insert to the head of a list, insert to the tail, insert in the middle of a list of length 2. Then write tests to return the n'th element and the element with a given value. After you have these simple cases working it will be easy to find the element in an ordered list that is the first one larger than the element to be inserted and add the element in front of the larger one. Don't forget the edge cases of adding a duplicate value, a value smaller than any in the list and a value larger than any in the list.

Answer 5

If you implement the add method to insert the element in sorted order (or anywhere but the end of the list), you are violating the contract of the List interface. Semantically, it's not a List, and it isn't safe to pass it to any code that is expecting one. Pretending to implement the List interface will only lead to trouble.

How about using a TreeSet? instead?

Set<Integer> list = new TreeSet<Integer>();

Of course, a Set will not permit duplicate elements.

If you want something that allows duplicates, but still allows efficient, in-order retrieval, try a heap-based collection, like PriorityQueue.