Original Study Notes: Data Structures in Java

A ten section beginner to intermediate guide for arrays, linked structures, hashing, trees, graphs, and
algorithmic thinking.

Document purpose A concise original guide written for study, revision, and practical reference.

Content policy The material is newly written explanatory content, not copied from textbooks,
websites, or articles.

Structure Ten focused sections with concepts, checklists, common mistakes, and short
practice tasks.

How to use this PDF

Read one section at a time, write the mini exercise in your own words, and convert each checklist into a
small action item. The document is deliberately practical, so it can be used as a quick revision file or as a
starter reference for a project notebook.

Original Study Notes: Data Structures in Java Page 1

 1. Arrays and Index Based Thinking
An array is a fixed order collection where position matters. It is useful when direct access is more
important than frequent insertion in the middle. A useful study note should connect the definition to the
reason it exists. This section frames the idea in simple language first, then links it with design choices,
code habits, and revision questions that a student can actually use.

In Java, begin by deciding what each index represents and whether the valid range is inclusive or
exclusive. Clear index meaning reduces off by one errors. Treat the topic as a working tool rather than a
line to memorize. When you revise, write a two line summary, draw a tiny example, and test the idea on a
small case before you move to a larger problem.

The common trap is treating the length as the last index. The last index is length minus one, and loops
must be written with that distinction in mind. Most errors come from assumptions that were never
checked. Look for boundary cases, missing constraints, vague names, and situations where a solution
works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Use arrays when size is known or when contiguous indexing is the simplest model.
- Prefer for loops when the index itself has meaning.
- Track empty input before accessing arr[0].
- Use helper functions for repeated scanning logic.
- When sorting is allowed, mention the changed complexity.
- Write one dry run for the smallest possible array.

Mini exercise

Create an integer array of five marks, find the maximum, and write the exact loop invariant in one
sentence.

Original Study Notes: Data Structures in Java Page 2

 2. Linked Lists and Node Movement
A linked list stores values in nodes, where each node points to the next node. It supports flexible growth
but loses constant time random access. A useful study note should connect the definition to the reason it
exists. This section frames the idea in simple language first, then links it with design choices, code habits,
and revision questions that a student can actually use.

Practice pointer movement slowly. Even in Java, references behave like links, so a temporary variable
can be the difference between a correct update and a lost chain. Treat the topic as a working tool rather
than a line to memorize. When you revise, write a two line summary, draw a tiny example, and test the
idea on a small case before you move to a larger problem.

The common mistake is changing next pointers before saving the remaining list. In reversal and deletion
problems, the update order must be planned first. Most errors come from assumptions that were never
checked. Look for boundary cases, missing constraints, vague names, and situations where a solution
works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Name references by role: prev, curr, next, slow, fast.

- Handle deletion at the head separately or use a dummy node.
- Draw three nodes for reversal problems.
- Avoid nested traversal unless the complexity is acceptable.
- Check null before [Link] access.
- Return the new head after structural changes.

Mini exercise

Write the reference changes needed to reverse three nodes A -> B -> C without using code.

Original Study Notes: Data Structures in Java Page 3

 3. Stacks, Queues, and Order Control
Stacks and queues solve problems where the order of processing is the key idea. A stack follows last in
first out, while a queue follows first in first out. A useful study note should connect the definition to the
reason it exists. This section frames the idea in simple language first, then links it with design choices,
code habits, and revision questions that a student can actually use.

Use a stack for nested structure, undo behavior, monotonic patterns, and expression validation. Use a
queue for breadth first search, level order processing, and fair scheduling. Treat the topic as a working
tool rather than a line to memorize. When you revise, write a two line summary, draw a tiny example, and
test the idea on a small case before you move to a larger problem.

A frequent issue is choosing the structure after seeing the code instead of after understanding the
process order. The data structure should match the order rule. Most errors come from assumptions that
were never checked. Look for boundary cases, missing constraints, vague names, and situations where a
solution works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Use ArrayDeque in Java for stack and queue operations.

- Avoid legacy Stack unless specifically required.
- For BFS, mark nodes when they enter the queue.
- For parentheses, compare expected closing symbols.
- For monotonic stack, state increasing or decreasing clearly.
- Check underflow before pop or remove.

Mini exercise

Given the expression {[()]}, describe the stack contents after reading each character.

