Introduction
In the world of programming, understanding data structures is fundamental. Among the most common data structures are static arrays, dynamic arrays, and strings. In this article, we will explore the characteristics of these data structures, how they operate, and their efficiency in various scenarios. Read on to delve into the nuances of arrays and strings in Python and understand their implications when it comes to performance.
Static Arrays
Static arrays consist of a contiguous block of memory with a fixed size. For example, consider a static array with a size of five:
arr = [1, 2, 3, 4, 5]
Characteristics of Static Arrays
- Fixed Size: Once created, the size of a static array cannot change. In our example, the array will always contain five elements. The indices for these elements will range from 0 to 4.
- Index Access: Accessing an element at a specific index, like
arr[2], allows for constant time retrieval (O(1)). The operation will return3for the example above. - Mutable Objects: Static arrays are mutable, meaning that while their size is fixed, the elements within can change. For instance,
arr[4] = 7will modify the last element of the array.
Limitations of Static Arrays
While static arrays provide fixed size and index-based access, they have significant limitations:
- Insertion Constraints: Inserting an element requires shifting the entire dataset, resulting in O(n) complexity. For example, inserting at position 2 would require moving all elements after it.
- Deletion Operations: Deleting elements also leads to an O(n) complexity as it requires shifting elements to fill the gap.
Dynamic Arrays
Dynamic arrays address some limitations of static arrays by allowing for dynamic resizing. In Python, dynamic arrays are typically known as lists.
Characteristics of Dynamic Arrays
- Flexible Size: Dynamic arrays can change size, accommodating more or fewer elements as needed. For example, appending an element to a list can be done easily.
- Underlying Implementation: Though dynamic arrays offer flexibility, they often utilize static arrays under the hood. When the array reaches capacity, it creates a new, larger static array and copies the elements over. This resizing operation incurs O(n) complexity.
Operations with Dynamic Arrays
- Appending Elements: Adding an element to an empty dynamic array typically requires O(1) time if there is space, but O(n) if resizing is needed.
- Inserting Elements: Inserting an element anywhere other than the end results in O(n) complexity due to the need to shift elements.
- Deleting Elements: Deleting from the end is O(1), but any deletions from the middle or front incur O(n) complexity.
Strings in Python
Strings are a unique data structure in Python, characterized as immutable, meaning their content cannot be changed once created.
Immutable Characteristic of Strings
- No Modifications: Unlike other data structures, you cannot change a string in place. For example, attempting to modify a character in the string
s = "hello"(likes[1] = 'a') will raise an error. - Creating New Strings: To modify a string, you must create a new string altogether. For example, appending a character will involve creating a new string:
new_str = s + 'z'results in"hello z", and this operation has a time complexity of O(n).
Operations on Strings
- Index Access: Accessing individual characters within a string is O(1), such as
s[1]returning'e'. - Searching Existence: Checking if a character exists within the string requires O(n) due to scanning through all characters.
Conclusion
Understanding the differences between static arrays, dynamic arrays, and strings is essential for effective programming in Python. Static arrays provide fixed-size capabilities with indexed access but lack flexibility for resizing. Dynamic arrays, found in Python as lists, overcome this limitation by allowing dynamic resizing at a performance cost. Strings, however, present unique challenges with immutability but offer efficient access and length functionalities. As you work with these data structures, consider their performance implications to make informed decisions in your coding endeavors.
By mastering these fundamental data structures, you can optimize your code and improve efficiency in your projects.
hey guys Greg here let's talk about three common data structures known as static arrays Dynamic arrays as well as
strings so let's first talk about static arrays which is basically a contiguous block of memory with a fixed size so
let's say that it has a size of five so we'll say 1 2 3 4 and five so we have five positions here and arrays have
positions and they're called indices or indexes so this first index or position is number zero this is index one 2 three
and the last one is always going to be the length of the array minus one so the length or the capacity of the array is
five things and so this last Position will be the length minus one which is four so if you were to call this thing a
here now one of the most common things to do with arrays is ask what is at a certain position so you'd be like okay
what is at index 2 well you would do that generally in code like this so what is a at two and it would tell you in
constant time we have immediate access to the arrays position I it would tell you in constant time that a at 2 is
equal to 3 and that goes for any index so you could do a at 4 and that's going to tell you that the value is five now
arrays are what we call mutable objects they are mutable which means that they are changeable and so while you can't
change the array's size it will always have five things in it well what you could do is change what's at a
particular index so you could do something like a at 4 is equal to 7 and so again in constant time you could
change this value to be a 7 another thing you might want to do with arrays is check if a certain value is in the
array so you might write this in a programming language like five in a you're basically asking the question if
the value of five is in the array a and you'd want are there a true or false answer so basically what I would do is
say okay is this one five no it's not is this five no and you'd basically keep asking that until you get to the end of
the array or if you found it earlier and in this case you would return false here this is false because five is not in the
array if you were asking something like is one in the array well then that's actually going to be true if you look at
the very first element here that one is a one and so you basically in the worst case you do have to scan the entire
array to see if an element is in the array and so this is actually an O of n operation you have to scan the whole
array potentially the point of Big O is that it's like the worst thing possible the very worst thing that you could do
is to go through all of the array elements it might not take that long it might just be one operation here but in
the worst case you would kind of go through the whole array so that's why we use Big O now static arrays are very
limiting this thing particularly has a size of five things and so if you were to say insert into this array maybe you
wanted the second position to be a five and you wanted to keep all the stuff that you have well you can't keep all of
it you could shift it over like this so you could do a shift except notice that you're losing an element you're going to
lose what was at the end there if you you do this shift so while they sort of support this insertion it doesn't really
work because you lose an element at the end of the array and this insertion would take o of n time because you'd
basically have to go through and shift all of this stuff over here again if you wanted this position to be a seven but
you wanted to keep this stuff well you'd basically have to move this five over here this two over here three over here
the four would get lost and you'd basically be left with this array here so in the worst case we're kind of
Shifting all of the n elements so that's o of n now if you wanted to delete an element let's say that we actually just
didn't want this in the array well what would have to happen here is you need to keep the array as a contiguous block of
memory and this is not contiguous we have this gaping hole here so what would have to happen is a reverse shift you'd
have to move this over here this over here this over here and so that deletion is essentially in the worst case an O of
n operation CU you're basically moving all the stuff over that you have to and then this is fine because this is at
least contiguous you do kind of have an empty slot here and we'll just represent that as an X that's okay because you
still have this contiguous block of memory here but deletion would be an O of an operation now as you can see
static arrays are very limiting they're very frustrating but they are kind of how underlying computer memory actually
works to do something that you might actually want to do in a programming language generally you use something
like a dynamic array and so a programming language like python doesn't even have static arrays it would use
them way under the hood in like the C language but you don't really have them in the language you just use Dynamic
arrays otherwise called a list in Python so what a dynamic array is is basically an array that can change size and so
here this array here it's basically length five I know we're really only using these positions but the array's
length is technically five a dynamic array you can actually change its size and so if you wanted to have this be A7
and if you wanted to append you might hear it called a pend if you insert at the end of the array if you wanted
another element here and to change its length to make it increase you can do that in a dynamic array you could
basically just add that in there and that would be fine but how this is actually implemented under the hood is
via a static array so how this might look under the hood is something like this via a static array you'd have
something that looks like this 1 5 2 3 7 and 8 and you'd have your same positions here except this array is is static it
has a fixed size so we'll say that this thing has a length of six so how is it possible if you can just append to your
Dynamic array like if you wanted to add something like another position here maybe a five at the end well that
doesn't work if you're implementing this via a static array because you can't just add a five there that doesn't work
so what would have to happen is that you would have to take all of this stuff here so you're basically copying those
things and then making a new static array so we'd have these same positions here but notice how before we had kind
of holes at the end there well this is actually quite allow and so this array could be bigger than the size necessary
we'd have all of these positions over here basically copy all of that stuff and then put them in this new static
array and we could have the five here and we could leave some space at the end now it's very useful to leave space at
the end because if we were to insert another element over here maybe we wanted a four at this new position of
seven well then that's actually a constant time thing to do in this case because all you'd have to do is just use
this extra block and add a four there same thing with the next insert if you wanted to add another position at the
end here maybe a three at the end that's still constant time because you just use that however now is where you have the
problem because if you wanted to add another thing here at the end you would basically again have to copy all of this
stuff you would have to take all of those that's going to be an O of n operation you would have to get a new
static array which had room for this so we'll say leave two spaces at the end if you were say trying to add the value of
seven at the end well that's fine it could do that because we have a static array that's big enough so as you'll see
if you're appending to the end of the array you're trying to add something to the end some of them will be o of one or
constant because all you do is just change that underlying memory but if you're full well then you need to get
more memory AKA a new array well then that's going to be an O of n operation to copy all of that stuff over okay and
this behavior is particularly about the end of the array if you were trying to insert over here like a seven over here
well even though there's space at the end over here well you'd still need your contiguous block here and so you could
put the seven here but all of this stuff would have to shift over which again is going to be an oven operation to do that
and if you were to delete at the end well then that's actually fine every single time because all it does here
here is basically removes that and you're basically just deallocating space here so you could delete at the end
however much you want it you're basically just getting some space back there's no problem with that all
deletions in the middle or even at the front are going to be o ofen because you'd have to shift everything if you're
inserting an element anywhere that's not at the end well then that's going to take o ofen time to shift all the stuff
over but if you're appending AKA inserting at the end of the array well then that's actually some sometimes
going to be constant and other times it's going to be o of n now I'm not going to get too into this but it's
important to understand that to implement a dynamic array well it would be made up of several different static
arrays over time and so if you told something like python hey I want the dynamic array AK the list of one two a
static array might be created that looks something like this where you have some leftover space at the end so if you were
to append a new element okay you can do that that's going to be constant that just changes that position there and if
you were to do this again well then that's still going to work just fine you just change that element but it's a
problem when you run out of space and so it's going to be o of n time to copy all of this stuff here put it in a new array
and it would look something like this where you had 1 2 3 and four and then you had a bunch of space at the end
let's say you were trying to add the element of five in here so you could put it there and it's going to leave some
space left over so generally what something like python is going to do is increment in powers of two it's
basically going to make the static arrays double in size so you might have something that starts out as size two
and then once that thing got full it would increase to an array of length four and then after that ran out it
would increase to an array of length 8 and 16 and 32 and 64 and so on so basically it's going to keep doubling in
size every time that you fill up the static array it'll take o of n time to shift everything to a new array
otherwise all of the other ones are going to take constant time most of the time you'll be doing o of ones and very
occasionally you'll have to do o of ends so the math works out so that you basically put an asterisk here and say
on average most of the time you'll have an O of one time to aend at the end of the array this is particularly when
you're regarding appending at the end of the array that's going to be on average that will take 0 of one time now this
picture is from lead code it's a really good one and by list they basically mean a Dynamic array so an array that can
change size then to append to the end because that's a special case most of them will be o of one some of them will
be o of n so on average it's going to be o of one and by the way you might see this called amortized so what that
basically means is just on average it's going to be o of one popping from the end is not too bad so you just delete
something it's constant to do that inserting anywhere that's not at the end means that you will have to shift
everything over so that's o of n deleting any thing that's not from the end that again would have to shift
everything over so that's o of n modifying an element at a particular index is constant accessing an element
at an index that is going to be constant and if you're to check if an element exists then that is going to be Big O of
n to search the whole array okay so that was static arrays and dynamic arrays strings are similar but a little bit
different you generally write them in quotes So something like a b c now this is still basically a contiguous block of
memory here but strings are what we call immutable they are unchangeable objects at least this is the case in Python if
you're seeing this for a course in C or something like that you know this might not be the case but in Python strings
are going to be immutable so if you wanted to like append to the end of a string in Python and make it ABC D well
that doesn't really work you can't actually do that you would have to take this string and then make a new string
which has all of these n characters so it takes o of n time to do this you would get those characters and then you
would add add on what you wanted at the end to make ABC D for example so that's going to be o of n time to do that and
pretty much everything to do with strings in Python is going to be oen you can't insert anywhere because you can't
modify it you can't delete anywhere because you can't modify it really the only things in Python that are going to
be constant time for Strings is well they still have indices or positions so if this string was called s well you
could ask what is s at one and in O of one time it'll tell you that it's a B and something you can't do is like s at1
is equal to D basically changing this to be a d well you can't do that there what's called immutable they're
unchangeable and so that operation just isn't even allowed okay so this is the whole chart from lead code here we saw
the array based stuff again Dynamic arrays or arrays in Python are generally called lists and strings which are we're
assuming that they're IM mutable there are languages where they are mutable like for example C but if you were to
append to an end that's modif Ying so it's O of n popping from an end is modifying o of n same thing with
insertion same thing with deletion same thing with modifying a particular element you can access and see what is
at a particular position in O of one and again if you wanted to check if something exists so if you had a string
like h e l l o and you wanted to know if Z is in the string well you'd kind of have to go over all of the positions to
find that out so that's going to be o of n as well okay now let me show you a little bit of how we can use these
things in Python Okay so let's show some code for these operations using arrays and strings now I'm doing this in an
environment called collab if you're watching this on YouTube you can actually check the video description and
I'll have this collab notebook available and you can actually run that same code on the cloud so to make an array you
would just give it a name we'll call it a and then you use square brackets so in Python you generally just call this a
list so a list is basically a dynamic array and so you'd have one 2 three will be an array of those elements if you
were to Output it you could run print a and that's going to show you that exact same output right there okay if you
wanted to append or basically insert an element at the end of array well as we said that's going to be on average so on
average this will be an O of one thing to do okay if you were to do that it's pretty easy it's just literally a.
append and you can give it say a number like five and so if you were to Output a again you're going to see it has five at
the end now if you're to pop an element it's pretty easy popping basically deleting element at the end of the array
that is always going to be constant thing to do and so you can just a. pop and if you were to print a well then
you're going to see that without that append that it had if you wanted to insert not at end of the array so
anywhere that's not at the end of the array that is going to have to shift a bunch of elements over so that is going
to be o of N and to do that python has an insert function you'll notice python continues to be awesome if you wanted to
insert into a then it needs a position so at position two we are going to insert the value of five so if you were
again to print a then you're going to see at position two we're setting that to be five if you were to modify an
element so add a particular index that is going to be Big O of one or constant time to do that that would just be
saying a add an index set the value of the first index equals 7 if you were to print that you would again see first
position changes to seven and accessing an element given an index so given an index I that is just going to be
something like print a at two you can ask what is at the second index that's going to tell you it's five again this
is going to be an O of one thing to do and if you wanted to know basically if an element say six is in the array well
this if Will execute if that's true so we could just print kind of true here and that did not print anything meaning
that six was not in the array but if it was so say if seven is in the array then we would output true and so clearly it
is that is going to be an O of n thing we'd have to search the whole array to find that out okay so that's all of the
array stuff but onto strings here well then if you wanted to append at the end so append to end of string well again
that's going to completely modify it so basically what you'd have to do if you add a string called s which is going to
be the string of hello and if you wanted to add say a z at the end well what you have to do is basically get a new string
which we'll call it B is equal to S Plus Z so it's all of S Plus the character of Z and if you were to print B well that's
going to be that new string and this is going to be a big O of n thing to do is you have to take all of those characters
and then make a new string and add a character at the end of that one okay and honestly most of these operations
don't really make sense for Strings you don't really want to pop at the end of a string that's very rare inserting
something in the middle also very rare as well really the only things that are going to come up really commonly you'd
probably want to check if something is in the string you could do if e is in the string s so we could print true here
so if that works yes okay it does so e is in the string but if it wasn't if F was in the string s well that's not
going to execute anymore because that's not the case so that is going to be again in o n thing you'd have to scan
the whole string and you would definitely want to access different positions in the array so if you again
had the string of hello you could just print what is at s at 2 for example that would tell you that the third character
is an L also I almost forgot for both arrays and strings they have a length or a size and so if you wanted to check the
length of pretty much anything in Python you can just call Len and then pass it so length of a is going to Output the
length of a and so if we print that it is equal to four so currently there's four things in the array and it's a
dynamic array so this thing will change as you give it more or less elements and what's very important to know is that in
Python this is actually an O of one operation so you might think logically to get the length of an array you might
have to go over its elements but Python's quite clever and it basically just stores length as a property that it
can look up so it is actually constant time to look up what is the length of the array same thing with strings here
if you were to check the length of the string so that is actually also going to be a constant time or o of one operation
you can again just ask the length of s and it's going to tell you that it has five many characters okay so I hope this
Heads up!
This summary and transcript were automatically generated using AI with the Free YouTube Transcript Summary Tool by LunaNotes.
Generate a summary for freeRelated Summaries
Top 10 Python Functions to Simplify Your Coding Experience
Discover 10 essential Python functions that can save time and reduce headaches while coding.
A Comprehensive Guide to Pandas DataFrames in Python
Explore pandas DataFrames: basics, importing data, indexing, and more!
Python Pandas Basics: A Comprehensive Guide for Data Analysis
Learn the essentials of using Pandas for data analysis in Python, including DataFrames, operations, and CSV handling.
Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation
Explore the concepts of time complexity, space complexity, and Big O notation with practical examples.
Mastering Pandas DataFrames: A Comprehensive Guide
Learn how to use Pandas DataFrames effectively in Python including data import, manipulation, and more.
Most Viewed Summaries
Pamamaraan ng Pagtamo ng Kasarinlan sa Timog Silangang Asya: Isang Pagsusuri
Alamin ang mga pamamaraan ng mga bansa sa Timog Silangang Asya tungo sa kasarinlan at kung paano umusbong ang nasyonalismo sa rehiyon.
A Comprehensive Guide to Using Stable Diffusion Forge UI
Explore the Stable Diffusion Forge UI, customizable settings, models, and more to enhance your image generation experience.
Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas
Tuklasin ang kasaysayan ng kolonyalismo at imperyalismo sa Pilipinas sa pamamagitan ni Ferdinand Magellan.
Pamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas
Tuklasin ang mga pamamaraan at patakarang kolonyal ng mga Espanyol sa Pilipinas at ang mga epekto nito sa mga Pilipino.
Ultimate Guide to Installing Forge UI and Flowing with Flux Models
Learn how to install Forge UI and explore various Flux models efficiently in this detailed guide.
If you found this summary useful, consider buying us a coffee. It would help us a lot!