Section 2

Section 2

Introduction to Java Collections Framework

Table of Contents

  1. Topic 1: Overview of Java Collections Framework - JCF

  2. Topic 2: Overview of Iterator<E>

  3. Topic 3: Overview of Collection<E> Interfaces

  4. Topic 4 : Overview of List Interface

  5. Topic 5: Overview of ArrayList<E> class

    • Topic 5a: ArrayList<E> Constructors

    • Topic 5b: Common ArrayList<E> Methods

      • Example: Arraylist and its Methods

      • Example: Java List Initialization in One Line

    • Topic 5c: Iterating through ArrayList<E>

      • Example - Iterating through ArrayList

      • Example: A GenericBox using Arraylist

      • Hands-On Lab - ArrayList

    • Topic 5d: Sorting an ArrayList

  6. Topic 6: Queues Interface Overview

  7. Topic 7: Overview of LinkedList<E> class

    • Topic 7a: LinkedList<E> in JCF

    • Topic 7b: Declare and initialize Linkedlist<E>

    • Topic 7c: LinkedList<E> - Constructors

    • Topic 7d: LinkedList<E> Common Methods

      • Example: LinkedList Declaration and initialization

      • Example - Iterating through LinkedList

    • Topic 7e: LinkedList<E> Applications and Use Cases

    • Topic 7f: LinkedList<E> Performance

Topic 1: Overview of Java Collections Framework

  • A framework in Java:

    • Provides ready-made architecture.

    • Represents a set of classes and interfaces.

  • The Java Collection framework represents a unified architecture for storing and manipulating a group of objects. It has interfaces and its implementations (e.g., classes) and algorithms.

  • Java Collection framework provides many interfaces (Set, List, Queue, and Deque) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, and TreeSet).

    • These classes implement the interfaces using a variety of data structures, including algorithms for using those data structures.

Topic 2: Overview of Iterator<E> Interface

  • The super-interface Iterable<E> defines a mechanism to iterate (or traverse) through all of the elements of a Collection<E> object via a so-called Iterator<E> object.

  • The Iterable<E> interface declares one abstract method to retrieve the Iterator<E> object associated with the Collection<E>.

    • abstract Iterator<E> iterator();

  • The Iterator<E> interface declares the following abstract methods for traversing through the Collection<E>.

    • abstract boolean hasNext() // Returns true if it has more elements

    • abstract E next() // Returns the next element (of the actual type)

Topic 3: Overview of Collection<E> Interfaces

  • The JCF defines several interfaces, which extend Collection:

    • List: A List is an ordered collection of elements, which may contain duplicates. It is an interface that extends the Collection interface.

    • Set: a Set contains NO duplicate elements:

      • SortedSet extends set and adds the requirement that elements are ordered.

      • NavigableSet extends set and adds operations for fuzzy comparisons.

    • Queue: Queue is designed to hold elements for future processing:

      • Queues are first-in-first-out (FIFO).

      • Some Java queues are last-in-first-out (LIFO), although these are more properly called Stacks.

      • Deque is a double-ended queue that supports insertion/removal at both ends.

  • There are additional sub-interfaces that support concurrent access to collections, as shown in the previous slide.

Topic 4: Overview of List Interface

  • In Java, the List Interface is an ordered collection that allows us to store and access elements sequentially. Since List is an interface, we cannot create objects from it.

  • In order to use functionalities of the List interface, we can use the following classes that implement List Interface:

    • ArrayList, Linked List, Vector, and Stack

Topic 5: Overview of ArrayList<E> Class

  • The java.util.ArrayList<E> class is the most commonly used implementation of List<E>.

  • The <E> type parameter indicates that the interfaces are generic in design. When you construct an instance of these generic types, you need to provide the specific data type of the objects contained in these collection, e.g., <String>, <Integer>.

  • When you actually declare and initialize an ArrayList<E>, you should specify data type for type parameter.

  • ArrayList<E> implements a dynamic array.

  • ArrayList<E> implements Collection<E>.

  • Collection<E> extends Iterable<E>.

  • ArrayList class is a RESIZABLE Array, and elements can be added and removed from an ArrayList whenever you want.

  • Allows duplicate values and null.

  • ArrayList<E> implements additional interfaces:

    • Serializable.

    • Cloneable.

    • RandomAccess.

