

II. Data Structure Basic Concepts

Java Collections Framework
Introduction to Data Structures

 Foundational Tools
Data structures are the foundational tools used to store, organize,
and manage data in a computer system.

 Performance Impact
They determine how data is arranged in memory and how Data Structures as Containers
efficiently it can be accessed, modified, or processed.

  
Folder for Box for Tools Shelf for Books
 Efficiency Matters Documents

Choosing the right data structure is crucial, as it directly affects a

program's speed, memory usage, and overall performance.
Java Collections Framework Overview

 What is it?
A collection of interfaces and classes that helps in storing and
processing data efficiently.

Collections Framework Hierarchy

 Useful Features Collection

Includes several useful classes with tons of useful functions
which make a programmer's task super easy. List Set Queue

ArrayList LinkedList HashSet TreeSet PriorityQueue

 Framework Structure
Organized hierarchy with interfaces at the top and concrete
implementations below, providing a unified architecture.
List Interface Overview

 What is a List?  Common Implementations

An ordered Collection (sequence) where elements maintain the
ArrayList
order in which they were added. Unlike sets, a list can contain 
A resizable array implementation, good for fast random
duplicate elements, meaning the same value can appear more access.
than once.

LinkedList

Uses nodes linked together, efficient for frequent insertions or
 Maintains Order  Allows Duplicates deletions.

Elements maintain insertion order, Can contain duplicate elements,

preserving the sequence in which unlike Set implementations. Vector
they were added.

A synchronized, resizable array (legacy, but still in use).

# Indexed Access  Dynamic Size Stack


Each element has a position with Can grow or shrink dynamically A subclass of Vector that follows the LIFO (Last In, First Out)
principle.
zero-based index for direct depending on the implementation.
access.
ArrayList

 What is ArrayList?  Visual Representation

One of the most widely used implementations of the List
interface in Java. Based on a dynamic array data structure that
can automatically grow or shrink as elements are added or
removed.

 Dynamic Sizing  Fast Random Access A B C D E

Automatically grows or shrinks as Elements stored in zero-based
elements are added or removed, index order, making retrieval by
unlike regular arrays with fixed index very fast (O(1) time [0] [1] [2] [3] [4]

size. complexity).
+ Add  Update  Remove  Get  Sort

 Allows Duplicates  Full Operations Support

Supports storing duplicate values Supports all optional list
and null elements without operations such as adding,
restrictions. removing, and updating elements.
LinkedList

 What is LinkedList?  Visual Representation

A linear data structure where elements (called nodes) are
connected using references (pointers) instead of being stored in
contiguous memory like arrays.

A B C
→ →
 Singly Linked List  Doubly Linked List →B →C → null

Each node stores data and a Each node stores data and two
pointer to the next node only. pointers: prev and next. Allows
Traversal is forward only. two-way traversal.
Node Structure

Data Next Prev

Value Pointer Pointer

Forward and backward


 Simpler implementation traversal
 Uses less memory  Faster insertion/removal
 Cannot traverse backward  Used by Java's LinkedList
Vector

 What is Vector?  Vector vs ArrayList

A resizable, synchronized list that stores elements in insertion
order and allows duplicates, including null. Because it is Feature Vector ArrayList
synchronized, multiple threads can safely access and modify a
Vector without causing data errors. Thread
 Yes  No
Safety

Slower due to Faster in single-

Performance
 Thread-Safe  Maintains Order synchronization threaded apps
Synchronized operations make it Elements are stored in insertion
safe for multithreaded programs order, preserving the sequence in Legacy Legacy class (Java
Modern (Java 1.2+)
Status 1.0)
where multiple tasks run which they were added.
concurrently.
Best Use Multithreaded Single-threaded
Case environments applications

 Allows Duplicates  Resizable

Can contain duplicate elements Automatically grows and shrinks
and null values without as elements are added or
 
restrictions. removed, similar to ArrayList. Multi- Single-
threaded threaded
Stack

 What is Stack?  Stack-Specific Methods

A subclass of Vector that follows the Last In, First Out (LIFO)
rule—the last element added is the first one removed. Like
Vector, it is synchronized, making it safe for multithreaded
Item 3 TOP
programs.

Item 2

 LIFO Principle  Thread-Safe

Item 1
Last element added is the first one Synchronized operations make it
removed, like a stack of plates. safe for multithreaded
environments.

push() pop()
+ Add to top
 Remove from top

 Performance  Inheritance
Slower than alternatives in single- Extends Vector class, inheriting all peek() empty()
 View top without removing
