Introduction to Algorithm and Data Structure 2 by Bolakale Aremu

Author:Bolakale Aremu [Aremu, Bolakale]
Language: eng
Format: epub
Tags: Introduction to Algorithms, data structures and algorithms, python data structures and algorithms, algorithm, fundamentals of data structure in, algorithms for beginners
Publisher: Ojula Technology Innovations
Published: 2023-04-14T23:00:00+00:00

Figure 2.2.12: Python allocates 4 blocks of memory even though only three elements have been added

If you look at when the size of the list is four, this means that when appending four more values until the size of eight, each of those append operations do not increase the amount of space taken at specific points. However, when resizing is triggered, space required increases as memory allocation increases. Figure 2.2.13.

Figure 2.2.13: Allocation of 16 blocks of memory is triggered when the 9th element 4 is added

This might signify that the append method has a non-constant space complexity, but it turns out that, because some operations don't increase space and others do, when you average all of them out, append operations take constant space. We say that it has an Amortized Constant Space Complexity.

This also happens with insert operations. If we had four-element array, we would have four elements and a memory allocation of four. An insert operation at that point, it doesn't matter where it happens on the list, it would trigger a resize. Inserting is still more expensive though because after the resize, every element needs to be shifted over one.

The last (third) insert operation that is supported in most languages is the ability to add one list to another. In Python, this is called an extend. Now, let’s clear your workspace and start writing a new code. We will begin with an empty list.

numbers = []

numbers.extend([4,5,6])

In the second line, as an argument, I just passed in (added) a new list (4, 5, 6) entirely. Now, to print out numbers, we write

print(numbers)

If you run this code, you'll see that our list now contains the values 4, 5, and 6.

[4, 5, 6]

So, extend takes another list to add. Extend effectively makes a series of append calls on each of the elements in the new list until all of them have been appended to the original list. This operation has a runtime of Big O(k) where k represents the number of elements in the list that we're adding to our existing list.

Array Deleting

The last type of operation we need to consider are delete operations. Deletes are similar to inserts in that when a delete operation occurs, the list needs to maintain correct index values. So, where an insert shifts every element to the right, a delete operation shifts every element to the left. Just like an insert as well, if we delete the first element in the list, every single element in the list needs to be shifted to the left. Delete operations have an upper bound of Big O(n), also known as a linear runtime.

Now that we've seen how common operations work on a data structure that we're quite familiar with, let's switch tracks and build our own data structure.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.