Competitive Programming with Java : Collections 01

 

practically most of programming contests have problems that consist of giving you data of some kind, and you need to do something with it, some other times an algorithm needs a special kind of data structure so knowing the one that you need can really help you find a solution faster , or reducing a very large amount of code , into small pieces and today we are going to look at what the java standard library has to offer when it comes to different types of collections , so let’s begin :

List :

Java Lists are ordered Collections, where you can access their elements by integer index , so if you don’t know the size of your data beforehand, just use Lists .

List is a Java interface which means it’s just  a contract or a specification that defines what the actual implementation should do (To do well with Java you should get a good grasp of object oriented programming which is out of the scope of this tutorial ) .
In the standard library you will find three major implementations : ArrayList , LinkedList and Vector they all provide practically the same usual methods add(E) remove(E) and contains(E) … but they differ in the internal implementation .

• LinkedList :
  The name says a lot about the internal implementation, it’s constructed as a Doubly linkedList they are great when it comes to adding at a specific index or for removing , but they are not that great with random access, worst case complexity is O(N/2) where N is the number of elements in the list, which is not that good
• ArrayList :
  Which what you will be using most of the time, cause in competitive programming you rarely use the remove operation from a continuous array of data, and we need fast access by index, and constant time add operations .
  ArrayList is implemented using an internal dynamically sized array. add(E) and get(index) operations have an O(1) time complexity .
• Vector :
  They offer same functionality as ArrayList but the problem is that they are synchronized, meaning an additional check is done before doing any operation to check for concurrent use of the resource (check java concurrency to understand more ..). What you should keep in mind is that this operation causes an additional unnecessary overhead which cause performance issues

	List<Integer> list = new ArrayList<>();
	// filling the list
	for(int i = 0; i < 10; i++){
	list.add(42);
	}
	System.out.println(list.get(0)); // it will print 42
	// exercice : what will be the result of list.remove(42)
	// hint it will throw an exception 😀

view raw

ArrayList.java

hosted with ❤ by GitHub

Using LinkedList or ArrayList have also another difference : memory usage . memory consumption is much bigger in linkedList, because the creation of every element causes the creation of a node object, the picture show the comparison between the two :

Set :

Java sets are collections with no duplicate elements in them, I.E you can’t find in the same set an object A and another Object B with A.equals(B) is true .

Just like Lists, it depends on the specific implementation of the set (Set again is an interface), you can find the 2 most used implementations of Set , HashSet and TreeSet .

HashSet :

A set implementation that doesn’t care about the ordering of the elements in the set, but it guarantees a constant time performance when it comes to operations such a (add(E), remove(E), and contains(E)) .
The internal implementation of set is basically a Map() ( a HashMap really ) where the keys are the elements of the set and the values are just ordinary Objects created like :

    Object o = new Object(); // a dummy Object basically

TreeSet :

A set implementation that guarantees ordering of the elements and provides extra functionality . the only down side of using it is the extra amount of complexity : O(Log(N)) for the usual operations .

Another thing about TreeSet is when you create it you need to specify the ordering of it’s elements . the natural ordering is followed if a
Comparator is not specified . for better understanding take a look the tutorial code in the github repo .

And again which one to use depends on the use case, and you have your own judgment for that .

Map :

Java maps are collections thats stores their elements in the form of key value pairs, one key maps to at most one value .
Depending on the implementation the keys ordering might have a guaranteed order, and if that’s the case a Comparator Object is needed to alter and customize the sorting behaviour .

As for the internal implementation i already wrote about it in my blog a while ago so you need to go check it out to better understand the mechanics of Java maps .

The github repository has code examples to create and operate on the collections discussed above , in the next tutorial we will take a look at other collections provided by the Java Standard library .

link to the github repo .