Java Collection Framework

Pertemuan 9

Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN
Topics

1. Java Collection Framework

a) List
b) Set
c) Map

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN2
Java Collections

• Collection merupakan suatu objek yang

mengelompokkan berbagai elemen
kedalam satu unit
• Kegunaan :
• Menyimpan, membaca dan memanipulasi
data
• Mengirimkan data dari satu method ke
method lain
• Struktur data

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN3
Collection Framework

• Collection Framework merupakan suatu

arsitektur untuk merepresentasikan dan
mengelola suatu collection.
• Terdiri atas 3 (tiga) hal, yaitu :
• Interfaces
• Implementations
• Algorithms

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN4
Collection Framework Diagram

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN5
Beberapa tipe collection framework
• List :
• Ketika urutan (sequence)
menjadi pertimbangan
• Ingin mengetahui posisi
berdasarkan index
• Boleh duplikasi value
• Set
• Ketika keunikan (uniqueness)
menjadi pertimbangan
• Tidak boleh duplikasi value
• Map
• Ketika mencari berdasarkan
kunci menjadi pertimbangan
• Boleh duplikasi value, namun
tidak boleh duplikasi key

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN6
Collection Interface
• Defines fundamental methods
• int size();
• boolean isEmpty();
• boolean contains(Object element);
• boolean add(Object element); // Optional
• boolean remove(Object element); // Optional
• Iterator iterator();

• These methods are enough to define the basic

behavior of a collection
• Provides an Iterator to step through the elements
in the Collection

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN7
Iterator Interface
• Defines three fundamental methods
• Object next()
• boolean hasNext()
• void remove()
• These three methods provide access to the
contents of the collection
• An Iterator knows position within collection
• Each call to next() “reads” an element from the
collection
• Then you can use it or remove it

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN8
Iterator Position

