Arrays in Data Structure
A fundamental data structure in computer science, arrays offer an organised and effective method for rapidly accessing and organising data in computer memory.
What is an Array?
A collection of objects, or elements, of the same data type kept in consecutive memory regions is the fundamental definition of an array. An array’s distinct numerical index, which usually begins at 0, identifies each element. Constant-time access (O(1)) to any element is made possible by the characteristic direct correlation between an element’s index and memory location. For example, any element’s address can be directly determined using the formula start address + (element size * index) if you know the array’s starting memory address and the size of each element.
Types of Arrays
Understanding arrays in Python requires being able to differentiate between the array module and the language’s built-in list type:
Python Lists (Referential Arrays): Python lists, sometimes known as referential arrays, are a very flexible sequence type that is frequently utilised as an array-like structure. But lists are technically referential structures; instead of storing actual things, they hold a series of pointers to them (memory addresses). Python lists can dynamically grow or shrink in size and contain elements of various data types with its architecture. The references themselves may be dispersed throughout memory, even though they are stored adjacent to one another.
Compact Arrays (using the array module): Python offers the array module for situations in which you need to store sets of elements of the same primitive data type, such as all floats or all integers. Similar to arrays in languages like C language or C++, this module enables compact storage, which means that the real data bits are kept in memory continuously. As a result, less memory is used because there is no overhead associated with keeping both the data and individual object references. A type code must be included when constructing an array.array instance in order to designate the data type of its elements (for example, ‘i’ for signed integers, ‘f’ for floats, and ‘d’ for doubles).
Dynamic Arrays: Python list class incorporates a dynamic array mechanism into its internal workings. The user is given the idea that lists have infinite capacity with this ingenious technology that makes them automatically resize when elements are added or removed. The old array is deallocated, existing elements are copied over, and a new, larger array is allocated when the underlying array runs out of space.
Even if a single resizing operation can be costly (quiring O(n) time, where n is the number of elements), doubling the array capacity guarantees that a series of n add operations will average out to O(1) amortised time per operation. Because of this, dynamic arrays are effective for routine tasks even when resizing them occasionally becomes expensive.
Ordered Arrays: Arrays that have their items arranged in a specific order are known as ordered arrays. Their main benefit is that binary search is quick (O(log N) time). But because other components must be moved to keep the array in order, adding or removing items from an ordered array can be slow and typically require O(N) operations.
Multidimensional Arrays: Two-dimensional arrays for matrices or grids are examples of multidimensional arrays (grids), which are arrays that can be expanded to represent data in several dimensions. One popular use is the adjacency matrix representation of graphs, which shows relationships between n vertices using a n × n two-dimensional array.
Operations on Arrays
Arrays facilitate a number of basic operations that enable data manipulation:
Traverse: This procedure entails going through or processing every member in the array, usually starting with the first one and working down to the last.
Insertion: Inserting an array element is insertion. The running time of appending an element to the end of a dynamic array (such as a Python list) is usually amortised O(1). However, because it could be necessary to move later components to provide room, inserting an element at any random location can be O(N).
Deletion: Taking an element out of the array is called deletion. Because of element shifting, removing an element from an arbitrary place can require O(N) time, just like insertion.
Search: Locating an element in the array is called a search.
- In a linear search, every element is checked one after the other until the goal is located or the array’s end is reached. In the worst scenario, its time complexity is O(N).
- Although much more effective, binary search necessitates sorting the array. The search interval is continually divided in half to make it function. O(log N) is the time complexity for binary search.
Update: Making a change to an existing element’s value at a given index. This operation takes O(1) time, making it incredibly efficient.
Slicing: Python slicing is essential for extracting substrings, sublists, and subtuples from sequences. Normal slicing syntax is [start:stop:steps]. Start is the slice’s beginning index (defaulting to 0), stop is its ending index (defaulting to the sequence’s last index), and steps is the increment between indices (defaulting to 1). Python zero-indexes elements from 0 to n-1 for n-length sequences.
Concatenation: Concatenation joins two or more strings, lists, or tuples end-to-end to construct a longer sequence. These data types are often operated on using Python’s + operator. Two strings like’mrcet’ + ‘college’ become ‘Mrcetcollege’, and two lists like [‘a’,’b’] and [‘c’] can be concatenated to [‘a’, ‘b’, ‘c’].
Multiplication/Repetition: Multiplication or repetition for lists, tuples, and strings repeats a sequence a defined number of times. In Python, the * operator is used for this. For instance, multiplying’mrcet’ by 3 yields’mrcetmrcetmrcet’, and multiplying a list by 2 yields. This operation also repeats tuple values n times. Repetition operations on list and tuple classes have an asymptotic running time of O(cn), where c is the repetition factor and n is the data sequence length.
Code Example
Using Python’s built-in list and, when necessary, the array module, the following Python code illustrates the ideas and procedures covered for arrays.
import array as arr # Import the array module for compact arrays
# 1. Creating an Array
# Python list: dynamic, referential, can hold mixed types
my_list = [10, "hello", 30.5, 40, True]
print(f"1. Initial list (Python's built-in list): {my_list}")
# Array using 'array' module: compact, fixed-type elements
# Benefits: Less memory, faster for numerical data due to contiguous storage of values..
my_array = arr.array('i', [126, 150, 151, 152, 153])
print(f" Initial array (using array module, type 'i'): {my_array}")
# 2. Accessing Elements (O(1) operation for both)
first_element_list = my_list[0]
third_element_array = my_array[2]
print(f"\n2. First element of list: {first_element_list}")
print(f" Third element of array: {third_element_array}")
# 3. Traversing (iterating through elements)
print("\n3. Traversing list elements:")
for element in my_list:
print(element, end=" ")
print("\n")
# 4. Insertion (Dynamic arrays: append is amortized O(1), insert at index is O(N))
my_list.append(60)
print(f"4. List after append(60): {my_list}")
my_list.insert(2, "new_item")
print(f" List after insert(2, 'new_item'): {my_list}")
# array.array objects support append, but not insert at arbitrary positions directly via slice assignment.
my_array.append(60)
print(f" Array after append(60) (array module): {my_array}")
# 5. Deletion (O(N) for removal at arbitrary index, O(1) for pop from end)
my_list.remove("hello")
print(f"5. List after remove('hello'): {my_list}")
del my_list[1]
print(f" List after del my_list[1]: {my_list}")
popped_element = my_list.pop()
print(f" List after pop() (last element removed): {my_list}, Popped: {popped_element}")
my_array.pop()
print(f" Array after pop() (array module): {my_array}")
# 6. Searching
# Linear Search (O(N) worst-case)
search_value_linear = 40
if search_value_linear in my_list:
print(f"\n6. {search_value_linear} found in list (Linear Search concept). Index: {my_list.index(search_value_linear)}")
else:
print(f"\n6. {search_value_linear} not found in list (Linear Search concept).")
# Binary Search (O(log N) for sorted arrays)
# Python's built-in list.index() is linear. For binary search, a custom function is needed.
def binary_search_func(arr_data, target):
low, high = 0, len(arr_data) - 1
while low <= high:
mid = (low + high) // 2
if arr_data[mid] == target:
return mid
elif arr_data[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
sorted_example_list = [112, 126, 150, 155, 156]
search_value_binary = 155
index_found = binary_search_func(sorted_example_list, search_value_binary)
if index_found != -1:
print(f" {search_value_binary} found at index {index_found} in sorted list (Binary Search concept).")
else:
print(f" {search_value_binary} not found (Binary Search concept).")
search_value_binary_not_found = 50
index_not_found = binary_search_func(sorted_example_list, search_value_binary_not_found)
if index_not_found != -1:
print(f" {search_value_binary_not_found} found at index {index_not_found} in sorted list (Binary Search concept).")
else:
print(f" {search_value_binary_not_found} not found (Binary Search concept).")
# 7. Updating (O(1))
my_list[0] = "updated_item"
print(f"\n7. List after updating index 0: {my_list}")
my_array[0] = 5
print(f" Array after updating index 0 (array module): {my_array}")
# 8. Slicing
sliced_part = my_list[1:4]
print(f"\n8. Sliced part of list (indices 1-3): {sliced_part}")
full_copy = my_list[:]
print(f" Full copy of list via slicing: {full_copy}")
# 9. Concatenation
list_a = [1, 154, 157]
list_b = [2, 25, 85]
combined = list_a + list_b
print(f"\n9. Concatenated lists: {combined}")
# array.array objects can also be concatenated
array_a = arr.array('i', [1, 154])
array_b = arr.array('i', [2, 157])
combined_array = array_a + array_b
print(f" Concatenated arrays (array module): {combined_array}")
# 10. Multiplication/Repetition
repeated = [1, 154] * 3
print(f"\n10. Repeated list: {repeated}")
repeated_array = arr.array('i', [1, 154]) * 2
print(f" Repeated array (array module): {repeated_array}")Output:
Initial list (Python's built-in list): [10, 'hello', 30.5, 40, True]
Initial array (using array module, type 'i'): array('i', [126, 150, 151, 152, 153])
First element of list: 10
Third element of array: 151
Traversing list elements:
10 hello 30.5 40 True
List after append(60): [10, 'hello', 30.5, 40, True, 60]
List after insert(2, 'new_item'): [10, 'hello', 'new_item', 30.5, 40, True, 60]
Array after append(60) (array module): array('i', [126, 150, 151, 152, 153, 60])
List after remove('hello'): [10, 'new_item', 30.5, 40, True, 60]
List after del my_list[1]: [10, 30.5, 40, True, 60]
List after pop() (last element removed): [10, 30.5, 40, True], Popped: 60
Array after pop() (array module): array('i', [126, 150, 151, 152, 153])
40 found in list (Linear Search concept). Index: 2
155 found at index 3 in sorted list (Binary Search concept).
50 not found (Binary Search concept).
List after updating index 0: ['updated_item', 30.5, 40, True]
Array after updating index 0 (array module): array('i', [5, 150, 151, 152, 153])
Sliced part of list (indices 1-3): [30.5, 40, True]
Full copy of list via slicing: ['updated_item', 30.5, 40, True]
Concatenated lists: [1, 154, 157, 2, 25, 85]
Concatenated arrays (array module): array('i', [1, 154, 2, 157])
Repeated list: [1, 154, 1, 154, 1, 154]
Repeated array (array module): array('i', [1, 154, 1, 154])Conclusion
In conclusion, because of their index-based referencing and contiguous memory allocation, arrays are essential for effective data access and storage. For more memory-efficient compact arrays of homogenous primitive types, Python provides the array module and its flexible list type, which serves as a dynamic, referential array. To select the best data structure for a particular programming assignment, it is essential to comprehend its kinds, benefits, drawbacks, related operations, and time complexity.