TK1143

TUTORIAL 4 (LIST)

Section A
1. Describe the differences between following Structure and when is the right time to use it a) Array
and ArrayList.

Arrays are used when there is a need to use many variables of the same type. Meanwhile, ArrayList
provides constant time for search operation, so it is better to use ArrayList if searching is more
frequent operation than add and remove operation. The table below shows the differences between
Array and ArrayList.
Basis Array ArrayList

Definition An array is a dynamically-created object. It serves as a The ArrayList is a class of

container that holds the constant number of values of Java Collections framework. It
the same type. It has a contiguous memory location. contains popular classes like Vector,
HashTable, and HashMap.

Static/ Array is static in size. ArrayList is dynamic in size.

Dynamic

Resizable An array is a fixed-length data structure. ArrayList is a variable-length data

structure. It can be resized itself
when needed.

Initialization It is mandatory to provide the size of an array while We can create an instance of
initializing it directly or indirectly. ArrayList without specifying its size.
Java creates ArrayList of default size.

Performance It performs fast in comparison to ArrayList because of ArrayList is internally backed by the

fixed size. array in Java. The resize operation in
ArrayList slows down the
performance.

Primitive/ An array can store both objects and primitives type. We cannot store primitive type in

Generic type ArrayList. It automatically converts
primitive type to object.

Iterating We use for loop or for each loop to iterate over an We use an iterator to iterate over
Values array. ArrayList.

Type-Safety We cannot use generics along with array because it is ArrayList allows us to store
not a convertible type of array. only generic/ type, that's why it is
type-safe.
 Length Array provides a length variable which denotes the ArrayList provides the size() method
length of an array. to determine the size of ArrayList.

Adding We can add elements in an array by using Java provides the add() method to

Elements the assignment operator. add elements in the ArrayList.

Single/ Array can be multi-dimensional. ArrayList is always single-

Multi- dimensional.
Dimensional

b) ArrayList and LinkedList

ArrayList provides constant time for search operation, so it is better to use ArrayList if searching is more frequent
operation than add and remove operation. The LinkedList provides constant time for add and remove operations.
So, it is better to use LinkedList for manipulation.

ArrayList LinkedList

1) ArrayList internally uses a dynamic array to store the LinkedList internally uses a doubly linked list to store the
elements. elements.

2) Manipulation with ArrayList is slow because it Manipulation with LinkedList is faster than ArrayList

internally uses an array. If any element is removed from because it uses a doubly linked list, so no bit shifting is
the array, all the other elements are shifted in memory. required in memory.

3) An ArrayList class can act as a list only because it LinkedList class can act as a list and queue both because
implements List only. it implements List and Deque interfaces.

4) ArrayList is better for storing and accessing data. LinkedList is better for manipulating data.

5) The memory location for the elements of an The location for the elements of a linked list is not
ArrayList is contiguous. contagious.

6) Generally, when an ArrayList is initialized, a default There is no case of default capacity in a LinkedList. In
capacity of 10 is assigned to the ArrayList. LinkedList, an empty list is created when a LinkedList is
initialized.

7) To be precise, an ArrayList is a resizable array. LinkedList implements the doubly linked list of the list
interface.

c) Stack, Queue and List?

Stack Queue List
Concept: FILO or LIFO Concept: FIFO There is no concept or rules in List
data structure
Implements: Stack Class from Java Implement: Queue API (User defined class) Implement: List Class from Java
 Library Library
Method: push, pop, peek, isEmpty, size Method: enqueue, dequeue, size, isEmpty, Method: add, remove, getFirst, size,
peek empty
Stack data structures are useful when The queue data structure is used for serving The need for List data structure is
the order of actions is important. They requests on a single shared resource, such as most obvious when you have the urge
ensure that a system does not move when a single resource is shared among to store items without knowing how
onto a new action before completing multiple consumers, such as printer, CPU much space you'll need in advance.
those before. Here are some common task scheduling, wash machine simulation Also, when you often have the need
examples where a stack is used: and palindrome. to add or get elements from a data
Calculator, Postfix Machine, Infix-postfix structure, the array list would suit
Converter, Balance symbol checker well because those operations are fast
and efficient. The examples of
problems use List are Text
concordance, find unique words and
display the frequent of duplicate
words.