Original Study Notes: Data Structures in Java Page 4

 4. Hashing and Frequency Maps
Hashing converts lookup into an average constant time operation. It is especially useful when the
question asks whether something has appeared before. A useful study note should connect the definition
to the reason it exists. This section frames the idea in simple language first, then links it with design
choices, code habits, and revision questions that a student can actually use.

In Java, HashMap and HashSet are standard tools for frequency counting, duplicate detection, and two
sum style searches. The key design matters more than the syntax. Treat the topic as a working tool rather
than a line to memorize. When you revise, write a two line summary, draw a tiny example, and test the
idea on a small case before you move to a larger problem.

The main caution is that average constant time is not the same as ordered behavior. If order is required,
choose LinkedHashMap, TreeMap, or store the order separately. Most errors come from assumptions
that were never checked. Look for boundary cases, missing constraints, vague names, and situations
where a solution works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Use containsKey before reading a missing value.

- Use getOrDefault for frequency counts.
- Use HashSet when values only need membership.
- Use [Link] for clean iteration.
- Consider composite keys carefully.
- Mention expected O(1), not guaranteed O(1).

Mini exercise

Count character frequencies in the word banana and state which data structure you would use.

Original Study Notes: Data Structures in Java Page 5

 5. Trees and Recursive Structure
A tree is a hierarchical structure where each node can lead to smaller subtrees. Binary trees are natural
examples of recursive thinking. A useful study note should connect the definition to the reason it exists.
This section frames the idea in simple language first, then links it with design choices, code habits, and
revision questions that a student can actually use.

Practice traversal by writing the visit order first. Preorder visits root before children, inorder places root
between subtrees, and postorder visits root after children. Treat the topic as a working tool rather than a
line to memorize. When you revise, write a two line summary, draw a tiny example, and test the idea on a
small case before you move to a larger problem.

A common error is mixing the traversal order with the storage order. The tree shape decides traversal
output; the array representation is only one possible implementation. Most errors come from assumptions
that were never checked. Look for boundary cases, missing constraints, vague names, and situations
where a solution works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Identify base case before recursive calls.

- Return useful information from each subtree.
- Use queues for level order traversal.
- For BST, use ordering constraints, not only local child checks.
- Track height and balance separately.
- Dry run on a tree with one node.

Mini exercise

Draw a three level binary tree and list preorder, inorder, postorder, and level order traversals.

Original Study Notes: Data Structures in Java Page 6

 6. Heaps and Priority Based Processing
A heap is useful when the next item must always be the smallest or largest according to a priority. Java
PriorityQueue gives a min heap by default. A useful study note should connect the definition to the reason
it exists. This section frames the idea in simple language first, then links it with design choices, code
habits, and revision questions that a student can actually use.

Practice by converting the problem statement into a comparator. Once priority is clear, operations like add
and poll become predictable. Treat the topic as a working tool rather than a line to memorize. When you
revise, write a two line summary, draw a tiny example, and test the idea on a small case before you move
to a larger problem.

The common mistake is expecting a priority queue to remain fully sorted when printed or iterated. Only
the next polled element is guaranteed by priority. Most errors come from assumptions that were never
checked. Look for boundary cases, missing constraints, vague names, and situations where a solution
works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Use PriorityQueue for min priority behavior.

- Use a custom comparator for objects.
- For max behavior, reverse the comparator.
- Remember poll changes the heap.
- Use heaps for top K, scheduling, and merging sorted lists.
- State O(log n) for insert and remove.

Mini exercise

Explain how you would use a heap to find the three smallest numbers from a stream.

Original Study Notes: Data Structures in Java Page 7

 7. Graphs and Relationship Modeling
A graph models entities and relationships. Vertices represent items, and edges represent connections
that may be directed, undirected, weighted, or unweighted. A useful study note should connect the
definition to the reason it exists. This section frames the idea in simple language first, then links it with
design choices, code habits, and revision questions that a student can actually use.

Represent small graphs with an adjacency matrix when lookup is central. Represent sparse graphs with
adjacency lists when traversal and memory efficiency matter. Treat the topic as a working tool rather than
a line to memorize. When you revise, write a two line summary, draw a tiny example, and test the idea on
a small case before you move to a larger problem.