? Check if stack is empty
threaded cases due to its properties and methods.
synchronization overhead.
Set Interface Overview

 What is a Set?  Common Implementations

A Collection that cannot contain duplicate elements. It models
the mathematical set abstraction—meaning each element is HashSet

unique. Fast, no order guarantee. Uses hashing for very fast
operations.
 Average O(1) time complexity
 No guaranteed iteration order
No Duplicates  Allows one null value

 Each element must be unique. If you try to add a duplicate, it will be

ignored.
LinkedHashSet

Maintains insertion order. Combines HashSet speed with
Order Varies by Implementation
ordering.
 Different Set implementations handle ordering differently: unordered,
 Preserves insertion order
insertion order, or sorted order.
 Slightly slower than HashSet
 Allows one null value

Performance Trade-offs
 Each implementation offers different performance characteristics for
TreeSet
add, remove, and contains operations. 
Sorted in natural order. Uses Red-Black Tree for
automatic sorting.
 Elements always sorted
 O(log n) time complexity
 Does not allow null values
HashSet

 What is HashSet?  How It Works Internally

A collection that stores unique elements only and does not
maintain insertion order. It is backed by a HashMap internally
and uses hashing to store elements for fast retrieval.
Bucket 0 Bucket 1 Bucket 2 Bucket 3

B
 No Duplicates  Unordered A D
C
If you try to add a duplicate, it is The order of elements is not
ignored. Each element must be guaranteed to be the same as
unique. insertion order.

# Compute hashCode()  Determine bucket

 One Null Allowed  Efficient Operations = Check with .equals()  Handle collisions
Only a single null element can be Average O(1) time complexity for
stored in a HashSet. add, remove, and contains
operations.
LinkedHashSet

 What is LinkedHashSet?  Visual Representation

Similar to HashSet but maintains insertion order. Allows only
unique elements with order preserved exactly as inserted.

A B C D
 Maintains Order  Unique Elements
Elements are stored in the exact Like all Set implementations, it First Second Third Fourth
order they were added, unlike does not allow duplicate values.
HashSet which is unordered.
 HashSet  LinkedHashSet
Unordered, slightly faster Ordered, maintains insertion
sequence

 Fast Operations  Internal Structure

 Predictable iteration  Fast lookups  No duplicates
Provides fast operations similar to Uses a combination of hash table
HashSet, though slightly slower and linked list to maintain both  One null allowed
due to maintaining order. uniqueness and order.
TreeSet

 What is TreeSet?  Red-Black Tree Structure

A collection that stores unique elements in a sorted order. It
implements the SortedSet interface and uses a Red-Black Tree
internally to maintain order. C

 Unique Elements Only  Automatic Sorting A E

Duplicate values are ignored, Elements are stored in ascending
ensuring all elements in the set order by default (natural ordering).
are unique.
B D F

Balanced Binary Search Tree

 Red-Black Tree  Performance
Uses a self-balancing Red-Black Slower than HashSet because
 No null values  Always sorted  Self-balancing
Tree for efficient search, insert, operations require O(log n) time
and delete operations. instead of O(1).  Efficient search
Map Interface Overview

 What is a Map?  Main Implementations

A Map maps keys to values. No duplicate keys are allowed;
each key maps to at most one value. Values can be duplicated. HashMap

Fast, no order guarantee. Uses hashing for very fast
lookups and insertions.
 Allows one null key and multiple null values
Unique Keys  Average O(1) time complexity
 Each key must be unique within the map. If you add a duplicate key,
the old value is replaced.

TreeMap

Duplicate Values Allowed Sorted by key. Stores key-value pairs in a red-black tree.
 Multiple keys can map to the same value without restriction.  Keys sorted in ascending order
 Does not allow null keys

Efficient Lookups
 Designed for fast retrieval of values based on their keys. LinkedHashMap

Maintains insertion order. Stores key-value pairs in the
order they were added.
Key1 → ValueA Key2 → ValueB Key3 → ValueA  Preserves insertion order
 Allows one null key and multiple null values
HashMap

 What is HashMap?  Internal Structure

Bucket 0 Bucket 1 Bucket 2
Stores key-value pairs with no guaranteed order. Uses hashing
for very fast lookups and insertions. Elements are stored based
101 → "Chaitanya"105 → "Derick" 120 → "Paul"
on hash codes of keys, making retrieval by key extremely
efficient. 111 → "Logan"

 Fast Operations  No Order Guarantee