2. Consider a following figure of myList elements with the specific index.

14 20 38 5 7
0 1 2 3 4

a) Write Java code to declare myList from type of integer.

List <Integer> myList = new ArrayList<Integer>();
b) How many elements in myList?
5

c) Write Java code to add all the elements in myList

import java.util.*;
public class MyList {
public static void main(String[] args) {
List<Integer>myList = new ArrayList<Integer>();
myList.add(14);
myList.add(20);
myList.add(38);
myList.add(5);
myList.add(7);
System.out.print(myList);

d) State an index of element 5.

3

e) Write Java code and illustrates the elements of myList after adding element 15 at index 1.
import java.util.*;
public class MyList {
public static void main(String[] args) {
List<Integer>myList = new ArrayList<Integer>();
myList.add(14);
 f) Write Java code and illustrates the elements of myList after removing element 38 at index 2.
import java.util.*;
public class MyList {
public static void main(String[] args) {
List<Integer>myList = new ArrayList<Integer>();
myList.add(14);
myList.add(20);
myList.add(38);
myList.add(5);
myList.add(7);
//myList.add(1,15);
myList.remove(2);
System.out.print(myList);

14 20 5 7
0 1 2 3

3. Consider the following Java code.

 a) What is the name of the iterator used in the above code?
it and it2

b) What is the purpose of the iterator in the above code?

Iterator is used to iterate through elements of list using at least hasNext method and next method and display
all or some elements of the list.

c) Write the output of the code.

Number of Home in myList: 1

myNumbers List:
1 2 3 4 5 6 7 8

Section B
1. Based on the Class Person and PersonApp answer the following question.

Class Person

Class PersonApp

a) Can you explain class PersonApp code in line 15-18 ? What is the purpose of that code?

From line 15-18, the class PersonApp use Collections.sort method to sort the persons by name and
age by doing comparison between the objects.
 b)What is the output from this code?
[{name='Bulya', age=18}, {name='Mierza', age=19}, {name='Irdina', age=20},
{name='Muaz', age=20}, {name='Sharon', age=24}]

2. Please answer the question based on the full structure of worked-example program in reading
material : List of Words.

1 import java.util.*; public class MyList {

2 public static void main(String args[]){
3
4 List<String> list1 = new ArrayList <String>();
5 Scanner in = new Scanner(System.in);
6
7 String passage = in.nextLine(); // read input passage
8 String delims = "\\W+"; // split any non-
9 word String [] words = passage.split(delims);
10 for (String str: words){
11 str = str.trim();
12 list1.add(str);
13 }
14 Iterator it = list1.iterator() ;
15 while (it.hasNext())
16 System.out.print(it.next() + “ “ ) ;
17 }
18 }
19

a) What is the purpose of list in the program?

To list out each of word from text concordance in String data type without symbols and blank
spaces.

b) Write the statement to complete the process for line 12?

c) Named the method used to add new string into the list? Which line to indicate this process?
The add() method. For example, list1.add() . Use this method at line 12.

d) Write the equivalent statement for line 15 to display all words.

3. Please answer the question based on the full structure of worked-example program in reading material :
List of Unique Words.
 1 import java.util.*;
2 public class MyList {
3
4 public static void main(String args[]) {
5
6 List<String> list1 = new ArrayList <String>();
7 boolean isDuplicate;
8 Scanner in = new Scanner (System.in);
9
10
11 String passage = in.nextLine(); // read input passage
12 String delims = "\\W+"; // split any non word
13 String [] words = passage.split(delims);
14
15 for (String str : words){
16 str = str.trim();
17 isDuplicate=false;
18 isDuplicate =CheckForDuplicates (list1, str);
19
20 if (!isDuplicate) {
21 list1.add(str);
22 int i;
23 i++;
24 }
25 }
26 System.out.println(list1);
27 }
28
29 static boolean CheckForDuplicates (List L1, String word) {
30 Iterator it = L1.iterator();
while(it.hasNext()) {
String str = (String)it.next();
if(str.equals(word))
return true;
}
return false;
}
}

