7. ArrayList

/* 
Writer: SP
Date: April 3rd
References: Fiveable
Unit 7: ArrayList */

Introduction

There are several data structures to store data in Java.

  • Sets, Lists, Deques, and Maps

  • We will mainly concern about lists.

    • Two main types:

      • LinkedLists & ArrayLists.

LinkedLists: We can only access elements in order.

  • If we want to access the 9th element, we have to start with the first element and then traverse.

We can access elements in the middle of the list much more easily in ArrayList.

We can only put reference types inside ArrayLists.

Using ArrayLists

We need to import ArrayList to use it.

import java.util.ArrayList;

// TO make

ArrayList list = new ArrayList();

// We can use generic to specify which objects that ArrayList will store. 

ArrayList<E> llist = new ArrayList<E>();

// Storing integers

ArrayList<Integer> lllist = new ArrayList<Integer>();

Why ArrayLists?

  • When it comes to Array, it has a fixed size.

  • However, ArrayList is more dynamic.

Methods

  1. Adding elements to the end of an arrayList.

// main code
boolean add(E obj);
// because whether added successfully or not. 

// lets use
import java.util.ArrayList;

ArrayList<Integer> integerList = new ArrayList<Integer>();

integerList.add(3); // Add 3.

  1. Accessing ArrayList Elements

// two main methods

int size(); // return the size

E get (int index); // return the specific value in the given index. 

// Let's assume ArrayList has the items: 3, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10. 

integerList.get(1); => Return 4

  1. Adding elements to the beginning or middle of an arrayList

void add(int index, E obj); // Add object in specific index

  1. Removing elements from an arraylist

E remove(int index); // remove object in specific index

  1. Modifying elements in an ArrayList

E set(int index, E obj); // Change the value in specific index with given object.

Traversing ArrayLists

We can traverse Arraylists using for loops and enhanced for loops.

int[] Array = new int[5];
ArrayList<Integer> List = new ArrayList<Integer>();

for (int i = 0; i < Array.length; i++) { 
   System.out.println(Array[i]);
}

for (int ii = 0; i<List.size(); i++) { 
   System.out.println(List.get(ii);
}

We can traverse ArrayList while removing/addding elements.

  • Only done by normal for loop

  • by changing the size

/* Removes all even numbers */

public static ArrayList<Integer> removeEvens(ArrayList<Integer> list) { 
   for (int i = 0; i<list.size(); i++) { 
      if (list.get(i) % 2 == 0) { 
         list.remove(i);
         i--;
      }
   }
}
// Duplicates all odd numbers
public static ArrayList<Integer> duplicateOdds(ArrayList<Integer> list) {
   for (int i = 0; i<list.size(); i++) { 
      if (list.get(i) % 2 == 1) { 
         list.add(i);
         i++;
      }
   }
}

Algorithms

  • Modifying Array Values

// Doubles all elements

public static ArrayList<Integer> doubleElements(ArrayList<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        int temp = list.get(i);
        list.set(i, 2 * temp);
    }
    return list;
}

Searching

Search: to see if an element is actually in an ArrayList and to return its index if it is.

Linear/Sequential Search:

  • Go through the arraylist until finds the number.

  • Cannot find => return -1.

  • Find => return index.

public static int linearSearch(ArrayList<Integer> array, int n) {
   for (int i = 0; i < list.size(); i++) { 
      if (list.get(i) == n) { 
         return i;
      }
   }
   return -1;
}

Sorting

// Return true if the ArrayList is sorted in ascending order

public static boolean isSorted(ArrayList<Integer> array) {
   for (int i = 0; i<array.size() -1; i=+) { 
      if (array.get(i+1) < array.get(i)) { 
         return false;
      }
   }
   return true;
}

Selection Sort: Keep moving the smallest value to the front to make ascending order.

public static void selectionSort(ArrayList<Integer> list) {
    int minIndex, temp;

    for (int i = 0; i < list.size() - 1; i++) {
      minIndex = i; // Assume the first element is the minimum

      for (int j = i + 1; j < list.size(); j++) {
        if (list.get(j) < list.get(minIndex)) {
          minIndex = j; // Update minimum index if a smaller element is found
        }
      }

      // Swap the minimum element with the current position (i)
      if (minIndex != i) {
        temp = list.get(i);
        list.set(i, list.get(minIndex));
        list.set(minIndex, temp);
      }
    }
  }
}

Insertion Sort: Keep comparing initial value and the next value to sort

public static void insertionSort(ArrayList<Integer> list) {
    for (int i = 1; i < list.size(); i++) {
      int key = list.get(i); // Element to be inserted
      int j = i - 1;

      // Shift elements in the sorted sub-list to make space for the key
      while (j >= 0 && list.get(j) > key) {
        list.set(j + 1, list.get(j));
        j--;
      }

      // Insert the key at its correct position
      list.set(j + 1, key);
    }
  }
}