Computer Science

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 ; // Here a linked list is created and assigned

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 and put, to remain constant even

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