The main mistake is forgetting visited tracking. Without it, cycles can cause repeated processing or infinite
recursion. Most errors come from assumptions that were never checked. Look for boundary cases,
missing constraints, vague names, and situations where a solution works on the sample input but fails
when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Choose adjacency list for most coding problems.

- Use BFS for shortest path in unweighted graphs.
- Use DFS for component exploration.
- Use Dijkstra only when edge weights are non negative.
- Track parent when reconstructing paths.
- Decide if edges are directed before coding.

Mini exercise

Model four classrooms connected by corridors as a graph and write the adjacency list.

Original Study Notes: Data Structures in Java Page 8

 8. Greedy Methods and Dynamic Programming
Greedy algorithms make the locally best choice, while dynamic programming stores results of overlapping
subproblems. The difference is about proof, not just code shape. A useful study note should connect the
definition to the reason it exists. This section frames the idea in simple language first, then links it with
design choices, code habits, and revision questions that a student can actually use.

For greedy, search for an exchange argument. For dynamic programming, define the state, transition,
base case, and final answer before writing loops. Treat the topic as a working tool rather than a line to
memorize. When you revise, write a two line summary, draw a tiny example, and test the idea on a small
case before you move to a larger problem.

A common problem is using dynamic programming without knowing what the cell means. If dp[i] has no
clear sentence definition, the code becomes guesswork. Most errors come from assumptions that were
never checked. Look for boundary cases, missing constraints, vague names, and situations where a
solution works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Write the state meaning in plain English.

- Check whether choices overlap.
- Use memoization first when recursion is natural.
- Use tabulation when iteration order is clear.
- For greedy, justify why earlier choices remain safe.
- Test with a counterexample before finalizing.

Mini exercise

For climbing stairs with one or two steps at a time, define dp[i] and write the recurrence in words.

Original Study Notes: Data Structures in Java Page 9

 9. Complexity Analysis
Complexity describes how resource use grows as input size grows. It is a language for comparing
approaches without depending on a specific laptop or compiler. A useful study note should connect the
definition to the reason it exists. This section frames the idea in simple language first, then links it with
design choices, code habits, and revision questions that a student can actually use.

Practice by counting dominant operations. Nested loops often suggest quadratic time, but the actual
count depends on how the loop ranges change. Treat the topic as a working tool rather than a line to
memorize. When you revise, write a two line summary, draw a tiny example, and test the idea on a small
case before you move to a larger problem.

The usual mistake is including constants or ignoring data structure costs. A clean answer mentions the
main operation, time complexity, and auxiliary space. Most errors come from assumptions that were
never checked. Look for boundary cases, missing constraints, vague names, and situations where a
solution works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Define n before giving Big O.

- Mention sorting cost separately.
- For hash maps, say average case when appropriate.
- Separate input space from auxiliary space.
- Use worst case unless the question asks otherwise.
- Compare brute force and optimized approach.

Mini exercise

Analyze the time complexity of checking all pairs in an array and explain why it is O(n squared).

Original Study Notes: Data Structures in Java Page 10

 10. Debugging DSA Solutions
Debugging is not random trial and error. It is a controlled process of checking assumptions, shrinking the
input, and verifying each variable role. A useful study note should connect the definition to the reason it
exists. This section frames the idea in simple language first, then links it with design choices, code habits,
and revision questions that a student can actually use.

For Java solutions, print small traces only when needed, then remove them. Better still, use a dry run
table with columns for index, value, condition, and answer. Treat the topic as a working tool rather than a
line to memorize. When you revise, write a two line summary, draw a tiny example, and test the idea on a
small case before you move to a larger problem.

The danger is changing code before identifying the failure point. That can replace one bug with another
and make the solution harder to reason about. Most errors come from assumptions that were never
checked. Look for boundary cases, missing constraints, vague names, and situations where a solution
works on the sample input but fails when the data becomes larger or messier.

A practical way to retain the section is to explain it once without notes, then turn that explanation into a
checklist. The checklist should be short enough to follow during debugging, but specific enough to prevent
repeated mistakes.

Checklist

- Start with the smallest failing input.

- Check empty, one element, and duplicate cases.
- Verify loop boundaries.
- Read error messages before editing.
- Keep variable names meaningful.
- After fixing, rerun all earlier tests.

Mini exercise

Take any wrong solution from a practice problem and write a three row dry run table for it.

Original Study Notes: Data Structures in Java Page 11