Java Basic Data Structure | You must know

Arrays: 

Java Arrays is an object that stores similar types of objects. It stores data in a contiguous memory location.  It's a primitive data structure of java. 

List:

The list is an interface that extends the collections interface. It's implemented by ArrayList, LinkedList, Stack, Queue, Vector, etc.

Set:
A collection that doesn't allow duplicate elements inside it. More formally, the set contains no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. This interface is implemented by HashSet, TreeSet, EnumSet, etc.
So formal characteristics:
1. it contains the distinct element
2. doesn't guarantee the order of elements.

Map:  

A map is an interface, it's a collection of key-value pairs. Note that the key can't be duplicated and each key can map to at most one value.
One very important point: if you use any object as a key, then must override equals and hashCode methods, otherwise it will produce the wrong result. It is implemented by HashMap, TreeMap, etc.

Java HashMap implementation:

HashMap implements an array of nodes, and the node is represented as a class. It uses an array and LinkedList data structure internally for storing Keys and Values. There are four fields in HashMap.

        1. generate hashCode for a given key

        2. calculate array index value using formula:    index = hashCode & (size-1).

                Note that the default size of the array is 16.

        3. put in that index as a LinkedList node.

insertion and accessing amortized complexity is O(1). you can check out link.

Difference Among HashMap, TreeMap, LinkedHashMap.

HashMap

• HashMap has the complexity of O(1) for insertion and lookup.

• HashMap allows one null key and multiple null values.

• HashMap does not maintain any order.

TreeMap

• TreeMap has the complexity of O(logN) for insertion and lookup.

• TreeMap does not allow a null key but allows multiple null values.

• TreeMap maintains order. It stores keys in sorted and ascending order. It is implemented by a Red-Black tree which is a balanced Binary Search tree (BST). But It is not thread-safe.

LinkedHashMap

• LinkedHashMap has the complexity of O(1) for insertion and lookup.

• LinkedHashMap allows one null key and multiple null values.

• LinkedHashMap maintains the order in which key-value pairs are inserted.

Last modified: 08.10.2022