Topic 5a: ArrayList<E> Constructors

  • ArrayList<E> has three constructors:

    • Default Constructor: ArrayList<E>().

      • Create an ArrayList with default capacity (which is 10).

    • Capacity Constructor: ArrayList<E>(initialCapacity).

      • Use this constructor when you know the target size.

      • It can greatly improve performance by avoiding multiple re-allocations of the underlying array.

    • Populating Constructor: ArrayList<E>(Collection<? extends E> values).

      • This constructor pre-populates the list with a collection of E (or any subclass of E).

Topic 5b: Common ArrayList<E> Methods

  • clear()

    • Removes all of the elements from an Arraylist and does not return any value.

  • size()

    • Returns the length of the Arraylist.

  • get(int index)

    • Returns the value at the given index.

  • set(int index, E value)

    • Sets the value at the given index.

  • isEmpty()

    • Checks if the Arraylist is empty.

  • sort()

    • Sort the Arraylist elements.

  • add(E e)

    • Add a single element to the list.

  • indexOf()

    • Find the index of an element.

    • Returns -1 if not found.

  • contains()

    • Test if the list contains a value.

  • remove(E e)

    • Removes the element.

    • Return true if successful.

  • remove(int index)

    • Remove the element at the given index.

    • Returns the removed element.

Example: Arraylist and its Methods

In this example, we will demonstrate how to use Arraylist and Arraylist methods. Create a class named ArraylistExample, and write the code below:

import java.util.ArrayList;
public class ArraylistExample {
   public static void main(String[] args) {
       ArrayList<String> Mylist = new ArrayList<String>();
       Mylist.add("New Jersey");
       Mylist.add("Dallas");
       Mylist.add("New York");
       Mylist.add("Chicago");
       Mylist.add("LA");
       System.out.println("Return boolean :" + Mylist.contains("Chicago"));
       System.out.println("Return index value of Element :" + Mylist.indexOf("Chicago"));
       System.out.println("Returns the actual Element at the given index :" + Mylist.get(2));
       System.out.println("Returns the length of the arraylist :" + Mylist.size());
       // Remove the element at the given index.   Returns the removed element.
       // remove element at index 3
       String removedElement =  Mylist.remove(3);
       System.out.println("Removed Element: " + removedElement);
       // remove all elements
       Mylist.clear();
       System.out.println("ArrayList after clear(): " + Mylist);
   }
}

Example: Java List Initialization in One Line

  • Arrays class provides shortcut for initializing an elements to list. We can use the Arrays.asList() method to work around the array initialization limitation in List and give our List a set of default values.

  • We have to import java.util.Arrays package on top of the class.

public class ArraylistExample {
   public static void main(String[] args) {
      /* Declare and initialize the List. */
      List<String> listObj =   Arrays.asList("Java", "Python", "JavaScript", "ReactJs");
      System.out.println(listObj);
      /* Declare and initialize the ArrayList. */
      ArrayList<Integer> intList =  new ArrayList<Integer>(Arrays.asList(10,20,30,40,50));
      System.out.println(intList);
   }
}

Topic 5c: Iterating Through ArrayList<E>

  • There are several ways to loop through ArrayList:

    • Regular for loops and while loops with ArrayList<E>.

    • Enhanced for Loop.

    • Iterator<E>.

      • ArrayList<E> implements Collection<E>, which extends Iterable<E>

      • ArrayList<E> in enhanced for loops.

      • Import java.util.Iterator package.

    • forEachRemaining.

    • Java ListIterator interface.

      • We have to import java.util.ListIterator package.

    • Java Stream forEach().

Example - Iterating Through ArrayList

Example: Iterating Using Iterator Interface

import java.util.*;
public class ArrayListExample{
public static void main(String args[]){
     ArrayList<String> al=new ArrayList();
     al.add("Jack");  al.add("Tyler");
     al.add("James");
     Iterator itr=al.iterator();
     while(itr.hasNext()){
        System.out.println(itr.next());
     }
} }

Example: Iterating Using Enhanced for Loop

import java.util.*;
public class ArrayListExample{
public static void main(String args[]){
     ArrayList<String> al=new ArrayList();
     al.add("Jack");
     al.add("Tyler");
     al.add("James");
     // Enhanced for each loop
     for (String st:  al) {
        System.out.println(st);
} }
}

