Java) List/ Stack/ Arrays Comparator/ Comparable Iterator

This post was migrated from Tistory. You can find the original here.

List

ArrayList(Vector)

• When you remove an element, every element below it gets copied up one slot to overwrite the removed spot, and the last slot is set to null. That’s why modifying/removing an element near the front is slow.
• Adding an element works the same way in reverse — every subsequent element gets shifted over by one.
• The size can’t be changed. Internally, a new array is created and the data is copied over.

LinkedList

• With an array, all the data sits contiguously in memory, but a linked list is made up of discontiguous data linked together.

• To remove an element, all you need to do is have the previous element’s reference point to the element after the one being removed.
• Adding an element is just as simple — only the references need to change.
• Reads are slow. To get the nth value, you have to walk through the list one node at a time until you reach it.

Bottom line: use ArrayList when the number of elements doesn’t change much, and LinkedList when additions/removals happen frequently.
Even with frequent changes, if they’re sequential (e.g., always adding/removing from the end), ArrayList can still be a reasonable choice.

Stack/Queue

In general, ArrayList is a better fit for a Stack, where elements are added and removed sequentially,
while LinkedList is a better fit for a Queue, which removes the first element that was stored.

public class Main {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();
    }
}

In Java, Stack is provided as a concrete class, while Queue is defined only as an interface.
LinkedList also happens to be a class that implements the Queue interface.

Arrays

public class Main {
    public static void main(String[] args) {
        int[] test = new int[10];
        int count = 0;

        Arrays.fill(test, 5);
        System.out.println(Arrays.toString(test));

        Arrays.setAll(test, (v) -> {
            //count++; 
            // Variable used in lambda expression should be final or effectively final
            return (int) (Math.random() * 5);
        });
        System.out.println(Arrays.toString(test));
    }
}

Result
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[0, 4, 2, 3, 1, 4, 0, 1, 2, 0]

setAll() takes a functional interface as a parameter to use for filling the array.
Any variable used inside the lambda expression must be final.

public class Main {
    public static void main(String[] args) {
        int[] t1 = new int[10];
        int[] t2 = new int[10];
        int[][] test = new int[10][10];
        int[][] test2 = new int[10][10];
        int[][][] test3 = new int[10][10][10];
        int[][][] test4 = new int[10][10][10];

        System.out.println(t1.equals(t2));
        System.out.println(Arrays.equals(test, test2));
        System.out.println(Arrays.deepEquals(test, test2));
        System.out.println(Arrays.deepEquals(test3, test4));
    }
}

Result
false
false
true
true

Array instance .equals(): same as the comparison operator (==)
Arrays.equals(): compares values
Arrays.deepEquals(): compares values in multi-dimensional arrays

Comparator/Comparable

public class Main {
    public static void main(String[] args) {
        Character[] t = {'a','b','c','d','e'};
        Arrays.sort(t);
        System.out.println(Arrays.toString(t));

        Arrays.sort(t, new Descending());
        System.out.println(Arrays.toString(t));
    }
}

class Descending implements Comparator{
    public int compare(Object o1, Object o2){
        if( o1 instanceof Comparable && o2 instanceof Comparable){
            Comparable c1 = (Comparable) o1;
            Comparable c2 = (Comparable) o2;
            return c1.compareTo(c2) * -1;
        }
        return -1;
    }
}

Result
[a, b, c, d, e]
[e, d, c, b, a]

Comparable: used to implement the default sort order
Comparator: used when you want to sort by some criterion other than the default

Comparable source
public interface Comparable<T> {
    public int compareTo(T o);
}

When Arrays.sort(arr) runs, it sorts using the compareTo method of the array’s type (e.g., Integer).

Iterator

Iterator, ListIterator, and Enumeration are all interfaces used to access collection elements.
The Collection interface defines iterator().

public class Main {
    public static void main(String[] args) {
        List<Integer> t = Arrays.asList(new Integer[2]);
        Iterator it = t.iterator();

        while(it.hasNext()){
            System.out.println(it.next());
        }
        System.out.println("===========");
        for(int i=0; i<t.size(); i++){
            Integer val = t.get(i);
            System.out.println(val);
        }
    }
}
Result
null
null
===========
null
null

That’s how it’s used.

Map m = new HashMap();
Set t = m.entrySet();
Iterator it = t.iterator();

For a Map, you use entrySet() or keySet().