a) Discuss the different between the list of words and list of unique words.

List of words display all the words including the duplicate words while list of unique words shows
all the unique words without any duplicate words.

b) Complete the code in line 20 to add a new word into list

c) Complete the code in line 23 to display all element of unique word in list
d) Specify the reason of using iterator in this problem.

Iterator is used to iterate through all the elements of list1 one by one and do comparison between
word and the element in list1. If they are same, the word will not add into the list1. Otherwise, the
word will add into list1.
4. Please answer the question based on the full structure of worked-example program reading material :
List of Sorted Words.
1 import java.util.*; public class MyList {
a) State 2 public static void main(String args[]) {
the 3 List<String> list1 = new ArrayList <String>();
4 Scanner in = new
5 Scanner(System.in); boolean
6 isDuplicate; int size=0;
7
8 String passage = in.nextLine(); // read input passage
9 String delims = "\\W+"; // split any non
10 word String [] words =
11 passage.split(delims); for (String str :
12 words){ str = str.trim(); isDuplicate=false;
13 isDuplicate =CheckForDuplicates (list1, str);
14 if (!isDuplicate) {
15 //add new word into list and update the list size
16 }
17 //sort the list
18 }
19 displayList(list1, size);
20 }
21 static boolean CheckForDuplicates (List L1, String word) {
22 // check for duplicate words
23 // if found duplicate return true else return false
24 }
25
26 static void displayList(List l1, int s) {
27 // use the iterator to iterate list
28 // and display all elements
29 }
30 }//The Program Ends Here
31
32
33
differences between List of Unique Words and List of Sorted Words.

b) Name the user defined functions used in List of Sorted Unique Words and its purpose.

c) Complete the CheckForDuplicates() and displayList() methods.

d) Write the code segment to sort the list in line 19.

5. Write a java program that read list of integer numbers from input user. If the number is even add it into
evenList. Otherwise add to oddList. At the end of the code, display the elements of the odd and even numbers
list respectively with ascending order. Display your output in the following format:
< Odd or Even list> <Size_of_list in a bracket>: <the elements of the list that are separated by a space>
[Note: The code must use list and iterator] Sample IO:

Input Output
2 3 0 -15 8 22 -11 6 -7 18 Odd List (4): -15 -11 -7 3
Even List (6): 0 2 6 8 18 22