Example: A GenericBox Using Arraylist

In this example, we will create GenericBox by using Generic and Arraylist. By this example, you will understand how we can utilize generic and Collection together. Step 1: Create Generic class named Box<>, write below code.

import java.util.*;
public class Box <T> {
   List<T> values;
   public Box() {
       values = new ArrayList<T>();
   }
   public void add(T value){
           values.add(value);
   }
   public List<T> get () {
       return values;
   }
}

Step 2: Create class named myMain, write below code.

public class myMain {
public static void main(String[] args) {
// creating  Generic Instance for box
Box<Integer> intBox = new Box<Integer>();
       intBox.add(12);
       intBox.add(24);
       intBox.add(42);
       intBox.add(45);
       System.out.println(intBox.get());
// creating  Generic Instance for box
       Box<Float> floatBox = new Box<Float>();
       floatBox.add(12.3f);
       floatBox.add(18.5f);
       floatBox.add(120.45f);
       floatBox.add(85.4f);
       System.out.println(floatBox.get());
} }

Hands-On Lab - ArrayList

Complete the lab GLAB - 303.11.2 - ArrayList and ArrayList methods. You can find this lab on Canvas under the Assignment section. If you have any technical questions while performing the lab activity, ask your instructors for assistance.

Topic 5d: Sorting an ArrayList

  • We have two common approaches for sorting an ArrayList:

    • Use Collections class.

      • Collections is a special class and Collection(JCF) is super parent interface. Do not mix both of them. Click here for more details.

      • The Collections class provides two methods to sort an ArrayList in Java:

        • sort().

        • reverseOrder().

    • Use the ArrayList.sort() method.

      • The ArrayList also provides sort() method that is one more way to sort the List. You must pass a Comparator to the ArrayList.sort() method.

Sort an ArrayList Using Collections.sort() Method

Example:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ArrayListCollectionsSortExample {
 public static void main(String[] args) {
 ArrayList<Integer> numbers = new ArrayList<>();
 numbers.add(13);
 numbers.add(7);
 numbers.add(18);
 numbers.add(5);
numbers.add(2);
 System.out.println("Before : " + numbers);
         // Sorting an ArrayList using Collections.sort() method
 Collections.sort(numbers);
 System.out.println("After : " + numbers);
 }
}

Output:

Before : [13, 7, 18, 5, 2]
After : [2, 5, 7, 13, 18]

Sort an ArrayList Using Arraylist.sort() and Comparator

Example:

import java.util.ArrayList;
import java.util.Comparator;
public class myMain {
  public static void main(String[] args) {
    // create an ArrayList
    ArrayList<String> languages = new ArrayList<>();
    // add elements to ArrayList
    languages.add("Python");
    languages.add("Swift");
    languages.add("C");
    languages.add("JavaScript");
    System.out.println("Unsorted ArrayList: " + languages);
    // sort the ArrayList in ascending order
    languages.sort(Comparator.reverseOrder());
    System.out.println("Sorted ArrayList: " + languages);
    }
}

Languages is a Object of Arraylist in this example. Output:

Unsorted ArrayList: [Python, Swift, C, JavaScript]
Sorted ArrayList: [Swift, Python, JavaScript, C]

Topic 5e: ArrayList<E> of User-Defined Objects

Since ArrayList supports generics, you can create an ArrayList of any data type. It can be of simple types like Integer, String, or Double, or complex types like an ArrayList of ArrayLists, an ArrayList of HashMaps, or an ArrayList of user-defined objects, such as:

  • We could have an ArrayList of String objects → ArrayList<String>.

  • We could have an ArrayList of Book objects, → ArrayList<Book>.

  • We could have an ArrayList of Employee objects → ArrayList<Employee>.

  • We could have an ArrayList of Student objects → ArrayList<Student >.

  • We could have an ArrayList of Shape objects → ArrayList<Shape>.

Remember that the specified data type must be a class.

String is a Class, so the following statement is legal and true because the specified data type must be a class or non-primitive data type.

Find the lab GLAB - 303.11.3 - ArrayList of User-Defined Objects on Canvas under the Assignment section for the demonstration.

Practice Assignment:

