🥪Array

1. Fundamentals

★ Stores items(C/C++) or their references(Python) at contiguous locations / a linear data structure that stores similar elements in contiguous memory locations.

 

★

(1) Random Access: i-th item can be accessed in O(1) Time as we have the base address and every item or reference is of same size

(2) Cache Friendliness: since items/references are stored at contiguous locations, we get the advantage of locality of reference

 

★ Not useful in places where inserting in the middle, deleting from middle, and searching in a unsorted data

 

★

(1) Array Index: elements are identified by their indexes. array index starts from 0(starting at 0 and going to (n-1) when there are n elements)

(2) Array element: elements are items stored in an array and can be accessed by their index

(3) Array Length: the length of an array is determined by the number of elements it can contain

 

★ memory representation of array

: all the elements are stored in contiguous memory locations. if we initialize an array, the elements will be allocated sequentially in memory. allows for efficient access and manipulation of elements.

 

★ declaration of array

arr = []

arr = [1, 2, 3, 4, 5]

arr = ['a', 'b', 'c', 'd', 'e']

arr = [1.4, 2.0, 24.0, 5.0, 0.0]  # All float values

 

★ types of arrays

(1) fixed size array

arr = [0] * 5

# Output the fixed-size list
print(arr)

 

(2) dynamic sized array

: the size of the array changes. add and remove the elements as per the need. The memory is mostly dynamically allocated & de-allocated in these arrays.

# Dynamic Array
arr = []

 

(3) one-dimensional array(1-D array)

: can imagine a 1d array as a row, where elements are stored one after another.

 

(4) multi-dimensional array(2-D arrays, 3-D arrays, 4-D arrays ~ )

: an array with more than one dimenstion, use multidimensional array to store complex data in the form of tables, etc. 

 

★ operaions on array

(1) array traversal: visiting all the elements of the array once.

# This list will store integer type elements
arr = [1, 2, 3, 4, 5]

# Traversing over arr
for i in range(len(arr)):
    print(arr[i], end=" ")

 

(2) insertion in array: insert one or multiple elements at any position in the array.

# Example usage
arr = [1, 2, 3, 4, 5]
x = 10  # Element to be inserted
pos = 2  # Position to insert the element

arr.insert(pos, x)

# Print the updated list
print("Updated List:", arr)

 

(3) deletion in array: delete an element at any index in an array.

# Initialize a list
arr = [10, 20, 30, 40, 50]

# Value to delete
key = 40

# Remove the element with the specified value
# if present in the list
if key in arr:
   arr.remove(key)
else:
   print("Element Not Found")

# Output the modified list
print(arr)  # Output: [10, 20, 30, 50]

 

(4) searching in an array: traverse over an array and search for an element.

# Function to implement search operation
def find_element(arr, n, key):
    for i in range(n):
        if arr[i] == key:
            return i
    return -1

(+ find(), rfind() in python)

 

★ the advantages / limitations of an array

→ the limitations of an array

* a collections of items of the same data type. ex) in an integer array only integer values can be stored. no array can have values of two data types.

* fixed size: arrays have a fixed size set at creation. expanding an array requires creating a new on and copying elements(time-consuming, memory-intensive)

* memory allocation issue: allocating large arrays can cause memory exhaustion(crashes, especially on systems with limited resources)

* insertion & deletion challenges

* limited data type support

* lack of flexibility: fixed size & limited type support make arrays less adaptable than structures like linked lists or trees

 

→ the advantages

* arrays allow random access to elements. this makes accessing elements by position faster

* arrays store multiple data of similar types with the same name

* arrays are used to implement the other data structures like linked lists, stacks, queues, trees, graphs, etc.

* memory efficiency: store elements in contiguous memory, allowing efficient allocation in a 'single block' and 'reducing memory fragmentation'

* versatility: can be used to store a wide range of data types(integers, floating-point numbers, character, and even complex data structures - objects, pointers) ** as of python

* compatibility with hardware: the array data structure is compatible with most hardware architectures(making it a versatile tool for programming in a wide range of environments)

 

★ the purpose of using arrays

: an array is used when several variables of the same type need to be used, and it can be defined as a sequence of objects of the same type(stored in contiguous memory locations. a static data structure with a fixed size)

Python

* creating a  list / accessing list items / adding items into list / updating items into list / removing items from list / iterating over lists / nested lists

 

