Collection Interface and Data Structures in Java

Reading Time: 3 minutes

Collection Interface

Introduction

Collections know also as Data Structures are the fundamentals of each and every programming language. Java provides many of useful data structure for different scenarios and needs. In this blog post I’ll cover only mostly used collections as well as keep things simple, not dive into methods and their details. Because those can be easily assumed and Oracle offers very useful java documentations that explain everything in details, plus you can always go and decompile these classes yourself in your IDE.

Vector, ArrayList and LinkedList

Vector

Vector collection is not usually used by developers, however its internal structure is same as the ArrayList identically, however the major difference is that it is synchronized, thus it is thread-safe. Alternatively developers tend to use the “CopyOnWriteArrayList” collection type or call “Collections.synchronizedList()”.

ArrayList

ArrayList is so far mostly used Data Structure in Java. It internally employs a re-sizable array that grows while adding more element into it. Positional access is very fast in ArrayList because it maintains an array, adding is also fairly faster, but remove operation is fairly slower compared to the LinkedList.

transient Object[] elementData;

Properties:

  • Allows null and duplicate values,
  • Initial capacity is 10,
  • Not synchronized,
  • Maintains insertion order(comparable or comparator can be used)

LinkedList

LinkedList internally maintains a double linked list. This design leads to a hierarchy of linking all the objects to themselves, thus each node knows the previous and the next node. A graphical representation of this structure goes as follows;

Furthermore, the major pitfall of the LinkedList is when we need to perform positional access in the data structure which is a Linear time, because the whole structure must be traversed. Other than that it performs much faster in add and remove.

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

Properties:

  • Allows null and duplicate values,
  • Not synchronized,
  • Maintains insertion order(comparable or comparator can be used)

Performance Comparison

HashSet, TreeSet and LinkedHashSet Comparison

HashMap, Hashtable, TreeMap and LinkedHashMap Comparison