This following practice assignments will be administered through HackerRank. Click on the below links:

  • Java Arraylist

  • Java Iterator

Note: This is not a mandatory assignment. Use your office hours to complete this assignment. If you have any technical questions while performing this lab activity, ask the instructors for assistance.

Topic 6: Queues<E> Interface Overview

  • Queues are like a line at the supermarket. If you are first in line, you expect to be first out of the line.

  • This behavior is called FIFO – First-In First-Out

  • The Queue Interface defines methods:

    • Add – insert an element into the queue.

    • Remove – remove an element from the queue.

    • Peek – retrieve (but do not remove) the first element in the queue.

  • Queues are often used to store objects for future processing.

  • A versatile implementation of this interface is ArrayDeque<T>.

  • Since the Queue is an Interface, we cannot provide the direct implementation of it because we cannot create objects from it. In order to use functionalities of the Queue interface, we can use these classes: ArrayDeque, PriorityQueue, LinkedList.

Topic 7: Overview of LinkedList<E> Class

  • A LinkedList is a data structure with nodes chained together via links.

  • In a LinkedList, each node contains — besides the next-node link — a second link field pointing to the 'previous' node in the sequence. The two links may be called “forwards” and “backwards,” or “next” and “prev” (previous).

  • LinkedLists may be either singularly-linked list or doubly-linked list. The doubly-link list offers more capabilities because it can be traversed in either direction.

For more information about LinkedLists, visit Wiki document

Topic 7a: LinkedList<E> in JCF

In JCF, LinkedList class is a doubly-linked list.

  • LinkedList<E> class implements both List<E> and Queue<E> interfaces.

LinkedList implements these interfaces:

  • List<E>

    • Collection<E>

    • Iterable<E>

  • Deque<E>

    • Queue<E>

  • Clonable

  • Serializable

Topic 7b: Declare and Initialize Linkedlist<E>

When you actually declare and initialize a Linkedlist<E>, you should specify data type for type parameter:

  • LinkedList<String> ListObj1 = new LinkedList<String>();

  • LinkedList<Integer> ListObj2 = new LinkedList<Integer>();

  • LinkedList<Float> ListObj2 = new LinkedList<Float>();

  • LinkedList<UserDefineObject> ListObj2 = new LinkedList<UserDefineObject>();

In order to create a Linkedlist<E>, we must import the java.util.LinkedList package on top of the class.

Topic 7c: LinkedList<E> - Constructors

LinkedList<E> has two Constructors:

  • LinkedList<Integer> listobj = new LinkedList<Integer>();

    • This creates an empty linked list.

  • LinkedList<Integer> listobj = new LinkedList<Integer>(c);

    • c is a Collection of Integer.

    • This constructor creates a linked list containing all elements of c.

    • The links are ordered in the same order returned by the collection’s iterator – the same order we would observe in an enhanced for loop (a foreach loop).

Topic 7d: LinkedList<E> Common Methods

Here are a few of the LinkedList Methods:

  • add(E e): Appends an element to the end of the list.

  • add(int index, E e): Inserts an element at the specified index.

  • get(int index): Returns the element at the specified index.

  • set(int index, E e): Replace/override the element at the given index with e.

  • indexOf(Object o): Returns the index of the specified element, or return -1 if the element is not found.

  • remove(int index): Removes and returns the element at the given index.

  • Object[] toArray(): Returns an array containing all of the elements in this list in proper sequence.

  • size(): Returns the number of elements in the list.

  • addFirst(Object o): Inserts the given element at the beginning of a list.

  • addLast(Object o): Appends the given element to the end of a list.

  • lastIndexOf(Object o): Returns the index in a list of the last occurrence of the specified element, or -1 if the list does not contain specified element.

Example: LinkedList<E> Declaration and Initialization

