Linear Data Structure Using Arrays

Introduction to Arrays

An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number. Arrays are fixed in size, meaning that they have a predetermined size that cannot be changed during runtime.

Arrays are fundamental to many algorithms and data structures. They provide a way to store multiple items of the same type together, making it easier to calculate the position of each element by simply adding an offset to a base value.

Key Characteristics of Arrays

• Fixed Size: The size of an array is determined at the time of declaration and cannot be changed during runtime.
• Homogeneous Elements: All elements in an array must be of the same data type.
• Contiguous Memory Allocation: Elements are stored in adjacent memory locations.
• Random Access: Elements can be accessed directly using their index.
• Index-Based: Array elements are identified by their index, which typically starts from 0 in most programming languages including C++.

1-D Arrays

A one-dimensional array is the simplest form of an array. It is a linear collection of elements, where each element is accessed using a single index.

Declaration and Initialization

In C++, a one-dimensional array can be declared and initialized in several ways:

// Declaration
data_type array_name[array_size];

// Declaration and initialization
data_type array_name[array_size] = {value1, value2, ..., valueN};

// Declaration with initialization (size determined by the compiler)
data_type array_name[] = {value1, value2, ..., valueN};
                    

Example

#include <iostream>
using namespace std;

int main() {
    // Declaration
    int numbers[5];
    
    // Initialization
    numbers[0] = 10;
    numbers[1] = 20;
    numbers[2] = 30;
    numbers[3] = 40;
    numbers[4] = 50;
    
    // Declaration and initialization
    int values[5] = {1, 2, 3, 4, 5};
    
    // Declaration with initialization (size determined by the compiler)
    int data[] = {5, 10, 15, 20, 25};
    
    // Accessing array elements
    cout << "numbers[0] = " << numbers[0] << endl;
    cout << "values[3] = " << values[3] << endl;
    cout << "data[2] = " << data[2] << endl;
    
    // Modifying array elements
    numbers[2] = 35;
    cout << "Modified numbers[2] = " << numbers[2] << endl;
    
    // Traversing the array
    cout << "Traversing the values array: ";
    for (int i = 0; i < 5; i++) {
        cout << values[i] << " ";
    }
    cout << endl;
    
    return 0;
}
                    

Memory Representation of 1-D Arrays

In memory, a one-dimensional array is stored as a contiguous block. If the base address of the array is base_address and the size of each element is size_of_element, then the address of the i-th element can be calculated as:

address_of_element[i] = base_address + (i * size_of_element)
                    

For example, if an integer array starts at memory address 1000 and each integer takes 4 bytes, then:

• Element at index 0 is at address 1000
• Element at index 1 is at address 1004
• Element at index 2 is at address 1008
• And so on...

Memory Address:  1000    1004    1008    1012    1016
                 ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
Array Elements:  │ 10│   │ 20│   │ 30│   │ 40│   │ 50│
                 └───┘   └───┘   └───┘   └───┘   └───┘
Array Indices:    [0]     [1]     [2]     [3]     [4]
                        

2-D Arrays

A two-dimensional array is an array of arrays. It is a collection of elements arranged in rows and columns, forming a table-like structure. Each element is accessed using two indices: one for the row and one for the column.

Declaration and Initialization

In C++, a two-dimensional array can be declared and initialized as follows:

// Declaration
data_type array_name[row_size][column_size];

// Declaration and initialization
data_type array_name[row_size][column_size] = {
    {value11, value12, ..., value1n},
    {value21, value22, ..., value2n},
    ...
    {valuem1, valuem2, ..., valuemn}
};

// Declaration with partial initialization
data_type array_name[row_size][column_size] = {
    {value11, value12},
    {value21}
};
                    

Example

#include <iostream>
using namespace std;

int main() {
    // Declaration and initialization
    int matrix[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    
    // Accessing elements
    cout << "matrix[1][2] = " << matrix[1][2] << endl;
    
    // Modifying elements
    matrix[0][1] = 20;
    cout << "Modified matrix[0][1] = " << matrix[0][1] << endl;
    
    // Traversing the 2-D array
    cout << "Matrix elements:" << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            cout << matrix[i][j] << "\t";
        }
        cout << endl;
    }
    
    return 0;
}
                    

Memory Representation of 2-D Arrays

In memory, a two-dimensional array is stored in row-major order or column-major order. In C++, arrays are stored in row-major order, which means that all elements of the first row are stored first, followed by all elements of the second row, and so on.

If the base address of the array is base_address, the number of columns is cols, and the size of each element is size_of_element, then the address of the element at row i and column j can be calculated as:

address_of_element[i][j] = base_address + ((i * cols + j) * size_of_element)
                    

