Data Structure and Algorithm Notes

Pointers and Dynamic Memory Allocation

Dynamic memory allocation allows programs to request memory during runtime.
Common functions in C/C++: malloc() (memory allocation) and free() (deallocating memory).

Arrays in Java

An array is a collection of homogeneous data elements stored in contiguous memory locations.
- Key Characteristics of Arrays:
- Ordered: Elements maintain a fixed order.
- Fixed Length: Size is predefined and cannot be changed after initial creation.
- Homogeneous: All elements must be of the same data type.
- Important Terms:
- Elements: Individual values stored in an array.
- Length: Total number of elements an array can hold.
- Indexing: Each element is referenced by a position number (index), starting from 0.
- Declaration Syntax:
  $type[] identifier = new type[length];$
- Example of an array declaration:
  Student[] topStudents = new Student[3];

Dynamic Memory Allocation in Java

Java handles memory differently than C/C++. It does not have explicit pointers.
Objects are created on the heap using the new keyword.
Memory is automatically managed by Java's Garbage Collector (GC); developers do not have to manually free memory.

Array of Objects

In Java, arrays can store objects, treating each element as a reference to an instance of a class.
Example of initializing an array of Student objects:
java Student[] topStudents = new Student[3]; topStudents[0] = new Student("Alice", 20); topStudents[1] = new Student("Bob", 21); topStudents[2] = new Student("Charlie", 19);
Before initialization, the array elements are set to null.

Memory Representation of Arrays

Arrays maintain references in memory.
Internally, the memory representation of an array will utilize contiguous blocks for storing data.

Two-Dimensional Arrays

A 2D array can be conceptualized as an array of arrays, often visualized as a matrix.
Declaration and initialization of a matrix:
java int[][] matrix = new int[3][3];
To initialize with user input, you would iterate through the array and fill in values.

Using Java's ArrayList Class

ArrayLists allow dynamic sizing, automatically resizing when elements are added or removed.

Built-in methods include:

add(T element): Adds an element.

remove(int index): Removes an element at the specified index.

get(int index): Retrieves an element by its index.

Differences between Arrays and ArrayLists:

Feature	Array	ArrayList
Size	Fixed	Dynamic
Data Type	Primitive & Objects	Objects only
Methods	Manual operations	Built-in methods
Memory Allocation	Pre-allocated	Auto-resizes
Indexing

Arrays in Java utilize zero-based indexing.
To implement user-friendly one-based indexing, either adjust the displayed values or create an array with an extra dummy element.
Swapping and Reversing Elements in Arrays

To swap elements:
`java private static void swapElements(int[] array, int p1, int p2) { int tmp = array[p1]; array[p1] = array[p2]; array[p2] = tmp; }`
To reverse elements:
`java private void reverseArray(int[] array) { for (int i = 0; i < array.length / 2; i++) { swapElements(array, i, array.length - i - 1); } }`

Basic Program Examples

Creating an Array of Students
java public class StudentDemo { static class Student { String name; int age; Student(String name, int age) { this.name = name; this.age = age; } void display() { System.out.println("Name: " + name + ", Age: " + age); } } public static void main(String[] args) { Student[] topStudents = new Student[3]; // Initialization logic here } }