Java Collections

Question 1

What are Collections?

Answer 1

§ The Collection in Java is a framework that provides an architecture to store and manipulate the group of objects.
§ Java Collections can achieve all the operations that you perform on a data such as searching, sorting, insertion, manipulation, and deletion.
§ Java Collection means a single unit of objects.
Java Collection framework provides many interfaces (Set, List, Queue, Deque) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet).

Question 2

What are data structures?

Answer 2

Data structures are objects that provide a way to store and organize data to use (access/modify) efficiently.

Question 3

Which are the most popular interfaces in Java Collections Framework?

Answer 3

SET, LIST, MAP

• Collection is anything holding data called "elements" (of the same type). Nothing more specific is assumed.
• List is an indexed collection of data where each element has an index. Something like the array, but more flexible. Data in the list keep the order of insertion. Typical operation: get the n-th element.
• Set is a bag of elements, each elements just once (the elements are distinguished using their equals() method. Data in the set are stored mostly just to know what data are there. Typical operation: tell if an element is present in the list.
• Map is something like the List, but instead of accessing the elements by their integer index, you access them by their key, which is any object. Like the array in PHP :) Data in Map are searchable by their key. Typical operation: get an element by its ID (where ID is of any type, not only int as in case of List).

Question 4

What is the use case for “List”?

Answer 4

Lists are used for ordered data collection, where the placement of the object is essential.

Question 5

What is the use case for “Set”

Answer 5

Sets are used for data collection, where no duplicate objects can be present.

Question 6

What is the use case for “Queue”

Answer 6

Queues are used for ordered data collection, where operations with the first/last elements are performed.

Question 7

What is the use case for “Map”?

Answer 7

Maps are used for data collection as key-value pairs.

Question 8

What is the use case for “Priority Queue”?

Answer 8

Priority queues are used for ordered data collection, where objects are processed based on a defined ‘priority’ using comparators.

Please note that PriorityQueue is a class in Java Collections Framework, not an interface. The aim of this question is to demonstrate understanding of the Heap data structure.

Question 9

How is “Map” interface different from most of the other JCF (Java Collections Framework) interfaces?

Answer 9

Other JCF interfaces store collections of single objects and implement the ‘Collection’ interface, but ‘Map’ stores object key-value pairs.

Question 10

Compare the differences of ARRAY, ARRAYLIST and LINKEDLIST.

Answer 10

a. Array is a fixed size collection, where you have to define the size at creation (where a memory space of that size is reserved), possible to store primitives, which is not the case for JCF collections.
b. ArrayList is an implementation of List interface, has some initial capacity which changes dynamically. The main advantage is speed when accessing objects by the index for large volumes.
c. LinkedList is an implementation of List and Queue interface, has no initial capacity as all objects are stored as nodes (objects that have information on previous and next element). Main advantages are when the collection is frequently changing, and functionality of queue is needed (working with first/last elements).

Question 11

What do these abbreviations mean in the context of data structures FIFO, FILO?

Answer 11

○ FIFO is an abbreviation for “First in First out”. It is a method for handling data structures where the first element is processed first and the last element processed last.
–> QUEUE (like a line to a rollercoaster or postal office, or a printer)
○ FILO is an abbreviation for “First in Last out”. It is a method for handling data structures where the first inserted element is processed last, and the most recently inserted element is processed first.
–> STACK (like a stack of dishes in the sink)

Question 12

What is the “Big-O” notation?

Answer 12

Big-O notation describes how fast an algorithm is in terms of the number of operations it makes. It shows how the number of operations grows as you add more items for the algorithm to process.

Question 13

What’s the efficiency of inserting an element in a random place in LinkedList?

Answer 13

Inserting an element at a random location in a linked list only requires to update the pointers of the element before it and after it.
As such, it is an efficient linear-time operation - 0(1).

Question 14

What’s the efficiency of accessing a random element place in LinkedList?

Answer 14

Elements in a linkedlist do not have a linear location in memory. The algorithm must go through the list until finding the desired element’s location to access it. It can be very inefficient if the location isn’t at the start of the list, as the algorithm requires traversing many elements. At worst, it’s a linear-time operation - O(n).

Question 15

What’s the efficiency of accessing a random element in an ArrayList?

Answer 15

ArrayLists are backed by arrays. Accessing a random location is efficient because each item has a known offset in memory. It’s a constant-time operation - O(1).

Question 16

What are the insert and access efficiencies of HashSet and HashMap?

Answer 16

Inserting and accessing HashSet elements is efficient, as it is possible to provide a key and an element can be retrieved immediately without traversing or moving other elements. Inserting and accessing has a constant-time efficienct - O(1) - on average, but due to hash collisions, it is possible to have O(n) worst time efficiency for access.

Question 17

What are the insert and access efficiencies of PriorityQueue?

Answer 17

PriorityQueue access is the most efficient - 0(1) - if it is required to retrieve an element based on a priority (smallest, largest, alphabetical, etc) because it will always be at the start of the queue.
Inserting is not as efficient - O(log n) - because each time an element is inserted, it needs to be moved based on a priority across the queue until reaching an appropriate location in the backing heap.

Question 18

When is the use of LinkedHashMap more appropriate than the use of HashMap?

Answer 18

LinkedHashMap is better than HashMap if the order of inserted elements is essential / should be remembered.

Question 19

When is the use of TreeMap more appropriate than use of a HashMap?

Answer 19

We should use TreeMap over HashMap if we should organize the elements in some hierarchical structure but accessing a random element is not as important.

Question 20

Difference between an ArrayList and Map?

Answer 20

ArrayList is a class that implements the List and Collection interface.
Map is an interface separate from the Collection interface.

The difference between ArrayList and HashMap is that ArrayList is an index-based data-structure supported by array, while the HashMap is a mapped data structure, which works on hashing to retrieve stored values. Although both are used to store objects, they are different in their implementation, function, and usage.

HashMap stores elements in Key and value pairs.
HashMap does not provide a guarantee of the order in which they are inserted.
HashMap allows duplicate values but does not allow duplicate keys.

Question 21

Difference between TreeSet and HashSet?

Answer 21

Simply put, HashSet is faster than the TreeSet.

HashSet provides constant-time performance for most operations like add(), remove() and contains(), versus the log(n) time offered by the TreeSet.