+ put(key, value)  get(key)  remove(key)
Average O(1) time complexity for Order of iteration may vary and is
get, put, and remove operations not guaranteed to remain constant  containsKey(key)
due to hashing mechanism. over time.

Possible Output (order may vary):

Key: 105 | Value: Derick
 Null Handling  Unique Keys
Key: 101 | Value: Chaitanya
Allows one null key and multiple Each key must be unique. If a
Key: 120 | Value: Paul
null values without restrictions. duplicate key is added, the old
Key: 111 | Value: Logan
value is replaced.
TreeMap

 What is TreeMap?  Red-Black Tree Structure

Stores key-value pairs in a red-black tree. Keys are sorted in
ascending order (natural ordering or custom Comparator). 105

 Sorted Keys  Performance 101 120

Keys are maintained in sorted Slower than HashMap due to
order, either by natural ordering or sorting overhead. Operations take
a custom Comparator. O(log n) time.
111

Balanced Binary Search Tree

Output (sorted by key):

 No Null Keys  Red-Black Tree Key: 101 | Value: Chaitanya
Does not allow null keys, though Uses a self-balancing binary
Key: 105 | Value: Derick
null values are permitted. search tree to maintain sorted
Key: 111 | Value: Logan
order efficiently.
Key: 120 | Value: Paul

 firstKey()  lastKey()  subMap()  headMap()

 tailMap()
LinkedHashMap

 What is LinkedHashMap?  Visual Representation

Stores key-value pairs in insertion order. Slightly slower than
100 120 105
HashMap but preserves order. Maintains a doubly-linked list of
Chaitanya Paul Derick
entries in addition to the hash table.
First Second Third
111
Logan
 Maintains Order  Performance
Fourth
Elements are stored in the exact Slightly slower than HashMap due
order they were added, unlike to maintaining the linked list, but
HashMap which is unordered. still provides fast lookups. Output (in insertion order):
Key: 100 | Value: Chaitanya
Key: 120 | Value: Paul
Key: 105 | Value: Derick
 Null Handling  Internal Structure Key: 111 | Value: Logan
Allows one null key and multiple Combines a hash table with a
null values, similar to HashMap. doubly-linked list to maintain both
fast access and insertion order.  Predictable iteration  Fast lookups  Insertion order

 One null key

Queue Interface

What is a Queue? Visual Representation

A linear data structure that follows the First-In-First-Out (FIFO)
principle—the first element added is the first one removed. Think
of it like a line at a ticket counter.
A B C D → E

Enqueue Dequeue FRONT REAR

Add element at the rear of the Remove element from the front of
queue. New elements join at the the queue. The first element in LinkedList PriorityQueue
end of the line. line is processed first. Simple FIFO implementation. Elements ordered by priority
Preserves strict insertion instead of insertion time.
order.

Peek / Front Use Cases

FIFO order Not synchronized Allows duplicates
View the front element without Useful for scheduling, buffering, or
removing it. Check who's next in task processing where order
ConcurrentLinkedQueue for threads
line. matters.
Summary Table

Key
Data
Common Java Order Allows Thread- Features /
Section Structure
Implementations Maintained Duplicates Safe Best Use
Type
Case

List Ordered ArrayList  Yes (insertion  Yes  Vector  Ideal when

collection of order) & Stack you need
elements, LinkedList Vector only ordered
supports
indexed Stack data and
access may allow
duplicates
 ArrayList for
quick
lookups,
LinkedList
for frequent
insert/delete

Set Collection of unique HashSet HashSet:   No  No  Best when you

elements (no LinkedHashSet: need
duplicates) LinkedHashSet  uniqueness
TreeSet: 
TreeSet  HashSet for
speed,
LinkedHashSet
when order
matters

Map Key-value pairs, HashMap HashMap:  Keys:   No  Ideal for

unique keys, values LinkedHashMap: Values: lookups by key
can repeat LinkedHashMap  
 HashMap for
TreeMap: 
TreeMap speed,
LinkedHashMap
to preserve
order
 Key
Data
Common Java Order Allows Thread- Features /
Section Structure
Implementations Maintained Duplicates Safe Best Use
Type
Case

Queue FIFO (First-In-First- LinkedList  Yes (FIFO)  Yes  No  Perfect for

Out) structure scheduling,
PriorityQueue buffering, or
task queues
 LinkedList
preserves strict
FIFO,
PriorityQueue
for priority
References


Java Collections: HashMap, HashSet, TreeSet and More
1
Neesri
Medium

 View Article

Java Collections tutorials

2
Singh, C.
BeginnersBook [Tutorial series]

 View Tutorials