Arrays & Linked Lists Review

[00:00:00]
>> Bianca Gandolfo: So we're gonna start with a quick review of linear data structures. So, prior to this course we talked a lot about linear data structures. So, for those of you who took my prior courses, this will be familiar, if not you should go, hurry and go look at them.

[00:00:17]
No, we will review them. So, our linear data structures are linked list, array, stack, and queue. And what do these data structures have in common?
>> Speaker 2: Order.
>> Bianca Gandolfo: Yeah, so there order. There's like an obvious order, right? There's always like a next or a previous even though there might not be a pointer to that, for sure.

[00:00:47]
Anything else?
>> Speaker 3: They're all one dimensional.
>> Bianca Gandolfo: Yeah, one dimensional. They have a start and an end, things like this. This is what we can expect with a linear data structure,
>> Bianca Gandolfo: Simple, right, we got this. It looks easy, right, cuz it's got the squares and the arrows.

[00:01:11]
I feel these kind of courses, we have the circles and the lines, the squares and the arrows and like, that's so easy. And then we're like, look at the code and it's this long. Cool, let's talk about the time complexity here. For an array, what is the time complexity if inserting a value at the end of an array?

[00:01:33]
>> Speaker 2: Constant.
>> Bianca Gandolfo: Constant. What about, let's go around like this. You can just say you don't know if you don't know, it's totally fine. What's the time complexity of inserting at the beginning, Stephanie?
>> Speaker 2: Constant as well, right?
>> Bianca Gandolfo: Actually, no. It's actually a linear, because we have to insert the value at the beginning and then we have to move over all of the indices.

[00:02:01]
So that's a linear operation, cool. What do you think the insert in general is?
>> Speaker 3: Also linear.
>> Bianca Gandolfo: Yep, what about removing from the end?
>> Speaker 3: Constant.
>> Bianca Gandolfo: Constant, what about removing from the beginning?
>> Speaker 3: Also linear.
>> Bianca Gandolfo: Yep, linear. What about generally removing?
>> Speaker 2: Linear.
>> Bianca Gandolfo: Yep, very good.

[00:02:29]
What about finding a value?
>> Speaker 3: Linear.
>> Bianca Gandolfo: Linear, what's the difference between finding and accessing a value, do you know Eric?
>> Speaker 3: So finding will be looking through all the values to find a specific value. If you're accessing your personal index and it will a constant time operation.

[00:02:48]
>> Bianca Gandolfo: Yeah, absolutely, very good. So, we're talking about constant and linear. These are different types of time complexity, and we write them down using big O notation which means we put an O in front of it, there's some parenthesis, if it's constant we put 1, if it's linear we put n.

[00:03:11]
This should sound familiar and if it's not sounding familiar, you should see my previous courses on time complexity where I break it down more in depth. All right, so linked list. So, linked list is a link data structure. Again, it's linear and it's nodes connected by a next property that points to the next node, okay?

[00:03:38]
What is the time complexity of inserting at the end, Michael?
>> Speaker 3: Constant.
>> Bianca Gandolfo: Yep, Joe, what's the time complexity of inserting at the beginning?
>> Speaker 3: I don't know.
>> Bianca Gandolfo: It is also constant. So this is different than the array, right, which was linear. And so this is one of the nice things about a linked list.

[00:04:07]
One caveat about inserting at the end being constant, that's only true if you have a reference to the last node. So if you don't have a reference to last node, you have to then traverse through the entire data structure to get to the end and then add it.

[00:04:22]
So then, what would time complexity for that, Michael?
>> Speaker 3: If you're adding to the end?
>> Bianca Gandolfo: Yeah, if you had to traverse through?
>> Speaker 3: Linear.
>> Bianca Gandolfo: Linear, yep. And Stephanie, generally inserting to a linked list?
>> Speaker 2: Is linear as well.
>> Bianca Gandolfo: Depending, right?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: Okay.

[00:04:45]
>> Bianca Gandolfo: So linear, if you don't have a reference to the node before it, or it's constant if you do have reference to that node, yeah. And so that's something to note, that's an optimization for your linked list. That if you need to insert or remove to have a reference to that node and it will make it a constant time operation versus linear, where you have to traverse through the entire data structure.

[00:05:12]
So same thing for removing. What about finding a value, Eli?
>> Speaker 2: It's linear.
>> Bianca Gandolfo: What about accessing value, Kareem?
>> Speaker 3: Linear.
>> Bianca Gandolfo: Yeah, it's actually also linear again, unless you somehow already have access to it. But that doesn't really make sense in the context of a linked list.

[00:05:33]
We don't have an index or a key where you could just quickly look it up. You only can find the next value or a particular value through the connection from a different node. So,