public class LinkedListExample {
   public static void main(String[] args) {
       //Create linked list
       LinkedList<String> linkObj = new LinkedList<String>();
       //Adding elements
       linkObj.add("A");
       linkObj.add("B");
       linkObj.add("C");
       linkObj.add("D");
       System.out.println(linkObj);
       //Add elements at specified position
       linkObj.add(4, "A");
       linkObj.add(5, "A");
       System.out.println(linkObj);
       //Adding an element to the first position
       linkObj.addFirst("AddedOnFirst");
       //Adding an element to the last position
       linkObj.addLast("Lastadded");
       System.out.println(linkObj);
       System.out.println("ELement on Index 4: "+  linkObj.get(4));
       // set() method for overide or replace any element
       linkObj.set(2, "B is relace by BBBBB");
       System.out.println(linkObj);
       //Remove element
       linkObj.remove(0);   //removes AddedOnFirst
       System.out.println(linkObj);
       linkObj.remove("A");   //removes A
       System.out.println(linkObj);
   }
}

In this example, we will demonstrate, how to declare a Linkedlist, how to initialize elements in a LinkedList by using built-in methods, how to get elements, and how to remove elements from LinkedList.

Output:

[A, B, C, D]
[A, B, C, D, A, A]
[AddedOnFirst, A, B, C, D, A, A, Lastadded]
ELement on Index 4: D
[AddedOnFirst, A, B is relace by BBBBB, C, D, A, A, Lastadded]
[A, B is relace by BBBBB, C, D, A, A, Lastadded]
[B is relace by BBBBB, C, D, A, A, Lastadded]

Example: Iterating Through LinkedList<E>

Example: Iterating using Iterator interface

public class LinkedListiterator {
   public static void main(String[] args) {
       LinkedList<String> l = new LinkedList<String>();
       l.add("John");
       l.add("Sara");
       l.add("Susan");
       l.add("Betty");
       l.add("Nathan");
       System.out.println("The LinkedList elements are: ");
       Iterator itr = l.iterator();
       while(itr.hasNext()){
           System.out.println(itr.next());
       }
   }
}

Example: Iterating using Enhanced for loop

public class LinkedListLoop {
   public static void main(String[] args) {
       LinkedList<String> l = new LinkedList<String>();
       l.add("John");
       l.add("Sara");
       l.add("Susan");
       l.add("Betty");
       l.add("Nathan");
       System.out.println("The LinkedList elements are: ");
       // Enhanced for each loop
       for (String st:  l) {
           System.out.println(st);
       }
   }
}

An Iterator can be used to loop through a LinkedList. The method hasNext()returns true if there are more elements in LinkedList and false otherwise. The method next() returns the next element in the LinkedList and throws the exception NoSuchElementException if there is no next element.

Topic 7e: LinkedList<E> Applications and Use Cases

LinkedLists are a natural choice for applications, and involve previous/next behavior:

  • Browser navigation.

  • Music players.

  • Image carousel. Some operating systems utilize LinkedLists for free-memory management. Some hash table implementations use LinkedLists for collision resolution.

Topic 7f: LinkedList<E> Performance

  • LinkedLists are optimized for Insertion/Removal.

  • Accessing elements by index is O(N).

  • Inserting/removing the head or tail element is O(1).

    • Ideal for implementing Stack and Queue.

  • Inserting/removing from other positions is O(N), but avoids the shifting that occurs with ArrayList.

  • indexOf (searching) is O(N).

  • LinkedLists can grow/shrink dynamically without a need for reallocation.

  • LinkedLists have memory overhead due to the Nodes.

Hands-On Lab - LinkedList

Complete the GLAB - 303.11.4 - LinkedList Processing. You can find this lab on Canvas under the Assignment section. If you have any technical questions while performing the lab activity, ask your instructors for assistance.

ArrayList vs. LinkedList

Let’s list a few notable differences between Arraylist and LinkedList.

  • An ArrayList is implemented with the concept of dynamic resizable array, while LinkedList is a doubly linked list implementation.

  • An ArrayList allows random access to its elements, while LinkedList does not.

  • A LinkedList implements a Queue interface, which adds more methods than an ArrayList, such as offer(), peek(), poll(), etc.

  • An ArrayList is slower than a LinkedList in add and remove, but faster in get because there is no need to resize array and copy content to new array if the array gets full in LinkedList.

  • LinkedLists have more memory overhead than ArrayList because in ArrayList, each index only holds actual objects, but in the case of LinkedLists, each node holds both data and addresses of the next and previous nodes.

Knowledge Check

  • Describe the Java Collections Interface.

  • How can you loop over ArrayList in Java?

  • When do you use ArrayList and LinkedList in Java?

PreviousSection 1NextSection 3

Last updated