Saturday, November 10, 2018

Java Collections - Lists

Greetings!

It is probably Lists are the most used Collections.
  • Can have duplicates.
  • Maintain the element order.
  • Can iterate in added order.

Lists maintain the added order. Hence it can be accessed by given position. List interface have additional methods to fulfill this requirement.


// add, remove in given position
void add(int index, E e)
E get(int index)
E remove(int index)
E set(int index, E e)

// search position by object
int indexOf(Object o)
int lastIndexOf(Object o)

// get a sub list by given positions (toIndex exclusive)
List<E> subList(int fromIndex, int toIndex)

// get listiterator
ListIterator<E> listIterator()

  • subList doesn't return a new list. It returns a view of the existing list by given positions. Because of this changing the original list changes the sub list. But changing the sub list doesn't affect the original list.
  • ConcurrentModificationException can be occurred if the original list is changed and try access the sub list.
  • ListIterator has methods to traverse backward using hasPrevious(), previous()

Additionally, Lists implement RandonAccess interface.

ArrayList

  • Implemented as a re-sizable array.
  • add, remove in middle is slow (to shift index).
  • Can get from any position.

LinkedList

  • Implemented as a double linked list.
  • add, remove is fast. (since only the link is affected)
  • accessing an element is slower. (have to traverse through links)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.IntStream;

public class ListsApp {

    public static void main(String[] args) {
        // add operation
        long start = System.nanoTime();
        List<String> arrayList = new ArrayList<>();
        IntStream.range(0, 10000).forEach(i -> arrayList.add("Hello"));
        long arrayListAdd = System.nanoTime() - start;

        start = System.nanoTime();
        List<String> linkedList = new LinkedList<>();
        IntStream.range(0, 10000).forEach(i -> linkedList.add("Hello"));
        long linkedListAdd = System.nanoTime() - start;
        
        System.out.println(arrayListAdd - linkedListAdd);
        
        // get operation
        start = System.nanoTime();
        IntStream.range(0, 10000).forEach(i -> arrayList.get(i));
        long arrayListGet = System.nanoTime() - start;
        
        start = System.nanoTime();
        IntStream.range(0, 10000).forEach(i -> linkedList.get(i));
        long linkedListGet = System.nanoTime() - start;
        
        System.out.println(arrayListGet - linkedListGet);
    }

}




No comments:

Post a Comment