Transcript Collection

Collections
Data structures in Java
OBJECTIVE
Debug
“ WHEN TO USE WHICH DATA
STRUCTURE ”
Data Structures
1. A data structure is an arrangement of data
in a computer’s memory.
2. It includes list,stack,binary trees, hash
tables, etc.
3. Algorithms manipulate the data in these
structures in various ways such as searching
and sorting.
What is a Collections
framework?

A framework is an extensive set of interfaces,
abstract classes and concrete classes together
with support tools

Framework is provided in java.util package &
comprises three parts:
1. Core interfaces
2. Set of implementations.
3. Utility methods
Need of a framework????

Pre Java SDK1.2, Java provided a handful of data structures:



Hash Table
Vector
Stack

These were good and easy to use, but they were not
organized into a more general framework.

Lacked interoperability.
Features of Collection
framework

Reduces programming effort.

Increases performance.

Provides interoperability between unrelated
APIs.

Faster software reuse.
Interfaces and implementation
Extends
Implements
Collection
Map
Interface
Class
Set
HashMap
List
HashSet
LinkedList
SortedMap
SortedSet
ArrayList
TreeMap
TreeSet
Interfaces
Collection  Set, List

A group of objects.

May or may not be ordered;

May or may not contain duplicates.
Interface continued



Set 
 The familiar set abstraction.
 No duplicates;
May or may not be ordered.
List 
 Ordered collection, also known as a sequence.
 Duplicates permitted; Allows positional access
Map 
 A mapping from keys to values.
 Each key can map to at most one value (function).
Iterators

A collection provides an iterator which allows
sequential access to the elements of a
collection.

Methods:
has Next() – check if there are still elements
 next() – return the next object and advance
 remove() – remove the currently pointed object

List interface


An interface that extends the Collections
interface.
An ordered collection .
Stores element by position
 Includes index based operation.


Allows duplicate elements.
Concrete List Implementations

There are two concrete implementations of the List
interface



LinkedList
ArrayList
Which is best to use depends on specific needs.
Array List

Stores element in a contiguous block of
memory and automatically expandable.

The collection efficiently (O(1)) inserts and
deletes elements at the rear of the list.
Operations at Intermediate positions have O(n)
efficiency.

Link List


Elements have a value and links that identify
adjacent elements in the sequence.
Inserting or deleting elements are O(1)
operations.
Link list vs. Array List
Link List
1. No random access
2. Fast Manipulation
Array List
1. Fast random access
2.Slow manipulation
Set Interface



Set also extends Collection, but it prohibits
duplicate items (this is what defines a Set).
No new methods are introduced.
Concrete Set implementations contain methods
that forbid adding two equal Objects.
HashSets Vs Tree Set
Hash Set
Storage method: hash table
Space used:
O(n)
Put speed:
O(1)
Iteration order: Arbitrary
Tree Set
red black tree
O(n)
O(lg n)
Sorted
Rule of thumb: Use a Tree only if you need them
sorted, otherwise use a Hash
Maps




Maps are similar to collections but are actually
represented by an entirely different class hierarchy.
Maps store objects by key/value pairs.
Keys may not be duplicated.
Each key may map to only one value.
Map Implementations

Java provides several common class
implementations:

HashMap
A hashtable implementation of a map.
 Good for quick searching where order doesn’t matter.


TreeMap
A tree implementation of a map.
 Good when natural ordering is required.

HashMap Vs Tree Map
Hash map
Storage method: hash table
Space used:
O(n)
Put speed:
O(1)
Iteration order: Arbitrary
Tree map
red black tree
O(n)
O(lg n)
Sorted
Rule of thumb: Use a Tree only if you need them
sorted, otherwise use a Hash
Small
amou
nt of
data?
Start
yes
Amou
nt of
data
predic
table?
More
additi
on
deleti
on?
No
yes
linked list
No
No
Hash
Table
yes
Searchin
g and
insertion
must be
very
fast?
No
Binary
Search
Tree
yes
Key
distribut
ion
guarante
ed
random?
No
Balanced
Tree
yes
Array list
Search
speed more
important
then
insertion
speed ?
No
Unordered
Array
yes
Ordered
Array
Data Structures
Array
Ordered array
Advantages
Quick insertion,
Slow search, slow
very fast access if deletion, and fixed
index known.
size.
Quicker search
Slow insertion and
than unsorted array deletion, fixed size
Stack
Last in first out
Queue
First in first out
access.
Quick insertion,
quick deletion
Random Access
Linked list
Array List
Disadvantages
Slow access to
other items
Slow access to
other items
Slow search
Slow insertion,
deletion
Thank you