For example, if a 3x4 integer array starts at memory address 1000 and each integer takes 4 bytes, then:

• Element at [0][0] is at address 1000
• Element at [0][1] is at address 1004
• Element at [0][2] is at address 1008
• Element at [0][3] is at address 1012
• Element at [1][0] is at address 1016
• And so on...

Memory Address:  1000    1004    1008    1012    1016    1020    1024    1028    1032    1036    1040    1044
                 ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
Array Elements:  │ 1 │   │ 2 │   │ 3 │   │ 4 │   │ 5 │   │ 6 │   │ 7 │   │ 8 │   │ 9 │   │ 10│   │ 11│   │ 12│
                 └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘
Array Indices:  [0][0]  [0][1]  [0][2]  [0][3]  [1][0]  [1][1]  [1][2]  [1][3]  [2][0]  [2][1]  [2][2]  [2][3]
                        

N-D Arrays

An N-dimensional array is a generalization of 2-D arrays to N dimensions. In C++, we can have arrays with any number of dimensions, although arrays with more than 3 dimensions are rare in practice.

Declaration and Initialization

In C++, an N-dimensional array can be declared and initialized as follows:

// Declaration of a 3-D array
data_type array_name[size1][size2][size3];

// Declaration and initialization of a 3-D array
data_type array_name[size1][size2][size3] = {
    {
        {value111, value112, ...},
        {value121, value122, ...},
        ...
    },
    {
        {value211, value212, ...},
        {value221, value222, ...},
        ...
    },
    ...
};
                    

Example of a 3-D Array

#include <iostream>
using namespace std;

int main() {
    // Declaration and initialization of a 3-D array
    int cube[2][3][4] = {
        {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12}
        },
        {
            {13, 14, 15, 16},
            {17, 18, 19, 20},
            {21, 22, 23, 24}
        }
    };
    
    // Accessing elements
    cout << "cube[1][0][2] = " << cube[1][0][2] << endl;
    
    // Traversing the 3-D array
    cout << "Cube elements:" << endl;
    for (int i = 0; i < 2; i++) {
        cout << "Layer " << i + 1 << ":" << endl;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 4; k++) {
                cout << cube[i][j][k] << "\t";
            }
            cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}
                    

Memory Representation and Address Calculation of N-D Arrays

For an N-dimensional array, the memory is still allocated contiguously, and the elements are stored in a row-major order (in C++). The address calculation becomes more complex with each additional dimension.

For a 3-D array with dimensions [d1][d2][d3], the address of element [i][j][k] can be calculated as:

address_of_element[i][j][k] = base_address + ((i * d2 * d3 + j * d3 + k) * size_of_element)
                    

This formula can be generalized for N dimensions, where each index is multiplied by the product of all the dimensions to its right.

Concept of Ordered List

An ordered list is a collection of elements arranged in a specific order. In the context of arrays, an ordered list typically refers to an array where elements are arranged according to some ordering criterion, such as ascending or descending order.

Characteristics of Ordered Lists

• Order Preservation: The relative order of elements is maintained.
• Efficient Searching: Ordered lists allow for more efficient searching algorithms like binary search.
• Insertion and Deletion: These operations are more complex as they require maintaining the order.

Example: Implementing an Ordered List using Arrays

#include <iostream>
using namespace std;

class OrderedList {
private:
    int* arr;
    int capacity;
    int size;
    
public:
    OrderedList(int capacity) {
        this->capacity = capacity;
        arr = new int[capacity];
        size = 0;
    }
    
    ~OrderedList() {
        delete[] arr;
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == capacity;
    }
    
    int getSize() {
        return size;
    }
    
    // Insert an element while maintaining order
    bool insert(int element) {
        if (isFull()) {
            return false;
        }
        
        // Find the position to insert
        int pos = 0;
        while (pos < size && arr[pos] < element) {
            pos++;
        }
        
        // Shift elements to make space
        for (int i = size; i > pos; i--) {
            arr[i] = arr[i - 1];
        }
        
        // Insert the element
        arr[pos] = element;
        size++;
        
        return true;
    }
    