Answer:
//BQ5
import java.util.*;
public class OddEvenList {
public static void main(String[] args) {
List<Integer> evenList = new ArrayList<Integer>();
List<Integer> oddList = new ArrayList<Integer>();
Scanner sc = new Scanner(System.in);

int e = 0;
int o = 0;
String n = sc.nextLine();
String [] numbers = n.split(" ");

for(String num: numbers) {

num = num.trim();
int nm = Integer.parseInt(num);
if(nm%2 == 0) {
evenList.add(nm);
e++;
}
else {
oddList.add(nm);
o++;
}
}
Collections.sort(evenList);
Collections.sort(oddList);

Iterator it = oddList.iterator();
System.out.print("Odd List (" + o + "): ");
while(it.hasNext())
System.out.print(it.next() + " ");

Iterator it2 = evenList.iterator();

System.out.println();
System.out.print("Even List (" + e + "): ");
while(it2.hasNext())
System.out.print(it2.next() + " ");

}
6. Create a program that receives sequence of integers that ends with 0. For every non-repeating number add it
into NumberList. Display the size and all list elements. Then display all list elements again after composing
them in an ascending order. Follow the following output format.
<Size_of_list>: <the elements of the list that are separated by a space>.
[Note: The code must use list and iterator]

Sample IO:

Input Output
5 1 2 1 1 1 6 2 1 0 4: 5 1 2 6
4: 1 2 5 6

Section C :
There are four (4) questions given in this section. Your task is to write the program to implement data
structure List for each question.

LIST OF WORDS
Input Standard Input

Output Standard Output

Java Elements Looping
Data Structure List
Additional Function Trim and Remove all non-alphabetical characters

Problem Description
The List of Words problem aims to display all words from a given passage. Your task is to write a Java program for
the List of words.
Input
Input of this program is a passage. A passage consists of N words and symbols. Symbols that will be considered in
the passage are full stop (.), comma (,), question mark (?) and exclamation mark (!).
Output
Output of the program is N lines, where each line contains a word.

Sample Input-Output

Input Output
I go to school by bus. The bus is big. I go
The school is also big. I like big school to
and big bus. schoo
l by
bus
The
bus
is
big
The
schoo
l is
 also
big I
like
big
school
and
big
bus

Solution
The algorithm for List of Words:
Read a passage.
For all words in the passage:

Add the word at the back of list

Display all words.

Basic Structure:

import java.util.*;

public class ListDemo {

public static void main(String[] args) {

List<String> myString = new ArrayList <String>();
Scanner in = new Scanner(System.in);

String passage = in.nextLine(); // read input passage

String delims = "\\W+"; // split any non-word
String [] words = passage.split(delims);
for (String str: words){

}
}
Full structure of worked-example program: List of Words.
 1 import java.util.*; public class MyList {
2 public static void main(String args[]){
3
4 List<String> list1 = new ArrayList <String>();
5 Scanner in = new Scanner(System.in);
6
7
String passage = in.nextLine(); // read input passage
8
String delims = "\\W+"; // split any non-
9
word String [] words =
10
passage.split(delims); for (String str:
11
words){
12
//remove leading and trailing spaces
13
//add the word athe back of list
14
}
15
//display all
16 word }
17
}

Tutorial Activity:
1. What is the purpose of list in the program?
2. What is the purpose of variable str?
3. Named the method used to add new string into the list? Which line to indicate this process?
4. What is the purpose of the statements in line 15 to 17?

LIST OF UNIQUE WORDS

Input Standard Input
 Output Standard Output
Data Structure List

Problem Description
List of Unique Words problem aims to display all words from a given passage in a non-recurring form.
Your task is to write a Java program for the List of Unique Words.

Input
Input of this program is a passage. A passage consists of N words and symbols. Symbols that will be
considered in the passage are full stop (.), comma (,), question mark (?) and exclamation mark (!). The
passage will have M unique words, where the M is less than or equal to N.

Output
Output of the program is M lines, where each line contains a unique word.

Sample Input-Output

Input Output
I go to school by bus. The bus is big. The school is I go
also big. I like big school and big bus. to
school
by bus
The is
big
also
like
and

Solution
The algorithm for List of Unique Words:
Read a passage
For all words in the passage:
Remove unnecessary characters
If the word not exist in list
Add the word at the back of list

Display the list.

Full structure of worked-example program: List of Unique Words.

 1 import java.util.*;
2 public class MyList {
3
4 public static void main(String args[]) {
5
6 List<String> list1 = new ArrayList <String>();
7 boolean isDuplicate;
8 Scanner in = new Scanner(System.in);
9
10
11 String passage = in.nextLine(); // read input passage
12 String delims = "\\W+"; // split any non word
13 String [] words = passage.split(delims);
14
15 for (String str : words){
16 str = str.trim();
17 isDuplicate=false;
18 isDuplicate =CheckForDuplicates (list1, str);
19
20 if (!isDuplicate) {
21 //add new word into list and update the list size
22 }
23 }
24 // display all elements of list
25 }
26
27 static boolean CheckForDuplicates (List L1, String word) {
28 // check for duplicate words
29 // if found duplicate return true else return false
30 }
}

Tutorial Activity:
1. Write the java code to show the if statement to check for duplicates word in the list.
2. Discuss the different between the list of words and list of unique words.
3. Specify the reason of using iterator in this problem.

LIST OF SORTED UNIQUE

WORDS
Input Standard Input

Output Standard Output

JAVA Elements Selection, Looping,

Data Structure List

Problem Description
List of sorted words problem aims to display all words from a given passage in an ascending order. Your task is to
write a JAVA program for the List of Sorted Words.

Program Scope: Value of ‘A’ is smaller that ‘a’. Each character is based on the value of ASCII CODE, where
ASCII CODE of character ‘A’ is 65, and character ‘a’ is 97. This mean that the word “The” is greater than
word “also”.

Input
Input of this program is a passage. A passage consists of N words and symbols. Symbols that will be considered in
the passage are full stop (.), comma (,), question mark (?) and exclamation mark (!). The passage will have M unique
words, where the M is less than or equal to N.

Output
Output of the program is M lines, where each line contains a list of Sorted unique word.

Sample Input-Output

Input Output
I go to school by bus. The bus is big. The school is I The
also big. I like big school and big bus. also
and
big
bus by
go is
like
school
to

Solution
The algorithm for List of Sorted Words:
Read a passage
For all words in the passage:
If the word not exist in list
Add the word into the list
Sort the list

Display all word.

Full structure of worked-example program: List of Sorted Words.

