A Complete Guide - Java Programming ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap
Java Programming: ArrayList vs. LinkedList vs. HashSet vs. TreeSet vs. HashMap vs. TreeMap
Overview
ArrayList
Details:
- Type: Part of the List interface.
- Internal Structure: Backed by a dynamic array.
- Access Time Complexity: O(1) for random access (get/set).
- Insertion/Deletion Time Complexity: Amortized O(1) for appending, O(n) for inserting/removing elements in the middle.
- Threadsafety: Not thread-safe, use
Collections.synchronizedList
to make it thread-safe or considerCopyOnWriteArrayList
. - Order: Maintains insertion order.
- Duplicates: Allows duplicates.
Important Info:
- Use an
ArrayList
when you need fast random access to elements. - It is efficient in operations that add elements only at its end.
- Ideal for scenarios where you perform more read operations than write.
LinkedList
Details:
- Type: Part of the List and Deque interfaces.
- Internal Structure: Implements a doubly-linked list.
- Access Time Complexity: O(n) for random access.
- Insertion/Deletion Time Complexity: O(1) for insertions/deletions at the beginning and end of the list.
- Threadsafety: Not thread-safe.
- Order: Maintains insertion order.
- Duplicates: Allows duplicates.
Important Info:
- Suitable for operations involving frequent additions and removals from both ends.
- Provides constant time complexity for adding and removing elements from the head or tail, but linear time for accessing elements by index.
- Can be used as a stack or queue, thanks to its
Deque
implementation.
HashSet
Details:
- Type: Part of the Set interface.
- Internal Structure: Uses a hash table (backed by a
HashMap
). - Time Complexity: Average O(1) for add, remove, contains, and size operations.
- Threadsafety: Not thread-safe.
- Order: Does not guarantee any specific order of elements.
- Duplicates: Does not allow duplicate elements.
Important Info:
- Best for applications requiring quick addition, deletion, and lookup operations.
- Ensures no duplicates by using an underlying hash table.
- Does not maintain any order of elements, making iterations over a
HashSet
unpredictable.
TreeSet
Details:
- Type: Part of the SortedSet interface.
- Internal Structure: A NavigableSet based on a TreeMap.
- Time Complexity: O(log n) for most operations (add, remove, contains, size).
- Threadsafety: Not thread-safe.
- Order: Sorted order.
- Duplicates: Does not allow duplicates.
Important Info:
- Ideal for maintaining ordered data sets.
- Ensures that there are no duplicate elements.
- Offers additional operations like finding nearest matches (
higher()
,lower()
).
HashMap
Details:
- Type: Part of the Map interface.
- Internal Structure: Uses a hash table.
- Time Complexity: Average O(1) for put, get, remove, and containsKey operations.
- Threadsafety: Not thread-safe.
- Order: Does not guarantee any particular order (except if using
LinkedHashMap
). - Duplicates: Keys are unique; values can have duplicates.
Important Info:
- Provides high-performance key-value pair storage.
- Suitable for applications where average-case constant-time performance is required.
- Iteration over keys, values, or entries can yield unpredictable order unless specified.
TreeMap
Details:
- Type: Part of the SortedMap interface.
- Internal Structure: A Red-Black tree based NavigableMap.
- Time Complexity: O(log n) for most operations (put, get, remove, containsKey).
- Threadsafety: Not thread-safe.
- Order: Sorted keys.
- Duplicates: Keys are unique; values can have duplicates.
Important Info:
- Maintains keys in sorted order.
- Useful for scenarios where data must be maintained in a sorted form.
- Supports range queries using methods like
subMap()
,headMap()
, andtailMap()
.
General Keyword Context
The collections framework in Java (ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap) offers rich functionalities to handle data structures efficiently across various application domains:
- Performance Optimization: Choosing the right collection type can significantly impact application performance.
- Memory Management: These structures help in managing memory by handling object storage and resizing dynamically.
- Iteration: They provide convenient ways to iterate through the elements, with support for forward and backward traversals.
- Data Integrity: Classes like
HashSet
andTreeSet
enforce uniqueness constraints. - Sorting:
TreeSet
andTreeMap
automatically sort their elements, ensuring data integrity. - Concurrency: Java provides thread-safe variants or utilities for concurrent modifications in multithreaded applications.
- Flexibility: The collections framework supports polymorphism and other OOP principles, making them flexible and reusable.
Online Code run
Step-by-Step Guide: How to Implement Java Programming ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap
1. ArrayList
Step-by-Step Example:
Step 1: Import the ArrayList class
First, you need to import the ArrayList
class from the java.util
package.
import java.util.ArrayList;
Step 2: Create an ArrayList object
Create an instance of the ArrayList
class. Typically, you specify the type of elements it will hold using generics.
public class ArrayListExample { public static void main(String[] args) { // Create an ArrayList to store Strings ArrayList<String> arrayList = new ArrayList<>(); // Adding elements to the ArrayList arrayList.add("Apple"); arrayList.add("Banana"); arrayList.add("Cherry"); // Displaying elements of the ArrayList System.out.println("ArrayList: " + arrayList); }
}
Step 3: Access, modify, and remove elements
You can access, modify, and remove elements in an ArrayList
.
// Accessing elements by index
String fruit = arrayList.get(1); // Get the fruit at index 1 (Banana)
System.out.println("Fruit at index 1: " + fruit); // Modifying elements by index
arrayList.set(1, "Blueberry"); // Change the fruit at index 1 to Blueberry
System.out.println("ArrayList after modification: " + arrayList); // Removing elements by index or value
arrayList.remove(0); // Remove the element at index 0 (Apple)
arrayList.remove("Cherry"); // Remove Cherry directly
System.out.println("ArrayList after removal: " + arrayList);
2. LinkedList
Step-by-Step Example:
Step 1: Import the LinkedList class
import java.util.LinkedList;
Step 2: Create a LinkedList object
public class LinkedListExample { public static void main(String[] args) { // Create a LinkedList to store Strings LinkedList<String> linkedList = new LinkedList<>(); // Adding elements to the LinkedList linkedList.add("Dog"); linkedList.add("Cat"); linkedList.add("Bird"); // Displaying elements of the LinkedList System.out.println("LinkedList: " + linkedList); }
}
Step 3: Access, modify, and remove elements
// Accessing elements by index
String animal = linkedList.get(1); // Get the animal at index 1 (Cat)
System.out.println("Animal at index 1: " + animal); // Modifying elements by index
linkedList.set(1, "Fox"); // Change the animal at index 1 to Fox
System.out.println("LinkedList after modification: " + linkedList); // Removing elements by index or value
linkedList.remove(0); // Remove the element at index 0 (Dog)
linkedList.remove("Bird"); // Remove Bird directly
System.out.println("LinkedList after removal: " + linkedList);
3. HashSet
Step-by-Step Example:
Step 1: Import the HashSet class
import java.util.HashSet;
Step 2: Create a HashSet object
public class HashSetExample { public static void main(String[] args) { // Create a HashSet to store Strings HashSet<String> hashSet = new HashSet<>(); // Adding elements to the HashSet hashSet.add("Red"); hashSet.add("Green"); hashSet.add("Blue"); // Displaying elements of the HashSet System.out.println("HashSet: " + hashSet); }
}
Note: Elements are stored in no particular order. Also, HashSet
does not allow duplicate elements.
Step 3: Check for existence and remove elements
// Checking if an element exists in the HashSet
boolean containsGreen = hashSet.contains("Green");
System.out.println("Contains Green: " + containsGreen); // Removing elements from the HashSet
hashSet.remove("Blue"); // Remove Blue directly
System.out.println("HashSet after removal: " + hashSet);
4. TreeSet
Step-by-Step Example:
Step 1: Import the TreeSet class
import java.util.TreeSet;
Step 2: Create a TreeSet object
public class TreeSetExample { public static void main(String[] args) { // Create a TreeSet to store Integers TreeSet<Integer> treeSet = new TreeSet<>(); // Adding elements to the TreeSet treeSet.add(5); treeSet.add(3); treeSet.add(8); // Displaying elements of the TreeSet System.out.println("TreeSet: " + treeSet); }
}
Note: Elements in TreeSet
are stored in sorted order, and no duplicates.
Step 3: Perform operations like navigation to first and last element
// Accessing the first and last element in the TreeSet
int first = treeSet.first(); // Get the smallest element (3)
int last = treeSet.last(); // Get the largest element (8) System.out.println("First element: " + first);
System.out.println("Last element: " + last); // Removing elements from the TreeSet
treeSet.remove(5); // Remove 5 directly
System.out.println("TreeSet after removal: " + treeSet); // Additional: Navigating elements
Integer lower = treeSet.lower(8); // Get the largest element less than 8 (3)
Integer higher = treeSet.higher(3); // Get the smallest element greater than 3 (8) System.out.println("Lower element of 8: " + lower);
System.out.println("Higher element of 3: " + higher);
5. HashMap
Step-by-Step Example:
Step 1: Import the HashMap class
import java.util.HashMap;
Step 2: Create a HashMap object
public class HashMapExample { public static void main(String[] args) { // Create a HashMap to store (String, Integer) key-value pairs HashMap<String, Integer> hashMap = new HashMap<>(); // Adding key-value pairs to the HashMap hashMap.put("Alice", 25); hashMap.put("Bob", 30); hashMap.put("Charlie", 35); // Displaying key-value pairs of the HashMap System.out.println("HashMap: " + hashMap); }
}
Step 3: Access, modify, and remove key-values
// Accessing the value of a key in the HashMap
int aliceAge = hashMap.get("Alice");
System.out.println("Alice's Age: " + aliceAge); // Modifying the value of a key in the HashMap
hashMap.put("Alice", 26); // Change Alice's age to 26
System.out.println("HashMap after modification: " + hashMap); // Removing a key-value pair from the HashMap
hashMap.remove("Bob"); // Remove Bob's entry directly
System.out.println("HashMap after removal: " + hashMap);
6. TreeMap
Step-by-Step Example:
Step 1: Import the TreeMap class
import java.util.TreeMap;
Step 2: Create a TreeMap object
public class TreeMapExample { public static void main(String[] args) { // Create a TreeMap to store (Integer, String) key-value pairs TreeMap<Integer, String> treeMap = new TreeMap<>(); // Adding key-value pairs to the TreeMap treeMap.put(10, "Ten"); treeMap.put(5, "Five"); treeMap.put(20, "Twenty"); // Displaying key-value pairs of the TreeMap System.out.println("TreeMap: " + treeMap); }
}
Note: Keys in TreeMap
are stored in sorted order, and no duplicate keys are allowed. The values can be duplicate though.
Login to post a comment.