Introduction to ArrayLists:
Data structures represent collections of related data using a single variable. Arrays are one type, while ArrayLists are another.
Example: Arrays have a fixed size, making reordering difficult:
int[] myArray = {1, 2, 3}; // Fixed size
In contrast, ArrayLists have a dynamic size:
ArrayList<Integer> myList = new ArrayList<>(); // Dynamic size
myList.add(1); // Add elements
myList.add(2);
myList.add(3);
ArrayList Basics:
An ArrayList is a class in Java, part of the java.util Package, and can only store references to objects (e.g., Strings, Integers). Primitive types must be wrapped in their corresponding wrapper classes (e.g., Integer, Double).
ArrayList<String> names = new ArrayList<String>(); // Stores Strings
ArrayList<Integer> nums = new ArrayList<Integer>(); // Stores Integers
Declaration Example:
The default constructor creates an empty ArrayList with a capacity of 10:
ArrayList<String> names = new ArrayList<>(); // Initial size = 0, capacity = 10
Capacity vs. Size:
Capacity refers to the size of the internal array, while size refers to the number of elements in the ArrayList. If the capacity is exceeded, a new larger array is created.
Example:
ArrayList<Integer> myList = new ArrayList<>(2); // Initial capacity of 2
myList.add(1);
myList.add(2);
myList.add(3); // Triggers resizing
Printing ArrayLists:
You can print an entire ArrayList directly using System.out.println(myList), which utilizes the toString method.
Example:
System.out.println(myList); // Output: [1, 2, 3]
Alternative Declarations:
ArrayLists can also be declared using the List interface:
List<Integer> myArray = new ArrayList<Integer>(); // Using List interface
A shorthand declaration is also possible:
ArrayList<Integer> myList = new ArrayList<>(); // Diamond operator
Auto-Boxing and Unboxing:
Collections like ArrayLists cannot contain primitive types directly. Auto-boxing allows automatic conversion of primitives to their wrapper classes when added to an ArrayList, and auto-unboxing retrieves the primitive value automatically.
Example:
ArrayList<Integer> myI = new ArrayList<>();
myI.add(7); // Auto-boxing: 7 is wrapped as Integer
int num = myI.get(0); // Unboxing: retrieves 7 as int
ArrayList Methods:
Common methods include:
size(): Returns the number of elements.
System.out.println(myList.size()); // Output: 3
add(x) and add(int x, Element y)
Inserts an object at a specified index.
myList.add(3,9); //inserts 9 at position 3
System.out.println(myList);// Output:
get()
set(int x, Element y)
remove(int x)
myList.remove(6);
ArrayList Traversal and Common Algorithms
ArrayList Traversal
1. Traditional for loop:
- Syntax:
for(int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
2. Enhanced ("for-each") loop:
- Syntax:
for(String each : list)
{
System.out.print(each + " ");
}
- Note: You can't modify primitive values or access the index with the "for-each" loop.
ArrayList Pitfalls
1. Problem: IndexOutOfBoundsException
Removing elements during traversal with a traditional for loop can cause this exception. Avoid removing elements inside the loop using changing indices.
2. Example of Pitfall (runtime error):
for (int i = 0; i < words.size(); i++) {
if ("like".equals(words.get(i))) {
words.remove(i);
}
}
3. Correct approaches:
- While loop approach:
int i = 0;
while (i < words.size()) {
if ("like".equals(words.get(i))) {
words.remove(i);
} else {
i++;
}
}
- Reverse loop approach:
for (int i = words.size() - 1; i >= 0; i--) {
if ("like".equals(words.get(i))) {
words.remove(i);
}
}
#### Common ArrayList Algorithms
1. Finding Maximum Value in ArrayList:
int max = list.get(0);
for (int i = 0; i < list.size(); i++) {
if (list.get(i) > max) {
max = list.get(i);
}
}
2. Getting Outliers from an Array of Doubles:
- Method to find scores greater than 20 points above or below the average.
public static ArrayList<Double> getOutliers(double scores[]) {
ArrayList<Double> outliers = new ArrayList<Double>();
double sum = 0;
for (int i = 0; i < scores.length; i++) {
sum += scores[i];
}
double avg = sum / scores.length;
for (int i = 0; i < scores.length; i++) {
if (Math.abs(scores[i] - avg) > 20) {
outliers.add(scores[i]);
}
}
return outliers;
}
Searching and Sorting
Searching Algorithms
1. Sequential Search:
- Can be used for unsorted data.
- Starts from the first element and checks each one until it finds the target or reaches the end.
- Best Case: Target found in the first position.
- Worst Case: Target not found or in the last position.
- Average Case: Target found after n/2 comparisons.
- Example code:
public static int sequentialSearch(int[] elements, int target) {
for (int j = 0; j < elements.length; j++) {
if (elements[j] == target) {
return j;
}
}
return -1;
}
Sorting Algorithms
1. Selection Sort:
- Finds the minimum value in the list and swaps it with the first element, repeats for the entire list.
- Example code:
public static void selectionSort(int[] elements) {
for (int j = 0; j < elements.length - 1; j++) {
int minIndex = j;
for (int k = j + 1; k < elements.length; k++) {
if (elements[k] < elements[minIndex]) {
minIndex = k;
}
}
int temp = elements[j];
elements[j] = elements[minIndex];
elements[minIndex] = temp;
}
}
- Efficiency:
- Time Complexity: O(n²) (quadratic)
- Best, Worst, and Average Case: Always the same number of comparisons (n-1 passes).
2. Insertion Sort:
- Sorts the array incrementally by inserting the next item into the sorted portion of the list.
- Example code:
public static void insertionSort(int[] elements) {
for (int j = 1; j < elements.length; j++) {
int temp = elements[j];
int possibleIndex = j;
while (possibleIndex > 0 && temp < elements[possibleIndex - 1]) {
elements[possibleIndex] = elements[possibleIndex - 1];
possibleIndex--;
}
elements[possibleIndex] = temp;
}
}
- Efficiency:
- Best Case: O(n) (if the array is already sorted)
- Worst Case: O(n²) (if the array is in reverse order)
Knowt
