🏫 Java Collections

🏫 Java Collections

💡 Collection (no interface) represents a group of objects, elements, or data.

💡 Java Collections Framework is a unified architecture that provides optimal data structures and essential algorithms for efficient data storage and manipulation.

Java Collections Framework enables developers to concentrate on managing and processing data without having to implement the underlying logic themselves, by offering standardised and optimal data structures and related algorithms as the framework simplifies tasks like searching, sorting, and organising data.

Collection Framework, specifically, implements the Collection interface in the java.util package where the interface is further implemented to other critical interfaces including:

• 🎴 Set
• 〰️ List
• 🖨️ Queue

List is further extended to a Stack, and the Map interface is a component of a Java Collections Framework that does not implement the Collection interface, however, implements the Map interface.

Overall, this can be graphically represented as below:

TechBum Available at here

👴 Iterable

💡 Interable Interface is implemented to the Collection Interface.

Implementing the iterable interface implies that the data will be sequentially managed followed by iterator() and other iterating methods.

Oracle (1) Available at here

👨 Collection

💡Collection Interface is virtually a root interface in the Collection hierarchy in the Collection Framework.

Many methods strictly related to data management are defined where these methods can be implemented individually in the collection classes.

Oracle (2) Available at here

🎴 Set

💡Set is a collection that contains no duplicate and non-sequential elements or data.

Set places stronger emphasis on some methods from the Collection interface including add, equals, and hashcode methods. The beyond is the list of methods that has to be implemented in the Set classes.

Oracle (3) Available at here

The most popular classes implementing the set interface are:

• HashSet

  • offers the constant time operation O(1).
  • non-sequential iteration order.
  • is backed by the HashMap class.

• LinkedHashSet

  • offers the constant time operation O(1) (except for iteration).
  • sequential iteration order.
  • is backed by HashSet and, ultimately the Linked HashMap class.

• TreeSet

  • log(n) time operation
  • orders data by the user set Comparator or by default by the NATURAL_ORDERING.
  • is backed by a TreeMap Class and hence the Red-Black Tree structure.

  ---

LinkedHashSet specifically uses a constructor only designed for the LinkedHashSet class in the HashSet class where a constructor initialises the map to an instance of the LinkedHashMap class.

HashSet & LinkedHashSet

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
     HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
 }


public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ...
  public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
 }

〰️ List

💡 List is a data structure appropriate for the ordered collection where a developer has full control of insertion and the data can be accessed via index.

List allows duplicate data as a part of a collection and the operation cost varies from O(1) to O(n) depending on the operations.

List Interface includes the following methods that are left for individual implementation from implementing classes:

Oracle (5) Available at here

Popular classes implementing the List interface are namely:

• ✅ ArrayList
• 🖨️ Queue
• 🦩 Vector
• 🧱 Stack

---

✅ ArrayList

💡 ArrayList is an implementation of the List interface, which dynamically resizes itself when the data exceeds its capacity.

• ArrayList maintains the order of data storage and allows duplicate values.

• ArrayList offers strengths in fast retrieval (O(1) for accessing elements by index), but operations like insertion and deletion can be slower (O(n)), especially when modifying elements in the middle of the list.

• In-depth, it is backed by an Object array, Object[], in which if the size of the data, n, reaches a cetain threashold resizes followed by its resizing method combined with Arrays.copyOf().

---

🖨️ Queue

💡 Queue is a FIFO (First In, First Out) data structure, commonly used to handle tasks in sequential order.

• Queue ensures that the first element added is the first one to be removed.

• Common operations include offer (adding an element) and poll (removing an element), typically having a time complexity of O(1) for both.

• In Java, queue is often implemented via LinkedList Class where it implements List and Queue interfaces together.

• LinkedList Class internally contains the Node Class where the Node object contains a data and previous and next Node information, implying it is a Doubly-LinkedList.

---

🦩 Vector

💡 Vector is a legacy Collection Class where it is essentially similar to the ArrayList Class, however, is thread-safe.

• Vector is implemented via resisable Object array, Object[] like the ArrayList Class.

• Vector is thread-safe and it is followed by all data operational methods being synchronized methods.

---

🧱 Stack

💡 Stack is a LIFO (Last In, First Out) data structure, where the most recently added element is the first one to be removed.

• Stack is widely used in tasks like function call management, expression evaluation, and undo features.

• Common operations include push (adding an element) and pop (removing the top element).

• Extends the Vector Class, where it implies that the Stack is thred-safe.

---

🗺️ Map

💡 Map is a key-value data structure where there are no duplicate keys.

Map almost always ensures a constant time for basic operations (O(1)), including search, add, remove, and etc, and hence if often used by the developers for performance's sake.

Some methods that are left for individual implementation from the Map classes are:

Oracle (5) Available at here

Most popular classes that implements the map interface are:

• HashMap

  • constant-time performance (O(1)).
  • roughly equivalent to HashTable.
  • permits null key.

• LinkedHashMap

  • constant-time performance (O(1)).
  • implements the HashMap & a doubly-linked list.
  • maintains a doubly-linked list running through all of its entries (preserves key insertion order).

• TreeMap

  • constant-time performance (O(log n)).
  • orders value by the user set Comparator or by default by the NATURAL_ORDERING.
  • A Red-Black tree based NavigableMap implementation.

• Hashtable

  • constant-time performance (O(1)).
  • Java’s legacy classes for storing key-value pairs.
  • synchronised (thread safety) where specifically all data operational methods are synchronized methods.

📚 References

자바의 신
TechBum
Oracle (1)
Oracle (2)
Oracle (3)
Oracle (4)
Oracle (5)