 1 import java.util.*; public class MyList {
2 public static void main(String args[]) {
3 List<String> list1 = new ArrayList <String>();
4 Scanner in = new
5 Scanner(System.in); boolean
6 isDuplicate; int size=0;
7
8 String passage = in.nextLine(); // read input passage
9 String delims = "\\W+"; // split any non
10 word String [] words =
11 passage.split(delims); for (String str :
12 words){ str = str.trim(); isDuplicate=false;
13 isDuplicate =CheckForDuplicates (list1, str);
14 if (!isDuplicate) {
15 //add new word into list and update the list size
16 }
17 //sort the list
18 }
19 displayList(list1, size);
20 }
21 static boolean CheckForDuplicates (List L1, String word) {
22 // check for duplicate words
23 // if found duplicate return true else return false
24 }
25
26 static void displayList(List l1, int s) {
27 // use the iterator to iterate list
28 // and display all
29 elements }
30 }//The Program Ends Here
31
32
33
Tutorial Activity:
1. State the differences between List of Unique Words and List of Sorted Words.
2. Name the method use to add new word into list.
3. Name the user defined functions used in List of Sorted Unique Words and its purpose.
4. Complete the CheckForDuplicates() and displayList() methods.
5. Write the statement to sort the list.

WORD FREQUENCIES
Input Standard Input

Output Standard Output

Data Structure List

Problem Description
Write a JAVA program that will display all words from a given passage with its frequencies. At the end of output,
print the text analysis such as (i) Total words, (ii) Number of Repeated words, (iii) Number of Unique words
and (iv) Most used word. Input
Input of this program is a passage. A passage consists of N words and symbols. Symbols that will be considered in
the passage are full stop (.), comma (,), question mark (?) and exclamation mark (!).
The passage will have M unique words, where the M is less than or equal to N.

Output
Output of the program is M lines, where each line contains a word followed by symbol (, then followed by an
integer that represent the word frequency and ends by symbol). Display the analysis of Total words,
Number of repeated words, Number of unique words and Most used word as shown in Sample Input- Output.

Sample Input-Output

Input Output
I go to school by bus. The bus is big. I(2)
The school is also big. I like big school The(2)
and big bus. also(1)
and(1)
big(4)
bus(3)
by(1)
go(1)
is(2)
like(1)
school(3)
to(1)

Total words: 22
Number of repeated words: 6
Number of unique words: 12
Most used word: big

Solution
The algorithm for Words Frequencies:
Read a passage
For each word in the passage:
Search for the same word in the list
If not found:
Add the word into the list
Set and add the word’s frequency to 1
If found:
Update the word’s frequency value in list
Sort the list

Display the list and text analysis

Class Data
** You must use class Data to complete question 4 in Section C for submission to CodeZinger

1 import java.util.Comparator;
2
3 // Class Data
4 public class Data {
5 String word;
6 int freq;
7
8 public Data (String item){
9 this.word =item;
10 this.freq=1;
11 }
12
13
14 public String getWord() {
15 return word;
16 }
17
18 public void setWord(String newword) {
19 this.word= newword;
20 }
21
22 public int getFreq() {
23 return freq;
24 }
25
26 public void setFreq(int freq2) {
27 this.freq = freq2;
28 }
29
30
public static Comparator<Data> WordComparator = new Comparator<Data>()
31 {
32 // Used for sorting in ascending order of word
33 public int compare(Data a, Data b)
34 {
35 String word1 = a.getWord();
36 String word2 = b.getWord();
37
38
39 return (word1).compareTo(word2);
40 //string1.compareTo(string2) }
};
}