Welcome to the wonderful world of data structures and algorithms! Today, we’re setting the foundation with a fundamental building block: The array. Arrays are like trusty toolboxes of computer science, used to store and organize similar types of data.
An array is simply a fixed-size list that holds elements of the same data type, whether they are numbers, characters, or even objects.
So what arrays can do:
- Random Access: An array is a sequence of items with an index, allowing you to access specific items immediately.
- Efficient for specific operations: Arrays are efficient when removing elements from the beginning or end, but inserting or deleting an element from the middle takes more time because it requires shifting elements to make space for the new item.
To understand more about arrays, we need to dive deeper into how they work behind the scenes. Therefore, we should not rely on libraries to perform basic operations such as insertions and deletions in an array.
Insert operation
When we insert an element into the middle of an array, we need to:
- Make space for the item to be inserted (we need to shift elements to the left to create more space).
- Insert element
def insert(array, value, index):
if index < 0 or index > len(array):
raise IndexError("Index out of bounds")
for i in range(len(array) - 1, index - 1, -1):
array[i] = array[i - 1]
array[index] = value
Insert operation
When we delete an element from the middle, we need to shift elements backward to overwrite the deleted element.
- Loop to find the element to delete.
- Create another loop from the element to be deleted to the end.
- Override j = j + 1
def remove(array, value):
found = False
for i in range(len(array)):
if array[i] == value:
for j in range(i + 1, len(array)):
array[j - 1] = array[j]
array.pop()
found = True
break
if not found:
raise ValueError(f"Value {value} not found in the array")
Source code : https://github.com/hongquan080799/data-structure-and-algorithms
Conclusion: An array is the building block of data structures, so based on what we have learned, arrays are commonly used for quick access and reading data regularly. They are also frequently used for inserting and updating data at the end but not typically used for frequent insertions or deletions in the middle. The time complexity for search is O(1), while for insertion and deletion it is O(N).
