Section 2
Section 2
Introduction to Java Collections Framework
Table of Contents
Topic 1: Overview of Java Collections Framework - JCF
Topic 2: Overview of Iterator<E>
Topic 3: Overview of Collection<E> Interfaces
Topic 4 : Overview of List Interface
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
Topic 6: Queues Interface Overview
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 elementsabstract 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:
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.
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
Example: Iterating Using Enhanced for Loop
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.
Step 2: Create class named myMain, write below code.
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:
Output:
Sort an ArrayList Using Arraylist.sort() and Comparator
Example:
Languages is a Object of Arraylist in this example. Output:
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
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:
Example: Iterating Through LinkedList<E>
Example: Iterating using Iterator interface
Example: Iterating using Enhanced for loop
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?
Last updated