A dynamic array is unlike a regular array with a fixed size, can automatically resize itself when elements are added or removed. This allows for more flexible use, especially when the number of elements is not known in advance. Dynamic arrays are commonly implemented by allocating a larger array when needed and copying the elements from the old array to the new one.
Dynamic arrays have many key features that make them a popular choice among programmers. Some of the key features of dynamic arrays are:
- Dynamic Resizing: A dynamic array can automatically resize itself when its capacity is exceeded. Initially, a dynamic array starts with a small capacity, but as more elements are added, the array grows, typically by doubling its size. This allows it to accommodate more elements efficiently.
- Efficient Element Access: Dynamic arrays provide constant-time access to elements via indices. You can access any element in the array in \(O(1)\) time using its index, just like a regular array.
- Flexible Size: Unlike fixed-size arrays, which have a predetermined capacity, a dynamic array can grow or shrink based on the number of elements it holds.
- Amortized Constant-Time Append: Adding an element at the end of a dynamic array is efficient and usually takes \(O(1)\) time. When the array reaches its capacity, the array is resized (which takes \(O(n)\) time for the copy operation), but this happens infrequently. Therefore, the average time complexity for appending an element is amortized \(O(1)\).
- Efficient Memory Management: Dynamic arrays allocate memory only when needed. Although resizing (doubling the size of the array) may lead to some temporarily unused memory (as the array can grow to be larger than the number of elements), this approach minimizes memory reallocations and ensures that elements are stored contiguously in memory.
- Index-Based Insertions and Deletions: Inserting or deleting elements at specific indices can be done in a dynamic array, but these operations require shifting elements, making them \(O(n)\) in the worst case. Inserting at the end (append) is faster, while inserting or deleting in the middle requires moving elements to maintain the order.
- Contiguous Memory Allocation: Like regular arrays, elements in a dynamic array are stored in a contiguous block of memory. This provides cache-friendly access to data, improving performance when iterating over the elements.
The following are some common operations implemented on the dynamic array:
add():
- Description: Adds an element to the end of the array. If the current size equals the capacity, the array is resized (usually doubled), and the element is added.
- Time complexity:
- If the dynamic array has enough capacity to accommodate the new element, adding the element is a simple operation, requiring constant time i.e. \(O(1)\) to place the new element at the end of the array.
- If the dynamic array is full, a new larger array must be allocated (typically twice the current size), and all the existing elements must be copied to the new array. This resizing operation takes linear time (\(O(n)\), where \(n\) is the number of elements in the array).
- Space complexity:
- If the dynamic array has enough capacity to accommodate the new element, no additional space is needed. This operation takes constant space i.e. \(O(1)\).
- If the dynamic array is full, a new larger array must be allocated (typically twice the current size), and all the existing elements must be copied to the new array. The new array requires \(O(n)\) space (where \(n\) is the current number of elements).
get():
- Description: Retrieves an element at a specified index. Returns the element at the given index without modifying the array.
- Time complexity: Accessing an element in a dynamic array is straightforward since arrays allow random access. This means that you can directly access any element by its index in constant time i.e. \(O(1)\).
- Space complexity: Accessing an element does not require any additional space apart from the memory already allocated for the array itself. Therefore this operation takes constant space i.e. \(O(1)\).
set():
- Description: Adds an element to the end of the array. If the current size equals the capacity, the array is resized (usually doubled), and the element is added.
- Time complexity: Setting an element at any index is a constant-time operation i.e. \(O(1)\) because it directly changes the value at the memory location corresponding to the index.
- Space complexity: No extra memory is allocated; you are just modifying the existing space. This operation takes constant space i.e. \(O(1)\).
remove():
- Description: Deletes an element from a specified index. Removes the element and shifts the subsequent elements to fill the gap.
- Time complexity:
- Removing the last element does not require shifting any elements. This is straightforward as it involves just updating the size of the array by decreasing it by 1. This operation takes constatnt time (\(O(1)\).
- Removing an element from any other position requires shifting all elements to the left to fill the gap left by the removed element. Every element after the removed element needs to be shifted one position to the left, resulting in a linear time complexity in the worst case. This operation requires linear time i.e. \(O(n)\) (where \(n\) is the number of elements after the removed element)
- Space complexity: No additional space is required to remove an element from the array, as you are modifying the existing array structure. This operation takes constant space i.e. \(O(1)\).
insert():
- Description: Inserts an element at a specified index. If the array is full, it resizes the array. The specified index is filled, and subsequent elements are shifted to the right.
- Time complexity:
- If the dynamic array has enough capacity to accommodate the new element, inserting to the end of the array without any additional operations. This operation requires constant time i.e. \(O(1)\) to place the new element at the end of the array.
- If the dynamic array is full, a new larger array must be allocated (typically twice the current size), and all the existing elements must be copied to the new array. This resizing operation takes linear time (\(O(n)\), where \(n\) is the number of elements in the array).
- When an element is inserted anywhere other than the end (e.g., in the middle), all subsequent elements need to be shifted one position to the right to make space for the new element. This shifting operation requires time proportional to the number of elements after the insertion point, resulting in a linear time complexity \(O(n)\).
- Space complexity:
- If the dynamic array has enough capacity to accommodate the new element, no additional space is needed. This operation takes constant space i.e. \(O(1)\).
- If the dynamic array is full, a new larger array must be allocated (typically twice the current size), and all the existing elements must be copied to the new array. The new array requires \(O(n)\) space (where \(n\) is the current number of elements).
size():
- Description: Returns the number of elements currently stored in the array. Simply returns the
sizeattribute. - Time complexity: Retrieving the size of a dynamic array is an \(O(1)\) operation because the size is typically stored as a separate variable (e.g., size or length). When you call the size method, it simply returns this value without needing to iterate over the array or perform any additional calculations.
- Space complexity: The operation does not require any additional space beyond what is already used to store the size variable.
- Description: Returns the number of elements currently stored in the array. Simply returns the
resize():
- Description: Changes the capacity of the array. Creates a new larger or smaller array and copies existing elements into it.
- Time complexity: The resize operation takes linear time because you need to copy all existing elements from the old array to the new one. If the current size of the array is \(n\), it will require \(n\) time to copy each element over. This operation takes linear time i.e. \(O(n)\).
- Space complexity: When you create a new array, it will require \(n\) space to hold the existing elements (where \(n\) is the number of elements in the current array). Additionally, the size of the new array is typically twice that of the old one, so the overall space allocation for the new array would also be proportional to \(n\). This operation takes linear time i.e. \(O(n)\).
clear():
- Description: Removes all elements from the array. Sets the size to zero, effectively clearing the contents, but the capacity may remain unchanged.
- Time complexity: The
clearoperation involves iterating through all elements to free up any dynamically allocated resources or simply resetting references, it takes linear time \(O(n)\), where \(n\) is the current number of elements in the array. - Space complexity: The
clearoperation does not allocate any new space or increase the overall memory usage. This operation takes constant space i.e. \(O(1)\).
display():
- Description: Displays all elements in the array. Iterates through the array and prints each element.
- Time complexity: The display operation involves iterating through all elements of the dynamic array from index
0tosize - 1to print each element. The time complexity of this operation is \(O(n)\), where \(n\) is the number of elements in the dynamic array. - Space complexity: The display operation does not require any additional memory proportional to the number of elements, except for a fixed amount of space used for variables like the loop counter. Therefore, the space complexity is \(O(1)\).
In C, there is no built-in dynamic array like in languages such as C++, Java or C#.
In C++, the built-in dynamic array is provided by the std::vector class, which is part of the Standard Template Library (STL). Vectors in C++ provide a dynamic array implementation that automatically resizes as elements are added or removed.
#include <iostream>
#include <vector>
int main() {
// Create a vector of integers
std::vector<int> dynamicArray;
// Add elements to the vector using push_back()
dynamicArray.push_back(10);
dynamicArray.push_back(20);
dynamicArray.push_back(30);
dynamicArray.push_back(40);
// Access elements using the [] operator or at() method
std::cout << "Element at index 2: " << dynamicArray[2] << std::endl;
// Modify an element
dynamicArray[2] = 50;
std::cout << "Array after modification: ";
for (int i = 0; i < dynamicArray.size(); i++) {
std::cout << dynamicArray[i] << " ";
}
std::cout << std::endl;
// Remove the last element using pop_back()
dynamicArray.pop_back();
std::cout << "Array after removing the last element: ";
for (int i = 0; i < dynamicArray.size(); i++) {
std::cout << dynamicArray[i] << " ";
}
std::cout << std::endl;
// Resize the vector to size 5, new elements initialized to 0
dynamicArray.resize(5);
std::cout << "After resizing to larger size: ";
for (int i = 0; i < dynamicArray.size(); i++) {
std::cout << dynamicArray[i] << " ";
}
std::cout << std::endl;
// Resize the vector to size 3, excess elements are truncated
dynamicArray.resize(3);
std::cout << "After resizing to smaller size: ";
for (int i = 0; i < dynamicArray.size(); i++) {
std::cout << dynamicArray[i] << " ";
}
std::cout << std::endl;
// Clear all elements from the vector
dynamicArray.clear();
std::cout << "Vector size after clear: " << vec.size() << std::endl;
return 0;
}In Java, the built-in dynamic array is represented by the ArrayList class, which is part of the Java Collections Framework.
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1); // Adds 1 to the list
arrayList.add(2); // Adds 2 to the list
arrayList.add(3); // Adds 3 to the list
arrayList.add(4); // Adds 4 to the list
System.out.println("ArrayList: " + arrayList);
System.out.println("Element at index 1: " + arrayList.get(1));
arrayList.set(1, 10); // Updates the element at index 1 to 10
System.out.println("Updated ArrayList: " + arrayList);
arrayList.remove(1); // Removes the element at index 1
System.out.println("ArrayList after removal: " + arrayList);
System.out.println("Size of ArrayList: " + arrayList.size());
arrayList.clear(); // Clears all elements from the list
System.out.println("ArrayList after clear: " + arrayList);
}
}In C#, the built-in dynamic array is represented by the List<T> class from the System.Collections.Generic namespace. The List<T> is similar to an array but with the ability to automatically resize itself when more elements are added, much like dynamic arrays in other languages such as Java's ArrayList.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Creating a List of integers with initial capacity
List<int> numbers = new List<int>();
// Adding elements to the List
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);
numbers.Add(4);
// Accessing elements by index
Console.WriteLine("Element at index 2: " + numbers[2]);
// Modifying an element
numbers[2] = 10;
Console.WriteLine("After modification, element at index 2: " + numbers[2]);
// Iterating through the List
Console.WriteLine("Elements in List:");
foreach (int number in numbers)
{
Console.WriteLine(number);
}
// Checking the size of the List
Console.WriteLine("Size of List: " + numbers.Count);
// Removing an element
numbers.RemoveAt(2); // Remove element at index 2
Console.WriteLine("After removal, size of List: " + numbers.Count);
// Displaying the elements after removal
Console.WriteLine("Elements in List after removal:");
foreach (int number in numbers)
{
Console.WriteLine(number);
}
}
}Here is an implementation of a simple dynamic array in C:
#include <stdio.h>
#include <stdlib.h>
struct DynamicArray {
int *array; // Array to hold elements
int capacity; // Capacity of the dynamic array
int size; // Current number of elements
};
// Initialize dynamic array
void init(struct DynamicArray *dArray, int capacity) {
dArray->array = (int *)malloc(capacity * sizeof(int));
dArray->capacity = capacity;
dArray->size = 0;
}
// Resize the dynamic array
void resize(struct DynamicArray *dArray) {
int newCapacity = dArray->capacity * 2;
dArray->array = (int *)realloc(dArray->array, newCapacity * sizeof(int));
dArray->capacity = newCapacity;
}
// Add an element to the end
void add(struct DynamicArray *dArray, int element) {
if (dArray->size == dArray->capacity) {
resize(dArray);
}
dArray->array[dArray->size++] = element;
}
// Get an element by index
int get(struct DynamicArray *dArray, int index) {
if (index < 0 || index >= dArray->size) {
printf("Index out of bounds\n");
return -1;
}
return dArray->array[index];
}
// Set (update) an element at a specific index
void set(struct DynamicArray *dArray, int index, int element) {
if (index < 0 || index >= dArray->size) {
printf("Index out of bounds\n");
return;
}
dArray->array[index] = element;
}
// Remove an element by index
void remove(struct DynamicArray *dArray, int index) {
if (index < 0 || index >= dArray->size) {
printf("Index out of bounds\n");
return;
}
for (int i = index; i < dArray->size - 1; i++) {
dArray->array[i] = dArray->array[i + 1];
}
dArray->size--;
}
// Insert an element at a specific index
void insert(struct DynamicArray *dArray, int index, int element) {
if (index < 0 || index > dArray->size) {
printf("Index out of bounds\n");
return;
}
if (dArray->size == dArray->capacity) {
resize(dArray);
}
for (int i = dArray->size; i > index; i--) {
dArray->array[i] = dArray->array[i - 1];
}
dArray->array[index] = element;
dArray->size++;
}
// Return the size of the array
int size(struct DynamicArray *dArray) {
return dArray->size;
}
// Clear the array
void clear(struct DynamicArray *dArray) {
dArray->size = 0;
}
// Display the array
void display(struct DynamicArray *dArray) {
if (dArray->size == 0) {
printf("Array is empty\n");
} else {
for (int i = 0; i < dArray->size; i++) {
printf("%d ", dArray->array[i]);
}
printf("\n");
}
}
// Free the memory allocated to the array
void deallocate(struct DynamicArray *dArray) {
free(dArray->array);
dArray->array = NULL;
dArray->capacity = dArray->size = 0;
}
int main() {
struct DynamicArray dArray;
initArray(&dArray, 2);
add(&dArray, 10);
add(&dArray, 20);
add(&dArray, 30);
display(&dArray); // Output: 10 20 30
printf("Element at index 1: %d\n", get(&dArray, 1)); // Output: 20
set(&dArray, 1, 25);
display(&dArray); // Output: 10 25 30
insert(&dArray, 1, 15);
display(&dArray); // Output: 10 15 25 30
remove(&dArray, 2);
display(&dArray); // Output: 10 15 30
printf("Size: %d\n", size(&dArray)); // Output: 3
clear(&dArray);
display(&dArray); // Output: Array is empty
deallocate(&dArray);
return 0;
}Here is an implementation of a generic dynamic array in C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Define a structure for StackElement
typedef struct {
void* data; // Generic pointer to hold data
char* toString; // String description of the element
} StackElement;
// Define a structure for the dynamic array of StackElements
typedef struct {
StackElement* array; // Array to store StackElements
int capacity; // Capacity of the array
int size; // Current number of elements
} DynamicArray;
// Function to initialize the dynamic array
void init(DynamicArray* arr, int initialCapacity) {
arr->capacity = initialCapacity;
arr->size = 0;
arr->array = (StackElement*)malloc(initialCapacity * sizeof(StackElement));
}
// Function to resize the dynamic array
void resize(DynamicArray* arr) {
arr->capacity *= 2;
StackElement* newArray = (StackElement*)malloc(arr->capacity * sizeof(StackElement));
// Copy elements from the old array to the new array
for (int i = 0; i < arr->size; i++) {
newArray[i] = arr->array[i];
}
free(arr->array); // Free the old array memory
arr->array = newArray;
}
// Function to add an element to the dynamic array
void add(DynamicArray* arr, void* data, const char* description) {
if (arr->size == arr->capacity) {
resize(arr);
}
arr->array[arr->size].data = data;
arr->array[arr->size].toString = strdup(description); // Duplicate the string description
arr->size++;
}
// Function to get an element at a specific index
StackElement* get(DynamicArray* arr, int index) {
if (index < 0 || index >= arr->size) {
printf("Index out of range\n");
return NULL;
}
return &arr->array[index];
}
// Function to set an element at a specific index
void set(DynamicArray* arr, int index, void* data, const char* description) {
if (index < 0 || index >= arr->size) {
printf("Index out of range\n");
return;
}
free(arr->array[index].data);
arr->array[index].data = data;
free(arr->array[index].toString); // Free the old string memory
arr->array[index].toString = strdup(description); // Duplicate the new string description
}
// Function to remove an element at a specific index
void remove(DynamicArray* arr, int index) {
if (index < 0 || index >= arr->size) {
printf("Index out of range\n");
return;
}
free(arr->array[index].toString); // Free the string memory
free(arr->array[index].data); // Free the Car instance memory
for (int i = index; i < arr->size - 1; i++) {
arr->array[i] = arr->array[i + 1];
}
arr->size--;
}
// Function to insert an element at a specific index
void insert(DynamicArray* arr, int index, void* data, const char* description) {
if (index < 0 || index > arr->size) {
printf("Index out of range\n");
return;
}
if (arr->size == arr->capacity) {
resize(arr);
}
for (int i = arr->size; i > index; i--) {
arr->array[i] = arr->array[i - 1];
}
arr->array[index].data = data;
arr->array[index].toString = strdup(description); // Duplicate the string description
arr->size++;
}
// Function to get the current size of the dynamic array
int size(DynamicArray* arr) {
return arr->size;
}
// Function to clear the dynamic array
void deallocate(DynamicArray* arr) {
for (int i = 0; i < arr->size; i++) {
free(arr->array[i].toString); // Free the string memory
free(arr->array[i].data); // Free the Car instance memory
}
arr->size = 0;
}
// Function to display the dynamic array
void display(DynamicArray* arr) {
for (int i = 0; i < arr->size; i++) {
printf("%s ", arr->array[i].toString);
}
}
// Function to free the dynamic array
void deallocate(DynamicArray* arr) {
for (int i = 0; i < arr->size; i++) {
free(arr->array[i].toString); // Free the string memory
free(arr->array[i].data); // Free the Car instance memory
}
free(arr->array); // Free the array memory
}
// A Car struct to demonstrate the use of StackElement in the dynamic array
typedef struct {
char model[50];
int year;
} Car;
// A function to create a string description for a Car
char* carToString(Car* car) {
char* result = (char*)malloc(100 * sizeof(char)); // Allocate memory for the string
sprintf(result, "Car{model:\"%s\",year:%d}", car->model, car->year);
return result;
}
// Main function for testing the implementation
int main() {
DynamicArray carArray;
// Initialize the dynamic array for StackElements
init(&carArray, 2);
// Create cars dynamically and add them to the array
Car* car1 = (Car*)malloc(sizeof(Car));
strcpy(car1->model, "Toyota Camry");
car1->year = 2020;
add(&carArray, car1, carToString(car1));
Car* car2 = (Car*)malloc(sizeof(Car));
strcpy(car2->model, "Honda Accord");
car2->year = 2019;
add(&carArray, car2, carToString(car2));
Car* car3 = (Car*)malloc(sizeof(Car));
strcpy(car3->model, "Tesla Model S");
car3->year = 2022;
add(&carArray, car3, carToString(car3));
// Display the car array
printf("Car Array:\n");
display(&carArray);
// Demonstrate using getElement, setElement, removeElement, and insertElement
printf("Size before modifications: %d\n", size(&carArray));
// Insert a new car
Car* car4 = (Car*)malloc(sizeof(Car));
strcpy(car4->model, "Ford Mustang");
car4->year = 2021;
insert(&carArray, 1, car4, carToString(car4)); // Insert at index 1
printf("Car Array after insertion:\n");
display(&carArray);
// Set a car at index 2
Car* car5 = (Car*)malloc(sizeof(Car));
strcpy(car5->model, "Chevrolet Camaro");
car5->year = 2023;
set(&carArray, 2, car5, carToString(car5)); // Set at index 2
printf("Car Array after setting new car at index 2:\n");
display(&carArray);
// Remove the first car
remove(&carArray, 0);
printf("Car Array after removing the first car:\n");
display(&carArray);
// Clean up
deallocate(&carArray);
return 0;
}Here is a custom implementation of a simple dynamic array in C++:
#include <iostream>
#include <stdexcept> // For exception handling
class DynamicArray {
private:
int* array;
int capacity;
int currentSize;
// Resize the array when it reaches capacity
void resize() {
capacity *= 2;
int* newArray = new int[capacity];
// Manually copy elements from the old array to the new array
for (int i = 0; i < currentSize; ++i) {
newArray[i] = array[i];
}
delete[] array; // Free the old array
array = newArray; // Assign the new array
}
public:
// Constructor to initialize the dynamic array with an initial capacity
DynamicArray(int initialCapacity = 2) {
capacity = initialCapacity;
array = new int[capacity];
currentSize = 0;
}
// Destructor to free allocated memory
~DynamicArray() {
delete[] array;
}
// Add an element to the array
void add(int element) {
if (currentSize == capacity) {
resize();
}
array[currentSize++] = element;
}
// Get an element at a specific index
int get(int index) const {
if (index < 0 || index >= currentSize) {
throw std::out_of_range("Index out of range");
}
return array[index];
}
// Set (update) an element at a specific index
void set(int index, int element) {
if (index < 0 || index >= currentSize) {
throw std::out_of_range("Index out of range");
}
array[index] = element;
}
// Remove an element at a specific index
void remove(int index) {
if (index < 0 || index >= currentSize) {
throw std::out_of_range("Index out of range");
}
for (int i = index; i < currentSize - 1; ++i) {
array[i] = array[i + 1];
}
--currentSize;
}
// Insert an element at a specific index
void insert(int index, int element) {
if (index < 0 || index > currentSize) {
throw std::out_of_range("Index out of range");
}
if (currentSize == capacity) {
resize();
}
for (int i = currentSize; i > index; --i) {
array[i] = array[i - 1];
}
array[index] = element;
++currentSize;
}
// Get the current size of the dynamic array
int size() const {
return currentSize;
}
// Clear the array
void clear() {
currentSize = 0;
std::cout << "Array cleared!" << std::endl;
}
// Display all elements in the dynamic array
void display() const {
if (currentSize == 0) {
std::cout << "Array is empty" << std::endl;
} else {
for (int i = 0; i < currentSize; ++i) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}
}
};
int main() {
DynamicArray dynamicArray;
// Adding elements
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
dynamicArray.add(4);
dynamicArray.display(); // Output: Array elements: 1 2 3 4
// Get element at index 2
std::cout << "Element at index 2: " << dynamicArray.get(2) << std::endl; // Output: 3
// Set element at index 1
dynamicArray.set(1, 20);
dynamicArray.display(); // Output: Array elements: 1 20 3 4
// Insert an element at index 2
dynamicArray.insert(2, 100);
dynamicArray.display(); // Output: Array elements: 1 20 100 3 4
// Remove an element at index 3
dynamicArray.remove(3);
dynamicArray.display(); // Output: Array elements: 1 20 100 4
// Get the current size of the array
std::cout << "Size: " << dynamicArray.size() << std::endl; // Output: Size: 4
// Clear the array
dynamicArray.clear();
dynamicArray.display(); // Output: Array is empty
return 0;
}Here is a custom implementation of a generic dynamic array in C++:
#include <iostream>
#include <stdexcept> // For exception handling
template <typename T>
class DynamicArray {
private:
T* array; // Pointer to hold the dynamic array
int capacity; // Capacity of the array
int currentSize; // Current number of elements in the array
// Resize the array when capacity is full
void resize() {
capacity *= 2;
T* newArray = new T[capacity]; // Allocate new array with double capacity
for (int i = 0; i < currentSize; ++i) {
newArray[i] = array[i]; // Copy elements from old array to new array
}
delete[] array; // Deallocate old array
array = newArray; // Point to the new array
}
public:
// Constructor to initialize dynamic array with an initial capacity
DynamicArray(int initialCapacity = 2) {
capacity = initialCapacity;
array = new T[capacity];
currentSize = 0;
}
// Destructor to clean up allocated memory
~DynamicArray() {
delete[] array;
}
// Add an element to the array
void add(const T& element) {
if (currentSize == capacity) {
resize();
}
array[currentSize++] = element;
}
// Get an element at a specific index
T get(int index) const {
if (index < 0 || index >= currentSize) {
throw std::out_of_range("Index out of range");
}
return array[index];
}
// Set (update) an element at a specific index
void set(int index, const T& element) {
if (index < 0 || index >= currentSize) {
throw std::out_of_range("Index out of range");
}
array[index] = element;
}
// Remove an element at a specific index
void remove(int index) {
if (index < 0 || index >= currentSize) {
throw std::out_of_range("Index out of range");
}
for (int i = index; i < currentSize - 1; ++i) {
array[i] = array[i + 1];
}
--currentSize;
}
// Insert an element at a specific index
void insert(int index, const T& element) {
if (index < 0 || index > currentSize) {
throw std::out_of_range("Index out of range");
}
if (currentSize == capacity) {
resize();
}
for (int i = currentSize; i > index; --i) {
array[i] = array[i - 1]; // Shift elements to the right
}
array[index] = element;
++currentSize;
}
// Get the current size of the array
int size() const {
return currentSize;
}
// Clear the array by resetting the size
void clear() {
currentSize = 0;
std::cout << "Array cleared!" << std::endl;
}
// Display all elements in the dynamic array
void display() const {
if (currentSize == 0) {
std::cout << "Array is empty" << std::endl;
} else {
for (int i = 0; i < currentSize; ++i) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}
}
};
// Test the DynamicArray class
int main() {
DynamicArray<int> dynamicArray;
// Adding elements
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
dynamicArray.add(4);
dynamicArray.display(); // Output: Array elements: 1 2 3 4
// Get element at index 2
std::cout << "Element at index 2: " << dynamicArray.get(2) << std::endl; // Output: 3
// Set element at index 1
dynamicArray.set(1, 20);
dynamicArray.display(); // Output: Array elements: 1 20 3 4
// Insert an element at index 2
dynamicArray.insert(2, 100);
dynamicArray.display(); // Output: Array elements: 1 20 100 3 4
// Remove an element at index 3
dynamicArray.remove(3);
dynamicArray.display(); // Output: Array elements: 1 20 100 4
// Get the current size of the array
std::cout << "Size: " << dynamicArray.size() << std::endl; // Output: Size: 4
// Clear the array
dynamicArray.clear();
dynamicArray.display(); // Output: Array is empty
return 0;
}Here is a custom implementation of a simple dynamic array in Java:
class DynamicArray {
private int[] array;
private int size;
private int capacity;
// Constructor to initialize array with a specified capacity
public DynamicArray(int initialCapacity) {
this.capacity = initialCapacity;
this.array = new int[capacity];
this.size = 0;
}
// Default constructor with an initial capacity of 2
public DynamicArray() {
this(2);
}
// Add an element to the dynamic array
public void add(int element) {
if (size == capacity) {
resize();
}
array[size++] = element;
}
// Get an element at a specific index
public int get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
return array[index];
}
// Set (update) an element at a specific index
public void set(int index, int element) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
array[index] = element;
}
// Remove an element at a specific index
public void remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
array[--size] = 0; // Clear last element
}
// Insert an element at a specific index
public void insert(int index, int element) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
if (size == capacity) {
resize();
}
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = element;
size++;
}
// Get the current size of the array
public int size() {
return size;
}
// Resize the array when capacity is reached
private void resize() {
capacity *= 2;
int[] newArray = new int[capacity];
// Manually copy elements from the old array to the new array
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
// Clear the array by setting the size to 0
public void clear() {
for (int i = 0; i < size; i++) {
array[i] = 0;
}
size = 0;
System.out.println("Array cleared!");
}
// Display all elements in the dynamic array
public void display() {
if (size == 0) {
System.out.println("Array is empty");
} else {
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
}
public class Main {
public static void main(String[] args) {
DynamicArray dynamicArray = new DynamicArray();
// Adding elements
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
dynamicArray.add(4);
dynamicArray.display(); // Output: Array elements: 1 2 3 4
// Get element at index 2
System.out.println("Element at index 2: " + dynamicArray.get(2)); // Output: 3
// Set element at index 1
dynamicArray.set(1, 20);
dynamicArray.display(); // Output: Array elements: 1 20 3 4
// Insert an element at index 2
dynamicArray.insert(2, 100);
dynamicArray.display(); // Output: Array elements: 1 20 100 3 4
// Remove an element at index 3
dynamicArray.remove(3);
dynamicArray.display(); // Output: Array elements: 1 20 100 4
// Get the current size of the array
System.out.println("Size: " + dynamicArray.size()); // Output: Size: 4
// Clear the array
dynamicArray.clear();
dynamicArray.display(); // Output: Array is empty
}
}Here is a custom implementation of a generic dynamic array in Java:
class DynamicArray<T> {
private Object[] array;
private int size;
private int capacity;
// Constructor to initialize array with a specified capacity
public DynamicArray(int initialCapacity) {
this.capacity = initialCapacity;
this.array = new Object[capacity];
this.size = 0;
}
// Default constructor with an initial capacity of 2
public DynamicArray() {
this(2);
}
// Add an element to the dynamic array
public void add(T element) {
if (size == capacity) {
resize();
}
array[size++] = element;
}
// Get an element at a specific index
public T get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
return (T) array[index];
}
// Set (update) an element at a specific index
public void set(int index, T element) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
array[index] = element;
}
// Remove an element at a specific index
public void remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
array[--size] = null; // Clear last element
}
// Insert an element at a specific index
public void insert(int index, T element) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
if (size == capacity) {
resize();
}
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = element;
size++;
}
// Get the current size of the array
public int size() {
return size;
}
// Resize the array when capacity is reached
private void resize() {
capacity *= 2;
Object[] newArray = new Object[capacity];
// Manually copy elements from the old array to the new array
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
// Clear the array by setting the size to 0
public void clear() {
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
System.out.println("Array cleared!");
}
// Display all elements in the dynamic array
public void display() {
if (size == 0) {
System.out.println("Array is empty");
} else {
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
}
public class Main {
public static void main(String[] args) {
DynamicArray<Integer> dynamicArray = new DynamicArray<>();
// Adding elements
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
dynamicArray.add(4);
dynamicArray.display(); // Output: Array elements: 1 2 3 4
// Get element at index 2
System.out.println("Element at index 2: " + dynamicArray.get(2)); // Output: 3
// Set element at index 1
dynamicArray.set(1, 20);
dynamicArray.display(); // Output: Array elements: 1 20 3 4
// Insert an element at index 2
dynamicArray.insert(2, 100);
dynamicArray.display(); // Output: Array elements: 1 20 100 3 4
// Remove an element at index 3
dynamicArray.remove(3);
dynamicArray.display(); // Output: Array elements: 1 20 100 4
// Get the current size of the array
System.out.println("Size: " + dynamicArray.size()); // Output: Size: 4
// Clear the array
dynamicArray.clear();
dynamicArray.display(); // Output: Array is empty
}
}Here is a custom implementation of a simple dynamic array in C#:
using System;
class DynamicArray
{
private int[] array; // Internal array to store elements
private int capacity; // Capacity of the array
private int size; // Current number of elements
// Constructor to initialize array with a default capacity
public DynamicArray(int initialCapacity = 2)
{
capacity = initialCapacity;
array = new int[capacity];
size = 0;
}
// Add an element to the dynamic array
public void Add(int element)
{
if (size == capacity)
{
Resize(); // Resize the array if it's full
}
array[size++] = element;
}
// Get an element at a specific index
public int Get(int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfRangeException("Index out of range");
}
return array[index];
}
// Set (update) an element at a specific index
public void Set(int index, int element)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfRangeException("Index out of range");
}
array[index] = element;
}
// Remove an element at a specific index
public void Remove(int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfRangeException("Index out of range");
}
for (int i = index; i < size - 1; i++)
{
array[i] = array[i + 1]; // Shift elements to the left
}
size--;
}
// Insert an element at a specific index
public void Insert(int index, int element)
{
if (index < 0 || index > size)
{
throw new IndexOutOfRangeException("Index out of range");
}
if (size == capacity)
{
Resize(); // Resize if array is full
}
for (int i = size; i > index; i--)
{
array[i] = array[i - 1]; // Shift elements to the right
}
array[index] = element;
size++;
}
// Get the current size of the array
public int Size()
{
return size;
}
// Resize the array when it's full
private void Resize()
{
capacity *= 2;
int[] newArray = new int[capacity];
for (int i = 0; i < size; i++)
{
newArray[i] = array[i]; // Copy elements to the new array
}
array = newArray;
}
// Clear the array by setting size to 0
public void Clear()
{
size = 0;
Console.WriteLine("Array cleared!");
}
// Display all elements in the dynamic array
public void Display()
{
if (size == 0)
{
Console.WriteLine("Array is empty");
}
else
{
for (int i = 0; i < size; i++)
{
Console.Write(array[i] + " ");
}
Console.WriteLine();
}
}
}
class Program
{
static void Main(string[] args)
{
DynamicArray dynamicArray = new DynamicArray();
// Adding elements
dynamicArray.Add(1);
dynamicArray.Add(2);
dynamicArray.Add(3);
dynamicArray.Add(4);
dynamicArray.Display(); // Output: Array elements: 1 2 3 4
// Get element at index 2
Console.WriteLine("Element at index 2: " + dynamicArray.Get(2)); // Output: 3
// Set element at index 1
dynamicArray.Set(1, 20);
dynamicArray.Display(); // Output: Array elements: 1 20 3 4
// Insert an element at index 2
dynamicArray.Insert(2, 100);
dynamicArray.Display(); // Output: Array elements: 1 20 100 3 4
// Remove an element at index 3
dynamicArray.Remove(3);
dynamicArray.Display(); // Output: Array elements: 1 20 100 4
// Get the current size of the array
Console.WriteLine("Size: " + dynamicArray.Size()); // Output: Size: 4
// Clear the array
dynamicArray.Clear();
dynamicArray.Display(); // Output: Array is empty
}
}Here is a custom implementation of a generic dynamic array in C#:
using System;
class DynamicArray<T>
{
private T[] array; // Internal array to store elements
private int capacity; // Capacity of the array
private int size; // Current number of elements
// Constructor to initialize array with a default capacity
public DynamicArray(int initialCapacity = 2)
{
capacity = initialCapacity;
array = new T[capacity];
size = 0;
}
// Add an element to the dynamic array
public void Add(T element)
{
if (size == capacity)
{
Resize(); // Resize the array if it's full
}
array[size++] = element;
}
// Get an element at a specific index
public T Get(int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfRangeException("Index out of range");
}
return array[index];
}
// Set (update) an element at a specific index
public void Set(int index, T element)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfRangeException("Index out of range");
}
array[index] = element;
}
// Remove an element at a specific index
public void Remove(int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfRangeException("Index out of range");
}
for (int i = index; i < size - 1; i++)
{
array[i] = array[i + 1]; // Shift elements to the left
}
size--;
}
// Insert an element at a specific index
public void Insert(int index, T element)
{
if (index < 0 || index > size)
{
throw new IndexOutOfRangeException("Index out of range");
}
if (size == capacity)
{
Resize(); // Resize the array if it's full
}
for (int i = size; i > index; i--)
{
array[i] = array[i - 1]; // Shift elements to the right
}
array[index] = element;
size++;
}
// Get the current size of the array
public int Size()
{
return size;
}
// Resize the array when it's full
private void Resize()
{
capacity *= 2;
T[] newArray = new T[capacity];
for (int i = 0; i < size; i++)
{
newArray[i] = array[i]; // Copy elements to the new array
}
array = newArray;
}
// Clear the array by setting size to 0
public void Clear()
{
size = 0;
Console.WriteLine("Array cleared!");
}
// Display all elements in the dynamic array
public void Display()
{
if (size == 0)
{
Console.WriteLine("Array is empty");
}
else
{
for (int i = 0; i < size; i++)
{
Console.Write(array[i] + " ");
}
Console.WriteLine();
}
}
}
class Program
{
static void Main(string[] args)
{
// Create a dynamic array for integers
DynamicArray<int> dynamicArray = new DynamicArray<int>();
// Adding elements
dynamicArray.Add(1);
dynamicArray.Add(2);
dynamicArray.Add(3);
dynamicArray.Add(4);
dynamicArray.Display(); // Output: Array elements: 1 2 3 4
// Get element at index 2
Console.WriteLine("Element at index 2: " + dynamicArray.Get(2)); // Output: 3
// Set element at index 1
dynamicArray.Set(1, 20);
dynamicArray.Display(); // Output: Array elements: 1 20 3 4
// Insert an element at index 2
dynamicArray.Insert(2, 100);
dynamicArray.Display(); // Output: Array elements: 1 20 100 3 4
// Remove an element at index 3
dynamicArray.Remove(3);
dynamicArray.Display(); // Output: Array elements: 1 20 100 4
// Get the current size of the array
Console.WriteLine("Size: " + dynamicArray.Size()); // Output: Size: 4
// Clear the array
dynamicArray.Clear();
dynamicArray.Display(); // Output: Array is empty
// Create a dynamic array for strings
DynamicArray<string> stringArray = new DynamicArray<string>();
stringArray.Add("Hello");
stringArray.Add("World");
stringArray.Display(); // Output: Array elements: Hello World
}
}
