UNIT 10: COLLECTIONS IN JAVA
Key unit competency
To be able to use collections to store data in Java
Introductory Activity
the following scenario:
Urumuri Primary School in Gakenke District is a School with Administrators, Teachers and Students (Boys and Girls). The number of students changes every year. At lunch time, every student is called to have lunch and finally realizes that the served food is not the same for all.
1. Discus on how the new comers will be assigned to classrooms and the outgoing students will be removed from the lists of students.
2. Suggest how the students will be called to get their lunch boxes
3. Show how the Stack theory can be implemented in the above Scenario.
4. Draw and explain the school organization structure.
10.1. INTRODUCTION TO THE COLLECTION FRAMEWORK
Learning Activity 10.1
.Discuss on the following java terms:
•A collection
•Java collection
•Framework
•Framework in Java
•Java collection Framework(JCF)
In Java, dynamically allocated data structures (such as ArrayList, LinkedList, Vector, Stack, HashSet, HashMap, Hashtable) are supported in a unified architecture called “Collection”, a framework which mandates the common behaviors of all the classes. The collection framework provides a unified interface to store, retrieve and manip-ulate the elements of a collection, regardless of the underlying and actual implementation. This allows the programmers to program at the interfaces, instead of the actual implementation.
10.1.1. A collection
A collection is a data structure which contains and processes a set of data. The data stored in the collection is encapsulated and the access to the data is only possible via predefined methods.
10.1.2. Collections in javaJava
Collection simply means a single unit of objects. It is a framework that provides an architecture to store and manipulate the group of objects. All the operations per-formed on data such as searching, sorting, insertion, manipulation, deletion, etc. can be performed by Java Collections.
10.1.3. Framework
Frameworks are large bodies of prewritten code to which new code is added to solve a problem in a specific domain.
A framework, or software framework, is a platform for developing software applica-tions. It provides a foundation on which software developers can build programs for a specific platform. For example, a framework may include predefined classes and functions that can be used to process input, manage hardware devices, and inter-act with system software. This streamlines the development process since program-mers don’t need to reinvent the wheel each time they develop a new application.
10.1.4. Framework in java:
It provides a ready-made architecture and represents a set of classes and interface.
10.1.5. Java Collection framework (JFC):
The Java Collection Framework (JCF) is a collection of interfaces and classes in the packages java.util and java.concurrent which helps in storing and processing the data efficiently or a set of classes and interfaces that implement commonly reusable collection data structures and represents a single unit of objects. JFC provides both interfaces that define various collections and classes that implement them. Inter-faces (Set, List, Queue, Map, etc.) and classes (ArrayList, Vector, LinkedList, Priority-Queue, Harshest, LinkedHashSet, TreeSet, etc.) work in a manner of a library.
10.1.6. Structure of Java Collections Framework
Below is the diagram picturing the different collection classes and interface.
Application Activity 10.1.
1. Explain the following: Collection and Collections Framework.
2. What are the benefits of Java Collections Framework?
3. What are the basic interfaces of Java Collections Framework?
4. List at least 2 practices related to Java Collections Framework.
5. What is the use of Java Collections Framework?
10.2 Java - The collection interfaces and Classes
An interface is a contract (or a protocol, or a common understanding) of what the classes can do. When a class implements a certain interface, it promises to provide implementation to all the abstract methods declared in the interface. Interface defines a set of common behaviors. The classes implement the interface, agree to these behaviors and provide their own implementation to the behaviors. This allows to program at the interface, instead of the actual implementation.
10.2.1Java Collections – List interface
Learning Activity 10.2.
We want to develop an application called Travel in which will display the travels
from the traveling agency companies Alpha Ltd and Beta Ltd and place an order
from customers.
Answer the following questions:
1. How should we design our application by considering the list
interfaces?
2. What are the methods that will be used by/ the application to keep the
travels for every company?
3. Display the travels available from vendors like "Alpha" and "Beta".
A List is an ordered Collection (sometimes called a sequence) of elements. The Lists
may contain duplicate elements. The elements can be inserted or accessed by their
position in the list, using a zero-based index. The java.util.List interface is a subtype
of the java.util.Collection interface. It represents an ordered list of objects, meaning
that the elements of a List can be accessed in a specific order, and by an index too.
The same element can be added more than once to a List.
The Java platform contains two general-purpose List implementations. ArrayList
which is usually the better-performing implementation, and LinkedList which offers better performance under certain circumstances.
Here are examples of how to create a List instance:
• List listA = new ArrayList
;
• List listB = new LinkedList
10.2.1.1 Java ArrayList class
a. Understanding the ArrayList Class
The ArrayList class extends AbstractList and implements the List interface. The ArrayList supports dynamic arrays that can grow as needed and it contains duplicate
elements. The Array lists are created with an initial size. When this size is exceeded,
the collection is automatically enlarged. When objects are removed, the array may
be shrunk. The Java ArrayList class uses a dynamic array for storing the elements.
An array averts many of the most common problems of working with arrays, specifically the following:
• An array list automatically resizes itself whenever necessary;
• An array list allows to insert elements into the middle of the collection
• An array list lets the items to be deleted. When an item is deleted from
an array list, any subsequent items in the array are automatically moved
forward one position to fill the spot that was occupied by the deleted item.
• The ArrayList class uses an array internally to store the data added to the
array list: When an item is added to the array list, and the underlying array
is full, the ArrayList class automatically creates a new array with a larger
capacity and copies the existing items to the new array before it adds the
new item.
b. ArrayList has three constructors:
d. Creating, declaring an ArrayList Object
To create an array list, an ArrayList variable is firstly declared and the ArrayList constructor is called to instantiate an ArrayList object and assign it to the variable.
ArrayList signs = new ArrayList();
Here are a few things to note about creating array lists:
• The ArrayList class is in the java.util package, so the program must import
either java.util.ArrayList or java.util.*.
• Unlike an array, an array list doesn’t make the user specify a capacity even
if it is possible.
Example that creates an array list with an initial capacity of 100:
ArrayList signs = new ArrayList(100);
e. Adding Elements
After an array list is created, the add method to add objects to the array list is the
used. An array lists is indexed starting with zero and when it is already at its capacity
when an element is added, the array list automatically expands its capacity.
Example: signs.add(“Peter”);
If a type when is specified during the creationof the array list, the added objects via
the add method must be of the correct type. An object can be inserted at a specific
position in the list by listing the position in the add method.
Syntax: ArrayList<String>nums = new ArrayList<String>();
f. Accessing Elements
To access a specific element in an array list, the get method can be used, which specifies the index value of the element to be retrieved. Here’s a for loop that prints all
the strings in an array list:
for (inti = 0; i<nums.size(); i++)
System.out.println(nums.get(i));
Here the size method is used to set the limit of the for loop’s index variable. The
easiest way to access all the elements in an array list is to use an enhanced “for”
statement, which allows to retrieve the elements without bothering with indexes or
the get method.
For example:
For (String s: nums)
System.out.println(s);
To know the index number of a particular object in an array list a reference to the
object is known, the indexOf method is used.
g. Printing an ArrayList
Arrays are usually useful when working with arbitrarily large number of data having
the same type. It is usually convenient if we can print the contents of an array.
• Print Array In Java Using Default toString()
The toString method of the ArrayList class (as well as other collection classes) is
designed to make it easy to quickly print out the contents of the list. It returns the
contents of the array list enclosed in a set of brackets, with each element value
separated by commas. The toString method of each element is called to obtain the
element value.
Below is a Simple Program That Prints An Array In Java using Arrays.toString().
The following is generalArrayList Example in Java
package arraylist1;
importjava.util.*;
public class ArrayList1 {
public static void main(String[] args) {
/*Creation of ArrayList: I’m going to add String elements so I made it of string type */
ArrayList<String>obj = new ArrayList<String>();
/*This is how elements should be added to the array list*/
obj.add(“Peter”);
obj.add(“TOM”);
obj.add(“Jim”);
obj.add(“Alice”);
obj.add(“Sam”);
/* Displaying or Printing an array list element */
System.out.println(“Currently the array list has following elements:”+obj);
/*Add element at the given index*/
obj.add(0, “Kayiranga”);
obj.add(1, “Damas”);
/*Remove elements from array list like this*/
obj.remove(“Peter”);
obj.remove(“Tom”);
System.out.println(“Current array list is:”+obj);
/*Remove element from the given index*/
obj.remove(1);
System.out.println(“Current array list is:”+obj);
}
}
Output:
10.2.1.2. Java - LinkedList class
The Linked list implementation of the List interface implements all optional List
operations and permits all elements (including null). In addition to implementing
the List interface, LinkedList provides uniformly named methods to get, remove
and insert an element at the beginning and end of the List. These operations allow
LinkedList to be used as a stack, queue, or double-ended queue (deque). It provides
a linked-list data structure and inherits the AbstractList class.
a. Creating, declaring a LinkedList
As with any other kind of object, creating a linked list is a two-step affair. First, declare a LinkedList variable; then call one of the LinkedList constructors to create the
object, as in this example:
LinkedList officers = new LinkedList
to the variable officers.
Here’s a statement that creates a linked list that holds strings:
LinkedList<String> officers = new LinkedList<String> ();
Then add only String objects to this list.
b. Adding Items to a LinkedList
The LinkedList class gives many ways to add items to the list. The most basic is the
add method, which works pretty much the same way that it does for the ArrayList
class.
Here’s an example:
To insert an object into a specific position into the list, specify the index in the add
method, as in this example:
c. Retrieving Items from a LinkedList
Get method is used to retrieve an item based on its index. If an invalid index number
is passed to it, the get method throws the unchecked IndexOutOfBoundsException.
An enhanced “for” loop to retrieve all the items in the linked list can also be used. The
examples in the preceding section use this enhanced for loop to print the contents
of the officers linked list:
for (String s: officers)
System.out.println(s);
Some methods retrieve the first item in the list:
d. Updating LinkedList Items
As with the ArrayList class, the set method can be used to replace an object in a
linked list with another object.
e. Removing LinkedList Items
Several of the methods that retrieve items from a linked list and also remove the
items have been seen. The remove, removeFirst, and poll methods remove the first
item from the list, and the removeLast method removes the last item. Any arbitrary
item can be removed by specifying either its index number or a reference to the
object to be removed on the remove
method. To remove item 3, for example, use a statement like this:
officers.remove(3);
If a reference to the item to be removed is there, use the remove method, like this:
officers.remove(Jim);
To remove all the items from the list, use the clear method:
officers.clear
The following program illustrates several of the methods supported by LinkedList
and support above collection method:
f. Java LinkedList Example: Book
import java.util.*;
class Book {
int id;
String book_title,author,publisher;
int quantity;
public Book(int id, String book_title, String author, String publisher, int quantity) {
this.id = id;
this.book_title = book_title;
this.author = author;
this.publisher = publisher;
this.quantity = quantity;
}
}
public class LinkedListExample {
public static void main(String[] args) {
//Creating list of Books
List<Book> list=new LinkedList<Book>
//Creating Books
Book b1=new Book(101,”Introduction to Java”,”Martin”,10);
Book b2=new Book(102,”Data Communications & Networking”,”James”,”Alph”4);
Book b3=new Book(103,”Operating System”,”John”,”Samuel”,6);
//Adding Books to list
list.add(b1);
list.add(b2);
list.add(b3);
//Traversing list
for(Book b:list){
System.out.println(b.id+” “+b. book_title +” “+b.author+” “+b.publisher+” “+b.quantity);
} } }
10.2.1.3 Java - vector class
Vectors (the java.util.Vector class) are commonly used instead of arrays, because
they expand automatically when new data is added to them. If a primitive type in a
Vector is to be put, put it inside an object (eg, to save an integer value use the Integer class or define your own class).
The java.util. Vector class implements a dynamic array of objects. Similar to an Array,
it contains components that can be accessed using an integer index. The size of a
Vector can grow or shrink as needed to accommodate adding and removing items.
Vector is synchronized. This means that if one thread is working on Vector, no other
thread can get a hold of it. Unlike ArrayList, only one thread can perform an operation on vector at a time.
Class declaration for java.util.Vector class
a. Class constructors
There exist Vector class methods which are used in Java collections. Here is an example of how these methods are used:
Example that can support some of the above said method:
Application Activity 10.2.
1. Discuss when to use ArrayList andLinkedList in Java?
2. Write a program that do the following:
• Create linkedList from linked list with assigned to the variable district.
• Add the following district in the List (Gakenke, Rubavu, Gasabo, Nyagatare,
Nyabihu )
• Add Bugesera District to the front of list and Karongi to the4th position
• Replace Gasabo District with Nyarugenge
• Retrieving the Second District using Index
• Show the Size and Remove the last district in the List
Note: After every operation display output
3. What are similarities and difference between ArrayList and Vector?
10.2.2. Java Collections – Set interface and implementations
Learning Activity 10.3.
Study the following part of Java Program and answer the following?
Set setA = new HashSet ();
String element = "element 1";
setA.add(element);
System.out.println(setA.contains(element));
1. Outline the method used in the above program?
2. What is HashSet in the above program?
3. List and explain Set implementations using by Internet or books help
Basically, a Set is a type of collection that does not allow duplicate elements. That
means an element can only exist once in a Set. It models the set abstraction in
mathematics. A Set is an unordered collection of objects.
1. Java - HashSet class
This class implements the Set interface backed by a hash table, It creates a collection that uses a hash table for storage. A hash table stores information by using a
mechanism called hashing. In hashing, the informational content of a key is used to
determine a unique value, called its hash code.
The following table lists the constructors associated with Java HashSet:
Java HashSet Example: Book
This is a HashSet example where we are adding books to set and printing all the
books.
import java.util.*;
class Book {
int id;
String book_title,author,publisher;
int quantity;
public Book(int id, String book_title, String author, String publisher, int quantity) {
this.id = id;
this.book_title = book_title;
this.author = author; // The body of class constructor
this.publisher = publisher;
this.quantity = quantity;
} }
public class HashSetExample {
public static void main(String[ ] args) {
HashSet<Book> set=new HashSet<Book>();
//Creating Books
Book b1=new Book(101,”Introduction to Java”,”Martin”,10);
Book b2=new Book(102,”Data Communications & Networking”,”James”,”Alph”4);
Book b3=new Book(103,”Operating System”,”John”,”Samuel”,6);
//Adding Books to HashSet
set.add(b1);
set.add(b2);
set.add(b3);
//Traversing HashSet
for(Book b:set){
System.out.println(b.id+” “+b.book_title+” “+b.author+” “+b.publisher+” “+b.quantity; } }
}
10.2.2.2. Java LinkedHashSet Class
Java LinkedHashSet class is a Hash table and Linked list implementation of the set
interface. It inherits HashSet class and implements Set interface.
The important points about Java LinkedHashSet class are:
• Contains unique elements only like HashSet.
• Provides all optional set operations, and permits null elements.
• Maintains insertion order.
LinkedHashSet class is declared like this:
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, serializable
LinkedHashSet<String>hs = new LinkedHashSet<String>();
Constructors of Java LinkedHashSet class
Unlike HashSet, LinkedHashSet builds a link-list over the hash table for better efficiency in insertion and deletion (in the expense of more complex structure). It maintains its elements in the insertion-order (i.e., order of add()).
Java LinkedHashSet Example: Book
import java.util.*;
class Book {
int id;
String book_title,author,publisher;
int quantity;
public Book(int id, String book_title, String author, String publisher, int quantity) {
this.id = id;
this.book_title = book_title;
this.author = author;
this.publisher = publisher;
this.quantity = quantity;
}
} public class LinkedHashSetExample {
public static void main(String[] args) {
LinkedHashSet<Book> hs=new LinkedHashSet<Book>();
//Creating Books
Book b1=new Book(101,”Introduction to Java”,”Martin”,10);
Book b2=new Book(102,”Data Communications & Networking”,”James”,”Alph”4);
Book b3=new Book(103,”Operating System”,”John”,”Samuel”,6);
//Adding Books to hash table
hs.add(b1);
hs.add(b2);
hs.add(b3);
//Traversing hash table
for(Book b:hs){
System.out.println(b.id+” “+b. book_title +” “+b.author+” “+b.publisher+” “+b.quantity);
} }
}
10.2.3. Java-class TreeSet class
The Java TreeSet class implements the Set interface that uses a tree for storage. It
inherits AbstractSet class and implements NavigableSet interface. The objects of
TreeSet class are stored in ascending order.
a. Constructors of Java TreeSet class
10.2.2.4. The difference between Set and List is:
• List is a collection class which extends AbstractList class whereas Set is a
collection class which extends AbstractSet class, but both implements
Collection interface.
• List interface allows duplicate values (elements) whereas Set interface does
not allow duplicate values which means that List can contain duplicate
elements whereas Set contains unique elements only
• Set is unordered while List is ordered. List maintains the order in which the
objects are added.
Application Activity 10.3.
1. What is the output of this program?
importjava.util.*;
class Output
{
public static void main(String args[])
{
HashSetobj = new HashSet();
obj.add("A");
obj.add("B");
obj.add("C");
System.out.println(obj + " " + obj.size());
}
}
2. What is the difference between a HashSet and a TreeSet?
10.2.3Java Collections – Map interface
Learning Activity 10.4.
Study the following part of Java Program and answer the following questions?
Map<Integer, String>mapmarks = new HashMap<>();
mapmarks.put(80, "tom");
mapmarks.put(75, "Alice");
mapmarks.put(65, "Antoine");
mapmarks.put(50, "peter");
System.out.println(mapmarks);
1. Outline the method used in the above program;
2. What is HashMap in the above program?
3. List and explain Map implementations by using Internet connection or
books.
4. Analyze the program and give the output.
A Map is a collection or an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. Maps are perfectly for key-value
association mapping such as dictionaries. Use Maps when there is a need to retrieve
and update elements by keys, or perform lookups by keys.
A Map is an object that maps keys to values or is a collection of attribute-value pairs.
It models the function abstraction in mathematics. The following picture illustrates
a map:
Note that a Map is not considered to be a true collection, as the Map interface does not extend the Collection interface.
a. Map implementation
The Java platform contains three general-purpose Map implementations: HashMap,
TreeMap, and LinkedHashMap. Their behavior and performance are precisely
analogous to HashSet, TreeSet, and LinkedHashSet, as described in The Set Interface
section. A Map cannot contain duplicate keys and each key can map to at most
one value. Some implementations allow null key and null value (HashMap and
LinkedHashMap) but some does not (TreeMap). The order of a map depends on
specific implementations, e.gTreeMap and LinkedHashMap have predictable order,
while HashMap does not.
10.2.3.1. Java - HashMap Class
This implementation uses a hash table as the underlying data structure. It implements
all of the Map operations and allows null values and one null key. This class is roughly
equivalent to Hashtable - a legacy data structure before Java Collections Framework,
but it is not synchronized and permits nulls. HashMap does not guarantee the order
of its key-value elements. Therefore, consider to use a HashMap when order does
not matter and nulls are acceptable.
Note: HashMap does not maintain any order neither based on key nor on basis of
value, If the keys is wanted to be maintained in a sorted order, TreeMap needs to be
used.
The HashMap class uses a hashtable to implement the Map interface. This allows the
execution time of basic operations, such as get
for large sets.
The following is the list of constructors supported by the HashMap class.
10.2.3.2. Java- LinkedHashMap
Java LinkedHashMap class is Hash table and Linked list implementation of the Map
interface, with predictable iteration order. It inherits HashMap class and implements
the Map interface.
The important points about Java LinkedHashMap class are:
• A LinkedHashMap contains values based on the key.
• It contains only unique elements.
• It may have one null key and multiple null values.
• It is same as HashMap instead maintains insertion order.
Java LinkedHashMap Example: Creating and traversing the book
importjava.util.*;
class Book {
int id;
String book_title,author,publisher;
int quantity;
public Book(int id, String book_title, String author, String publisher, int quantity) {
this.id = id;
this. book_title = book_title;
this.author = author;
this.publisher = publisher;
this.quantity = quantity;
}
}
public class MapExample {
public static void main(String[] args) {
//Creating map of Books
Map<Integer,Book> map=new LinkedHashMap<Integer,Book>();
//Creating Books
Book b1=new Book(101,”Let us C”,”Yashwant Kanetkar”,”BPB”,8);
Book b2=new Book(102,”Data Communications & Networking”,”Forouzan”,”Mc Graw Hill”,4);
Book b3=new Book(103,”Operating System”,”Galvin”,”Wiley”,6);
//Adding Books to map
map.put(2,b2);
map.put(1,b1);
map.put(3,b3);
//Traversing map
for(Map.Entry<Integer, Book>entry:map.entrySet()){
int key=entry.getKey();
Book b=entry.getValue();
System.out.println(key+” Details:”);
System.out.println(b.id+” “+b. book_title +” “+b.author+” “+b.publisher+” “+b.quantity);
} }
}
10.2.3.3. Java – TreeMap class
This implementation uses a red-black tree as the underlying data structure. A TreeMap is sorted according to the natural ordering of its keys, or by a Comparator provided at creation time. This implementation does not allow nulls. So consider using a
TreeMap when Map is wanted to sort its key-value pairs by the natural order of the
keys (e.g. alphabetic order
• Difference between Map and Set
The Map object has unique keys each containing some value, while Set contain only
unique values.
Application Activity 10.4.
1. Describe various implementations of the Map interface and their use
case differences.
2. How is HashMap implemented in Java? How does its implementation
use hashCode and equals methods of objects?
3. Write a program to do the following :
• create HashMap from copying data from another Map
• adding key and value in Java HashMap
• Retrieving value from HashMap
• Show the Size and Clear value in HashMap
• Sorting HashMap on keys and values entered using TreeMap.
10.2.4. Java collections – Queue interface
a. Definition
Queue means ‘waiting line’. A Queue is designed in such a way so that the elements
added to it are placed at the end of Queue and removed from the beginning of
Queue. In programming a Queue is a collection or data structure for holding
elements prior to processing like queues in real-life scenarios.
b. First In First Out or FIFO
Let’s consider that a queue holds a list of waiting customers in a bank’s counter. Each
customer is served one after another, by following their orders of arriving. The first
customer comes is served first, and after him is the 2nd, the 3rd, and so on. When
the customer is served, he or she leaves the counter (removed from the queue), and
the next customer is picked to be served next. Other customers who come later are
added to the end of the queue. This processing is called First In First Out or FIFO. The
FIFO principle is thatItems stored first are retrieved first.
c. Queue methods
The Queue interface defines some methods for acting on the first element of the
list, which differ in the way they behave, and the result they provide.
• peek()
In computer science, peek is an operation on certain abstract data types, specifically
sequential collections such as stacks and queues, which returns the value of the top
(“front”) of the collection without removing the element from the collection. It thus
returns the same value as operations such as “pop” or “dequeue”, but does not modify the data. If the list is empty, it returns null.
Key points:
peek ():
• Retrieves, but does not remove, the head of this queue, or returns null if
this queue is empty.
• Returns: the head of this queue, or null if this queue is empty
• element()
The element() method behaves like peek(), so it again retrieves the value of the first
element without removing it. Unlike peek(), however, if the list is empty element()
throws a NoSuchElementException
• poll()
The poll() method retrieves the value of the first element of the queue by removing
it from the queue . At each invocation it removes the first element of the list and if
the list is already empty it returns null but does not throw any exception.
• remove()
The remove() method behaves as the poll() method, so it removes the first element
of the list and if the list is empty it throws a NoSuchElementException
• boolean add():
This method adds the specified element at the end of Queue and returns true if
the element is added successfully or false if the element is not added that basically
happens when the Queue is at its max capacity and cannot take any more elements.
d. Queue Implementations
Queue interface in Java collections has two implementations: LinkedList and
Priority Queue.
• LinkedList is a standard queue implementation. Queue q1 = new LinkedList ();
• Priority Queue stores its elements internally according to their natural order.
PriorityQueue class is a priority queue based on the heap data structure. By
default, we know that Queue follows First-In-First-Out model but sometimes we
need to process the objects in the queue based on the priority. That is when Java
PriorityQueue is used. For example, let’s say we have an application that generates
stocks reports for daily trading session. This application processes a lot of data and
takes time to process it. So, customers are sending request to the application that
is actually getting queued, but we want to process premium customers first and
standard customers after them. So in this case PriorityQueue implementation in java
can be really helpful. Example of how to create a Queue instance:
Queue q2 = new PriorityQueue();
1. Adding and Accessing Elements
To add elements to a Queue you call its add() method. This method is inherited from
the Collection interface.
Here are examples:
Queue queueA = new LinkedList ();
queueA.add(“element 1”);
queueA.add(“element 2”);
The order in which the elements added to the Queue are stored internally, depends
on the implementation. The same is true for the order in which elements are retrieved from the queue. You can peek at the element at the head of the queue without taking the element out of the queue. This is done via the element() method.
Here is how that looks: Object firstElement = queueA.element();
2. Removing Elements
To remove elements from a queue, you call the remove() method. This method removes the element at the head of the queue. In most Queue implementations the
head and tail of the queue are at opposite ends. It is possible, however, to implement the Queue interface so that the head and tail of the queue is in the same end.
In that case you would have a stack.
Remove example: Object firstElement = queueA.remove();
3. Generic Queue
By default, any Object can be put into a Queue, Java Generics makes it possible to
limit the types of object you can insert into a Queue.
Example: Queue<MyObject> queue = new LinkedList<MyObject> ();
Another type of collection that allows to add objects to the end of the collection and
remove them from the top. Queues are commonly used in all sorts of applications,
from data processing applications to sophisticated networking systems. This queue
class is named GenQueue and has the following methods:
• enqueue: This method adds an object to the end of the queue. (insertion
of element in Queue)
• dequeue: This method retrieves the first item from the queue. The item is
removed from the queue in the process. (Deletion of element in Queue)
2. Removing
packagequeuemethod;
importjava.util.Queue;
importjava.util.LinkedList;
public class Queuemethod {
public static void main(String[] args) {
Queue<Integer> qi = new LinkedList<>();
qi.add(50);
qi.add(100);
Integer A = qi.remove();
System.out.println(“the first value is:”+A);
A = qi.remove();
System.out.println(“after remove the first value is:”+A);
A = qi.remove();
System.out.println(A);
System.out.println(qi);
}
}
From the following result, the third remove() call throws a NoSuchElementException
because it has been executed on an empty queue. This behavior, is what makes it
different from the poll() method.
The Dequeu interface abstracts this kind of queue, and it is a sub interface of the
Queue interface. And the LinkedList class is a well-known implementation. Some
implementations accept null elements, some do not. Queue does allow duplicate
elements, because the primary characteristic of queue is maintaining elements by
their insertion order. Duplicate elements in terms of equals contract are considered
distinct in terms of queue, as there are no two elements having same ordering.
Additionally, the Java Collection Framework provides the BlockingQueue interface
that abstracts queues which can be used in concurrent (multi-threading) context.
A blocking queue waits for the queue to become non-empty when retrieving an element and waits for space become available in the queue when storing an element.
Similarly, the BlockingDeque interface is blocking queue for double ended queues.
Application Activity 10.5.
1. What is Java Priority Queue?
2. Explain the method used in Queue interface and write a program that
those are applicable.
3. What is the difference between poll() and remove() in a PriorityQueue?
4. Give a question where students write a program by applied the queue
interface
5. Write a program and ask students to interpret is an give output
10.2.5 Java collections – Stack
Learning Activity 10.6.
Obverse carefully the following figure and respond to the asked questions:
1. Describe what you see on the above figure
2. According to the Figure: how the teller serves the customer?
3. With example discuss FIFO.
A stack is a container of objects that are inserted and removed according to the lastin first-out (LIFO) principle. In computer science, a stack is an abstract data type that
serves as a collection of elements, with two principal operations:
• push, which adds an element to the collection
• pop, which removes the most recently added element that was not yet removed.
a. Operations on Stack
The Push operation stores something on the top of the stack and the Pop operation
retrieves something from the top of the stack.
The following figures represent the stack operations.
b. LIFO Stack (Last In First Out)
A stack is a last-in-first-out (LIFO) data structure; in other words, the first thing to be
removed is the item most recently added. A push is when you put a new item onto
the stack, and a pop is when you take it off.
Some Applications of stack:
• The simplest application of a stack is to reverse a word. You push a given
word to stack - letter by letter - and then pop letters from the stack.
• Another application is an “undo” mechanism in text editors; this operation
is accomplished by keeping all text changes in a stack.
Application activity 10.6
1. Give the output of the following program:
Packagestackimpl;
Importjava.util.Stack;
public class StackImpl<E>
{
private Stack<E> stack;
publicStackImpl()
{
stack = new Stack<E>();
}
publicboolean empty()
{
returnstack.empty();
}
public E peek()
{
returnstack.peek();
}
public E pop()
{
returnstack.pop();
}
public E push(E item)
{
returnstack.push(item);
}
publicint search(Object o)
{
returnstack.search(o);
}
public static void main(String...arg)
{
StackImpl<Integer> stack = new
StackImpl<Integer>();
System.out.println(“element pushed :
“ + stack.push(3));
System.out.println(“element pushed :
“ + stack.push(4));
System.out.println(“element pushed
: “ + stack.push(-19));
System.out.println(“element pushed
: “ + stack.push(349));
System.out.println(“element pushed
: “ + stack.push(35));
System.out.println(“element poped :
“ + stack.pop());
System.out.println(“element poped :
“ + stack.pop());
System.out.println(“Element peek : “
+ stack.peek());
System.out.println(“position of
element 349 “ + stack.search(3));
while (!stack.empty())
{
System.out.println(“element poped :
“ + stack.pop());
}
}
}
2. What is the output of this
program?
importjava.util.*;
class stack
{
public static void main(String args[])
{
Stack obj = new Stack();
obj.push(new Integer(3));
obj.push(new Integer(2));
obj.pop();
obj.push(new Integer(5));
System.out.println(obj);
}
}
10.2.6. Java collection – Tree
Learning Activity 10.6.
Obverse carefully this figure and answer to the following questions:
1. What is a node in tree?
2. Illustrate relationship between A and B; E and F?
3. Draw your school organization structure?
a. Definition
A tree, T, by definition, is a non-empty set of elements where one of these elements
is called the root and the remaining elements are partitioned further into sub trees
of T.
A Tree is a non-linear data structure where data objects are organized in terms of
hierarchical relationship. The structure is non-linear in the sense that, unlike simple
array and linked list implementation, data in a tree is not organized linearly.
A tree data structure is a powerful tool for organizing data objects based on keys.
it can be defined as a collection of entities called nodes linked together to simulate
a hierarchy. It is equally useful for organizing multiple data objects in terms of hierarchical relationships (think of a “family tree”, where the children are grouped under
their parents in the tree).
a. Node in a Tree
Each data element is stored in a structure called a node. The topmost or starting
node of the (inverted) tree is called the root node. All nodes are linked with an edge
and form hierarchical sub trees beginning with the root node.
The descendants of A are arranged in a hierarchical fashion. A, at the top of the (inverted) tree, represents the root node. A’s children are B and C. B’s children are D and
E. C’s children are F and G. F has no children, E has one, and D has two. They are listed
in the same hierarchical manner. The link between each of the nodes is called an
edge. This link signifies the relationship that one node has with another, such as B’s
children, F’s sibling, A’s descendant, and so forth. Sometimes, the ending nodes of
the tree are called leaves.
• Node: stores a data element.
• Parent: single node that directly precedes a Node, all nodes have one
parent except root (has 0)
• Child: one or more nodes that directly follow a node
• Ancestor: any node which precedes a node. itself, its parent, or an
ancestor of its parent
• Descendent: any node which follows a node. itself, its child, or a descendent
of its child
• Root: The node at the top of the tree is called root. There is only one root
per tree and one path from the root node to any node.
More Tree Terminology
• Leaf (external) node: node with no children
• Internal node: non-leaf node
• Siblings: nodes which share same parent
• Subtree: a node and all its descendants. Ignoring the node’s parent, this is
itself a tree
• Ordered tree: tree with defined order of: tree with defined order of children.
Enables ordered traversal
• Binary tree: each node can have at least two children, ordered tree with up
to two. children per node
• Path: Path refers to the sequence of nodes along the edges of a tree.
• Visiting: Visiting refers to checking the value of a node when control is on
the node.
• Traversing: Traversing means passing through nodes in a specific order.
• Levels: Level of a node represents the generation of a node. If the root node
is at level 0, then its next child node is at level 1, its grandchild is at level 2,
and so on.
c. Advantages of a tree (Order of items in a tree)
The Tree data structure is useful on occasions where linear representation of data
does not suffice, such as creating a family tree. Java provides two in-built classes,
TreeSetand TreeMap, in Java Collection Framework that cater to the needs of the
programmer to describe data elements in the aforesaid form.
Treemap main advantage is that it allows to store the key-value mappings in a sorted order
Some Applications of Trees
• Storing naturally hierarchical data eg. File system
• Trees can hold objects that are sorted by their keys
• An operating system maintains a disk’s file system as a tree, where file
folders act as tree nodes
d. Storing elements in a tree
When an object contains two pointers to objects of the same type, structures can be
created that are much more complicated than linked lists, the most basic and useful
structures of this type used is binary trees. Each of the objects in a binary tree contains two pointers, typically called left and right.
• Binary Tree
A binary tree is a recursive data structure where each node can have 2 children at
most. A common type of binary tree is a binary search tree, in which every node
has a value that is greater than or equal to the node values in the left sub-tree, and
less than or equal to the node values in the right sub-tree. A binary tree of integers
would be made up of objects of the following type:
classTreeNode {
int item; // The data in this node.
TreeNode left; // Pointer to the left subtree.
TreeNode right; // Pointer to the right subtree.
}
e. Data representation
The simplest data representation is Nodes and Links; so a list of Nodes such as
1,2,3,4,5, and a list of links such as 1:2, 1:3, 2:4, 2:5 would represent the tree below:
f. Traversing the Tree
• Depth-First Search: is a type of traversal that goes deep as much as possible
in every child before exploring the next sibling.
here are several ways to perform a depth-first search: in-order, pre-order and post-order.
Example:
privateBinaryTreecreateBinaryTree() {
BinaryTreebt = new BinaryTree();
bt.add(6);
bt.add(4);
bt.add(8);
bt.add(3);
bt.add(5);
bt.add(7);
bt.add(9);
returnbt;
}
The in-order traversal in the console output: 3 4 5 6 7 8 9
The pre-order traversal in the console output: 6 4 3 5 8 7 9
Here are the nodes in post-order: 3 5 4 7 9 8 6
• Breadth-First Search: This is another common type of traversal that visits
all the nodes of a level before going to the next level.
In this case, the order of the nodes will be: 6 4 8 3 5 7 9
Example of TreeMap that store the element:
importjava.util.Map;
public class TreeMap {
public static void main(String[] args) {
Map<Integer, String >empInfo = new TreeMap<Integer,String>();
empInfo.put(20,”kalisa” );
empInfo.put(4,”Emmy” );
empInfo.put(9,”Diane” );
empInfo.put(15,”Karera” );
System.out.println(empInfo);
}
}
Application Activity 10.7.
1. 1)List the nodes of the tree below in preorder, post order, and breadthfirst order
2. Write an example showing basic operations on TreeMap like creating
an object, adding key-value pair objects, getting value by passing key
object, checking whether the map has elements or not, deleting specific
entry, and size of the TreeMap.
END UNIT ASSSSMENT
1. Describe the Collections type hierarchy. What are the main interfaces, and
what are the differences between them?
2. What is the difference between: List and Set? List and Map? ArrayList and
Vector?
3. How to create a List instance?
4. What is Queue and Stack, list their differences?
5. Write a Java program to insert an element into the array list at the first
position.
6. Write a Java program to search a key in a Tree Map