25/11/2018
Ghifari Munawar, S.Kom, M.T Jurusan Teknik Komputer dan Informatika - POLBAN9
Example - SimpleCollection
public class SimpleCollection {
public static void main(String[] args) {
Collection c;
c = new ArrayList();
System.out.println(c.getClass().getName());
for (int i=1; i <= 10; i++) {
c.add(i + " * " + i + " = "+i*i);
}
Iterator iter = c.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}

25/11/2018
Ghifari Munawar, S.Kom, M.T 10
Jurusan Teknik Komputer dan Informatika - POLBAN
a. List
Collection

List

25/11/2018
Ghifari Munawar, S.Kom, M.T 11
Jurusan Teknik Komputer dan Informatika - POLBAN
ArrayList and LinkedList Context
Collection

List

ArrayList LinkedList

25/11/2018
Ghifari Munawar, S.Kom, M.T 12
Jurusan Teknik Komputer dan Informatika - POLBAN
List Implementations
• ArrayList
• low cost random access
• high cost insert and delete
• array that resizes if need be
• LinkedList
• sequential access
• low cost insert and delete
• high cost random access

25/11/2018
Ghifari Munawar, S.Kom, M.T 13
Jurusan Teknik Komputer dan Informatika - POLBAN
ArrayList overview

• Constant time positional access (it’s an

array)
• One tuning parameter, the initial capacity
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException(
"Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
}

25/11/2018
Ghifari Munawar, S.Kom, M.T 14
Jurusan Teknik Komputer dan Informatika - POLBAN
ArrayList methods
• The indexed get and set methods of the List interface are
appropriate to use since ArrayLists are backed by an
array
• Object get(int index)
• Object set(int index, Object element)
• Indexed add and remove are provided, but can be costly
if used frequently
• void add(int index, Object element)
• Object remove(int index)
• May want to resize in one shot if adding many elements
• void ensureCapacity(int minCapacity)

25/11/2018
Ghifari Munawar, S.Kom, M.T 15
Jurusan Teknik Komputer dan Informatika - POLBAN
LinkedList overview
• Stores each element in a node
• Each node stores a link to the next and previous
nodes
• Insertion and removal are inexpensive
• just update the links in the surrounding nodes
• Linear traversal is inexpensive
• Random access is expensive
• Start from beginning or end and traverse each node
while counting

25/11/2018
Ghifari Munawar, S.Kom, M.T 16
Jurusan Teknik Komputer dan Informatika - POLBAN
 LinkedList entries
private static class Entry {
Object element;
Entry next;
Entry previous;

Entry(Object element, Entry next, Entry previous) {

this.element = element;
this.next = next;
this.previous = previous;
}
}

private Entry header = new Entry(null, null, null);

public LinkedList() {
header.next = header.previous = header;
}

25/11/2018
Ghifari Munawar, S.Kom, M.T 17
Jurusan Teknik Komputer dan Informatika - POLBAN
 LinkedList methods
• The list is sequential, so access it that way
• ListIterator listIterator()

• ListIterator knows about position

• use add() from ListIterator to add at a position
• use remove() from ListIterator to remove at a position
• LinkedList knows a few things too
• void addFirst(Object o), void addLast(Object o)
• Object getFirst(), Object getLast()
• Object removeFirst(), Object removeLast()

25/11/2018
Ghifari Munawar, S.Kom, M.T 18
Jurusan Teknik Komputer dan Informatika - POLBAN
b. Set
Collection

Set

25/11/2018
Ghifari Munawar, S.Kom, M.T 19
Jurusan Teknik Komputer dan Informatika - POLBAN
Set Interface
• Same methods as Collection
• different contract - no duplicate entries
• Defines two fundamental methods
• boolean add(Object o) - reject duplicates
• Iterator iterator()
• Provides an Iterator to step through the elements
in the Set
• No guaranteed order in the basic Set interface
• There is a SortedSet interface that extends Set

25/11/2018
Ghifari Munawar, S.Kom, M.T 20
Jurusan Teknik Komputer dan Informatika - POLBAN
HashSet and TreeSet Context
Collection

Set

HashSet TreeSet

25/11/2018
Ghifari Munawar, S.Kom, M.T 21
Jurusan Teknik Komputer dan Informatika - POLBAN
 HashSet
• Prevent duplicates in the collection
• Can find and add that elements in the collections
very quickly
• Hashing uses an array of linked lists
• The hashCode() is used to index into the array
• Then equals() is used to determine if element is in the
(short) list of elements at that index
• The hashCode() method and the equals() method
must be compatible
• if two objects are equal, they must have the same
hashCode() value
25/11/2018
Ghifari Munawar, S.Kom, M.T 22
Jurusan Teknik Komputer dan Informatika - POLBAN
TreeSet
• Prevent duplicates in the collections
• Keep the element sorted
• Elements can be inserted in any order
• The TreeSet stores them in order
• Red-Black Trees out of Cormen-Leiserson-Rivest
• An iterator always presents them in order
• Default order is defined by natural order
• objects implement the Comparable interface
• TreeSet uses compareTo(Object o) to sort
• Can use a different Comparator
• provide Comparator to the TreeSet constructor

25/11/2018
Ghifari Munawar, S.Kom, M.T 23
Jurusan Teknik Komputer dan Informatika - POLBAN
c. Map
Map

25/11/2018
Ghifari Munawar, S.Kom, M.T 24
Jurusan Teknik Komputer dan Informatika - POLBAN
Map Interface
• Stores key/value pairs
• Maps from the key to the value
• Keys are unique
• a single key only appears once in the Map
• a key can map to only one value
• Values do not have to be unique

25/11/2018
Ghifari Munawar, S.Kom, M.T 25
Jurusan Teknik Komputer dan Informatika - POLBAN
Map methods
Object put(Object key, Object value)
Object get(Object key)
Object remove(Object key)
boolean containsKey(Object key)
boolean containsValue(Object value)
int size()
boolean isEmpty()

25/11/2018
Ghifari Munawar, S.Kom, M.T 26
Jurusan Teknik Komputer dan Informatika - POLBAN
Map views
• A means of iterating over the keys and values in a Map
• Set keySet()
• returns the Set of keys contained in the Map
• Collection values()
• returns the Collection of values contained in the Map.
This Collection is not a Set, as multiple keys can map to
the same value.
• Set entrySet()
• returns the Set of key-value pairs contained in the
Map. The Map interface provides a small nested
interface called Map.Entry that is the type of the
elements in this Set.
25/11/2018
Ghifari Munawar, S.Kom, M.T 27
Jurusan Teknik Komputer dan Informatika - POLBAN
HashMap and TreeMap Context
Map

HashMap TreeMap

25/11/2018
Ghifari Munawar, S.Kom, M.T 28
Jurusan Teknik Komputer dan Informatika - POLBAN
HashMap and TreeMap
• HashMap
• The keys are a set - unique, unordered
• Fast

• TreeMap
• The keys are a set - unique, ordered
• Same options for ordering as a TreeSet
• Natural order (Comparable, compareTo(Object))
• Special order (Comparator, compare(Object,
Object))

25/11/2018
Ghifari Munawar, S.Kom, M.T 29
Jurusan Teknik Komputer dan Informatika - POLBAN
Bulk Operations
• In addition to the basic operations, a Collection
may provide “bulk” operations
boolean containsAll(Collection c);
boolean addAll(Collection c); // Optional
boolean removeAll(Collection c); // Optional
boolean retainAll(Collection c); // Optional
void clear(); // Optional
Object[] toArray();
Object[] toArray(Object a[]);

25/11/2018
Ghifari Munawar, S.Kom, M.T 30
Jurusan Teknik Komputer dan Informatika - POLBAN
Kesimpulan
• Java Collection Framework mencakup : List,
Set, Map
• List digunakan ketika urutan (sequences)
menjadi pertimbangan.
• Set digunakan ketika keunikan
(uniqueness) menjadi pertimbangan.
• Map digunakan ketika pencarian
berdasarkan kunci (key) menjadi
pertimbangan

25/11/2018
Ghifari Munawar, S.Kom, M.T 31
Jurusan Teknik Komputer dan Informatika - POLBAN
Referensi

• Head first java 2nd Edition. Chapter 16 :

Collections and Generic
• Java Collections. URL
[http://www.cs.washington.edu/education/c
ourses/403/03wi/]

25/11/2018
Ghifari Munawar, S.Kom, M.T 32
Jurusan Teknik Komputer dan Informatika - POLBAN
Tugas
• Tugas Collection (pelajari kasus yang
diberikan)
• Pengumpulan tugas dilakukan melalui
dropbox sebagaimana biasanya, dokumen
berbentuk pdf yang berisi source code dan
juga screenshoot hasilnya.
• Tuliskan nim & nama nya pada file yang akan
dikirimkan.
• Dikumpulkan selambat-lambatnya 1 hari
sebelum perkuliahan berikutnya.

25/11/2018
Ghifari Munawar, S.Kom, M.T 33
Jurusan Teknik Komputer dan Informatika - POLBAN