    // Remove an element
    bool remove(int element) {
        int pos = search(element);
        
        if (pos == -1) {
            return false;
        }
        
        // Shift elements to fill the gap
        for (int i = pos; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        
        size--;
        return true;
    }
    
    // Search for an element (using binary search)
    int search(int element) {
        int left = 0;
        int right = size - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == element) {
                return mid;
            }
            
            if (arr[mid] < element) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
    
    // Display the list
    void display() {
        if (isEmpty()) {
            cout << "List is empty" << endl;
            return;
        }
        
        cout << "List elements: ";
        for (int i = 0; i < size; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    OrderedList list(10);
    
    list.insert(5);
    list.insert(2);
    list.insert(8);
    list.insert(1);
    list.insert(9);
    
    list.display();
    
    cout << "Searching for 8: " << list.search(8) << endl;
    cout << "Searching for 3: " << list.search(3) << endl;
    
    list.remove(2);
    list.display();
    
    list.insert(7);
    list.display();
    
    return 0;
}
                    

In this example, we've implemented an ordered list using an array. The insert method ensures that elements are inserted in the correct position to maintain the order, and the search method uses binary search for efficient searching.

String Manipulation

Strings are sequences of characters, and in C++, they can be represented using character arrays or the string class from the Standard Template Library (STL). Here, we'll focus on string manipulation using character arrays.

Character Arrays (C-style Strings)

In C++, a string can be represented as an array of characters terminated by a null character ('\0'). This is known as a C-style string.

// Declaration and initialization
char str[] = "Hello";  // Equivalent to {'H', 'e', 'l', 'l', 'o', '\0'}
                    

Basic String Operations

Let's look at some basic string operations using character arrays:

#include <iostream>
#include <cstring>  // For string functions
using namespace std;

int main() {
    char str1[20] = "Hello";
    char str2[20] = "World";
    char str3[40];
    
    // String length
    cout << "Length of str1: " << strlen(str1) << endl;
    
    // String copy
    strcpy(str3, str1);
    cout << "str3 after copy: " << str3 << endl;
    
    // String concatenation
    strcat(str1, str2);
    cout << "str1 after concatenation: " << str1 << endl;
    
    // String comparison
    int result = strcmp(str1, str2);
    if (result == 0) {
        cout << "str1 and str2 are equal" << endl;
    } else if (result < 0) {
        cout << "str1 is less than str2" << endl;
    } else {
        cout << "str1 is greater than str2" << endl;
    }
    
    // Finding a substring
    char* ptr = strstr(str1, "World");
    if (ptr) {
        cout << "Substring found at position: " << (ptr - str1) << endl;
    } else {
        cout << "Substring not found" << endl;
    }
    
    return 0;
}
                    

Custom String Manipulation Functions

Let's implement some custom string manipulation functions:

#include <iostream>
using namespace std;

// Function to calculate string length
int stringLength(const char* str) {
    int length = 0;
    while (str[length] != '\0') {
        length++;
    }
    return length;
}

// Function to copy one string to another
void stringCopy(char* dest, const char* src) {
    int i = 0;
    while (src[i] != '\0') {
        dest[i] = src[i];
        i++;
    }
    dest[i] = '\0';
}

// Function to concatenate two strings
void stringConcat(char* dest, const char* src) {
    int destLen = stringLength(dest);
    int i = 0;
    
    while (src[i] != '\0') {
        dest[destLen + i] = src[i];
        i++;
    }
    
    dest[destLen + i] = '\0';
}

// Function to compare two strings
int stringCompare(const char* str1, const char* str2) {
    int i = 0;
    
    while (str1[i] != '\0' && str2[i] != '\0') {
        if (str1[i] != str2[i]) {
            return str1[i] - str2[i];
        }
        i++;
    }
    
    return str1[i] - str2[i];
}

// Function to reverse a string
void stringReverse(char* str) {
    int length = stringLength(str);
    int start = 0;
    int end = length - 1;
    
    while (start < end) {
        // Swap characters
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        
        start++;
        end--;
    }
}

int main() {
    char str1[20] = "Hello";
    char str2[20] = "World";
    char str3[40];
    
    cout << "Length of str1: " << stringLength(str1) << endl;
    
    stringCopy(str3, str1);
    cout << "str3 after copy: " << str3 << endl;
    
    stringConcat(str3, str2);
    cout << "str3 after concatenation: " << str3 << endl;
    
    int result = stringCompare(str1, str2);
    if (result == 0) {
        cout << "str1 and str2 are equal" << endl;
    } else if (result < 0) {
        cout << "str1 is less than str2" << endl;
    } else {
        cout << "str1 is greater than str2" << endl;
    }
    
    stringReverse(str1);
    cout << "str1 after reverse: " << str1 << endl;
    
    return 0;
}
                    

Using the C++ String Class

While character arrays are useful, the C++ string class provides a more convenient and safer way to work with strings:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str1 = "Hello";
    string str2 = "World";
    
    // String length
    cout << "Length of str1: " << str1.length() << endl;
    
    // String concatenation
    string str3 = str1 + " " + str2;
    cout << "str3: " << str3 << endl;
    
    // String comparison
    if (str1 == str2) {
        cout << "str1 and str2 are equal" << endl;
    } else {
        cout << "str1 and str2 are not equal" << endl;
    }
    
    // Substring
    string sub = str3.substr(6, 5);  // Start at index 6, length 5
    cout << "Substring: " << sub << endl;
    
    // Find
    size_t pos = str3.find("World");
    if (pos != string::npos) {
        cout << "Substring found at position: " << pos << endl;
    } else {
        cout << "Substring not found" << endl;
    }
    
    // Insert
    str1.insert(5, " there");
    cout << "str1 after insert: " << str1 << endl;
    
    // Replace
    str2.replace(0, 2, "Hi");
    cout << "str2 after replace: " << str2 << endl;
    
    return 0;
}
                    

Pros and Cons of Arrays

Advantages of Arrays

• Random Access: Elements can be accessed directly using their index, which makes access operations very efficient (O(1) time complexity).
• Simple and Easy to Use: Arrays are straightforward to declare, initialize, and use.
• Memory Efficiency: Arrays use contiguous memory locations, which can lead to better cache performance.
• Fixed Size: The size of an array is fixed, which can be an advantage in situations where the maximum number of elements is known in advance.

Disadvantages of Arrays

• Fixed Size: The size of an array is fixed, which can be a limitation if the number of elements is not known in advance or if it changes dynamically.
• Insertion and Deletion: These operations are inefficient for arrays, especially for large arrays, as they require shifting elements (O(n) time complexity).
• Memory Wastage: If the array is declared with a size larger than needed, memory is wasted.
• Homogeneous Elements: All elements in an array must be of the same data type, which can be a limitation in some scenarios.
• No Built-in Methods: Unlike some other data structures, arrays do not come with built-in methods for common operations like insertion, deletion, or searching.

When to Use Arrays

Arrays are suitable in the following scenarios:

• When the size of the data is known in advance and is fixed.
• When random access to elements is required.
• When memory efficiency is a concern.
• When the data structure needs to be simple and straightforward.
• When implementing other data structures like stacks, queues, and heaps.

When Not to Use Arrays

Arrays may not be the best choice in the following scenarios:

• When the size of the data is not known in advance or changes frequently.
• When frequent insertions and deletions are required.
• When the data is sparse (many elements are empty or have default values).
• When the elements are of different data types.

Applications of Arrays

Arrays are widely used in various applications due to their simplicity and efficiency. Here are some common applications:

1. Implementing Other Data Structures

Arrays are used as the underlying data structure for implementing various other data structures such as:

• Stacks: A stack can be implemented using an array with a top pointer.
• Queues: A queue can be implemented using an array with front and rear pointers.
• Heaps: Binary heaps are commonly implemented using arrays.
• Hash Tables: Arrays are used to implement the buckets in hash tables.

2. Storing and Manipulating Matrices

2-D arrays are used to represent matrices, which are fundamental in various fields such as:

• Linear Algebra: Matrix operations like addition, multiplication, and determinant calculation.
• Image Processing: Images are represented as 2-D arrays of pixels.
• Graph Representation: Adjacency matrices use 2-D arrays to represent graphs.

3. Lookup Tables

Arrays are used to implement lookup tables for quick access to precomputed values:

• Trigonometric Functions: Precomputed values of sine, cosine, etc.
• Character Encoding: ASCII and Unicode tables.
• Color Maps: Mapping between color codes and RGB values.

4. Buffering

Arrays are used as buffers in various applications:

• I/O Buffers: Temporary storage for input/output operations.
• Network Buffers: Storing packets in network communication.
• Audio/Video Buffers: Storing audio or video frames for processing.

5. Sorting and Searching

Arrays are fundamental in sorting and searching algorithms:

• Sorting Algorithms: Bubble Sort, Insertion Sort, Quick Sort, etc.
• Searching Algorithms: Linear Search, Binary Search, etc.

6. Dynamic Programming

Arrays are used to store intermediate results in dynamic programming:

• Fibonacci Series: Storing previously computed Fibonacci numbers.
• Longest Common Subsequence: Using a 2-D array to store intermediate results.
• Knapsack Problem: Using arrays to store the maximum value for different weights.

Summary

In this section, we covered linear data structures using arrays:

• Introduction to arrays and their characteristics
• 1-D arrays: declaration, initialization, and memory representation
• 2-D arrays: declaration, initialization, and memory representation
• N-D arrays: declaration, initialization, and memory representation
• Concept of ordered lists and their implementation using arrays
• String manipulation using character arrays and the C++ string class
• Pros and cons of arrays
• Applications of arrays in various domains

Arrays are fundamental data structures that serve as building blocks for more complex data structures and algorithms. Understanding arrays is essential for any programmer or computer scientist.