Locked in the 1P03

What is an array?

A data structure that holds multiple elements of the same type, accessed by index.

Are array indices zero-based or one-based in Java?

Zero-based.

What does the length property of an array represent?

The total number of elements (not the highest index).

Can the size of an array be changed after initialization?

No, array size is fixed once created.

What happens when you access an invalid index?

IndexOutOfBoundsException.

What are right-sized and variable-sized arrays?

Right-sized: exact number of needed cells.
Variable-sized: larger array with some unused cells tracked by a separate size variable.

What types can arrays hold in Java?

Primitive types (int, double, etc.) or objects (String, Student, etc.).

How do you traverse an array safely?

Use a for loop with condition i < array.length.

What is a 2D array?

An array of arrays (table-like), accessed by two indices [row][col].

What does data.length return for a 2D array?

The number of rows.

What are row-major and column-major traversals?

Row-major: iterate through rows first, then columns.
Column-major: iterate through columns first, then rows.

Lecture 2

What is asymptotic complexity?

A theoretical measure of an algorithm’s efficiency as input size grows

What does Big-O represent?

The worst-case upper bound of an algorithm.

What does Big-Ω (Omega) represent?

The best-case lower bound.

What does Big-Θ (Theta) represent?

The average case or tight bound.

Why do we ignore constants in Big-O?

Because constants are insignificant as input size grows very large.

What is the mathematical definition of Big-O?

f(x) ≤ C·g(x) for x ≥ k, where C and k are constants.

What is the order of efficiency from fastest to slowest?

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

How do nested loops affect complexity?

Multiply their complexities (e.g., two O(n) loops = O(n²)).

How do sequential (non-nested) loops affect complexity?

Add their complexities, then keep the dominant term.

What is the Big-O of binary search?

O(log n).

What is a singly linked list?

A dynamic data structure made of nodes where each node points to the next.

What are the parts of a Node?

item (data) and next (reference to the next node).

What does the head variable represent?

The first node in the linked list.

What is the time complexity to access an element in a linked list?

O(n), because traversal starts from the head.

What does print() do?

Traverses the list and prints all items until null.

What is the time complexity of print()?

O(n).

What does insertAtFront() do?

Inserts a new node at the front (before the head).

What is the time complexity of insertAtFront()?

O(1).

What does removeAtFront() do?

Removes and returns the first node.

What is the time complexity of removeAtFront()?

O(1).

What does insertAtRearOnePointer() do?

Traverses to the last node and appends a new node at the end.

What is its time complexity?

O(n).

What does insertAtRearTwoPointers() do?

Uses two pointers (p, q) to reach the end before insertion.

What is sortedInsertion()?

Inserts a node while maintaining ascending order using two pointers.

Lecture 4

What is the purpose of sortedInsertion()?

Insert a node in its sorted position, maintaining list order.

What operator prevents NullPointerException in loops?

&& (logical AND short-circuit).

What does the remove() method do in a singly linked list?

Deletes a node by linking the previous node to the next one.

What is a tail reference?

A pointer to the last node, allowing O(1) insertion at the rear

What is a doubly linked list?

A structure where each node has a prev, item, and next, allowing bidirectional traversal.

What are the advantages of a doubly linked list?

Easier deletion and traversal in both directions.

What is the structure of a doubly linked list node?

prev, item, and next

How is sorted insertion done in a doubly linked list?

Create a new node between two existing ones and update both surrounding pointers.

What is the deletion rule in linked lists?

Nothing should point to the node being deleted — that’s when it’s garbage-collected.

What is a circular linked list?

A linked list where the last node’s next points back to the first node.

Lecture 5

What is an interface?

A blueprint for a class; defines methods (no code) and public instance variables.

What’s automatically true for interface variables?

They’re public static final (constants shared by all).

Can interfaces have private variables?

❌ No — only public variables.

How do you implement an interface?

Use implements, match all method headers exactly (same name, parameters, return type, and must be public).

What happens if you miss a method when implementing?

Compilation error.

Can a class have more methods than defined in the interface?

✅ Yes, extra methods are allowed.

What are the 4 types of Access Modifiers?

public, private, protected, and default (no keyword).

What’s an exception?

An event that disrupts normal program flow (error).

How to make a custom exception?

public class EmptyLinkedListException extends RuntimeException {}

How to throw an exception?

if (head == null) {

throw new EmptyLinkedListException();

}

How to catch an exception?

try {

// risky code

} catch (EmptyLinkedListException e) {

// handle error

}

Why catch exceptions?

Prevents program crash; lets you handle issues gracefully.