* length of a list / maximum in a list / swap two items in a list / check if an element exists / index of an item / remove duplicate from a list / reverse a list in python / sum of a list / concatenate two lists / sort a list in python / check for sublist

 

* list method: append(), copy(), clear(), count(), extend(), index(), insert(), pop(), remove(), reverse(), sort()

C++

★ In C++, vector is a dynamic array with the ability to resize itself automatically when an element is inserted / deleted. It is the part of STL and provide various useful functions for data manipulation.

#include <bits/stdc++.h>
using namespace std;

int main() {

      // Creating a vector of 5 elements
      vector<int> v = {1, 4, 2, 3, 5};

      for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
      return 0;
}

 

★ syntax of vector

: vector is defined as the std::vector class template(contains its implementation and some useful member functions). Defined inside the <vector> header flie.

 

vector<T> vec_name;

(T: type of elements in the vector / vec_name: name assigned to the vector)

 

★ declaration & initialization

: the process of creating an instance of std::vector class and assiginig it some initial value.

 

vector<T> vec_name;

vector<T> vec_name(size, value);

vector<T> vec_name = {v1, v2, v3};

vector<T> vec_name ({v1, v2, v3...});

#include <bits/stdc++.h>
using namespace std;

void printV(vector<int> &v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

int main() {

    // Creating an empty vector
    vector<int> v1;

    // Creating a vector of 5 elements from
    // initializer list
    vector<int> v2 = {1, 4, 2, 3, 5};

    // Creating a vector of 5 elements with
    // default value
    vector<int> v3(5, 9);

    printV(v1);
    printV(v2);
    printV(v3);

    return 0;
}


/*
1 4 2 3 5 
9 9 9 9 9 
*/

 

★ Basic Vector operations

(1) accessing elements: using [] subscript operator / vector at()

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<char> v = {'a', 'c', 'f', 'd', 'z'};

    // Accessing and printing values using indexes
      cout << v[3] << endl;
      cout << v.at(2);
  
    return 0;
}

/*
d
f
*/

 

(2) updating elements(same as (1) accessing elements)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<char> v = {'a', 'c', 'f', 'd', 'z'};

    // Updating values using indexes 3 and 2
      v[3] = 'D';
      v.at(2) = 'F';
      
      cout << v[3] << endl;
      cout << v.at(2);
  
    return 0;
}

/*
D
F
*/

 

(3) traversing vector

: vector in C++ can be traversed using indexes in a loop. the indexes start from 0 and go up to vector size - 1. To iterate though this range, we can use a loop and determine the size of the vector using the vector size() method.

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<char> v = {'a', 'c', 'f', 'd', 'z'};

    // Traversing vector using vector size()
      for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}

/*
a c f d z 
a c f d z
*/

 

(4) inserting elements

: element can be inserted into a vector using vector insert() method(takes linear time) / but for the insertion at the end, the vector push_back() method can be used. It is much faster, taking only constant time.

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<char> v = {'a', 'f', 'd'};
  
      // Inserting 'z' at the back
      v.push_back('z');
  
      // Inserting 'c' at index 1
      v.insert(v.begin() + 1, 'c');

      for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}

//a c f d z

 

(5) deleting elements

: an element can be deleted from a vector using vector erase() method

// 1. remove the element at index 2
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // Remove the element at index 2
    v.erase(v.begin() + 2);

    for (auto i : v)
        cout << i << " ";
    return 0;
} // 1 3 4 5

// 2. remove the last element from the vector

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // Remove the last element
    v.erase(v.end() - 1);

    for (auto i : v)
        cout << i << " ";
    return 0;
} // 1 2 3 4 

// 3. remove a range of elements from a vector(remove elements in the range [1,4))
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // Remove elements in the range [1, 4)
    v.erase(v.begin() + 1, v.begin() + 4);

    for (auto i : v)
        cout << i << " ";
    return 0;
} // 1 5

 

: for the deletion at the end, vector push_back() method can be used, and it is much faster, taking only constant time. you can use pop_back() / erase() (for deleting element 'f' in an array)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<char> v = {'a', 'c', 'f', 'd', 'z'};

    // Deleting last element 'z'
      v.pop_back();
      for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
  
      // Deleting element 'f'
      v.erase(find(v.begin(), v.end(), 'f'));
      for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}

/*
a c f d 
a c d 
*/

 

★ member functions of vector

: push_back(), pop_back(), size(), max_size(), resize(), empty(), operator[], at(), front9), begin(), end() ~