Adjacency List

[00:00:00]
>> Bianco Gandolfo: Adjacency List is another top contender for how we can represent a graph. So what we do here is, we have a list of all the Vertices, and then we point to all the adjacent vertices. That's why it's called Adjacency List. So 1 is connected to 2, and also 5.

[00:00:24]
So we can see here 1 is pointing to 2, and also 5. I am gonna stop there and just show you the code, because it's a little simpler than this diagram. So 1 is connected to 2 and 5.
>> Bianco Gandolfo: Right, and this is gonna be a pointer. This is not just a raw value.

[00:00:46]
This is pointing to an object.
>> Bianco Gandolfo: Why does that matter?
>> Student1: [INAUDIBLE]
>> Bianco Gandolfo: Why does it matter?
>> Student1: Cuz we are cursing through it.
>> Bianco Gandolfo: Yeah, we're cursing. If we didn't hold reference to the value then, if we didn't hold reference to the object, we only had the value, then we would have to search for the object and stuff like that.

[00:01:12]
So we wanna point to the actual value, but because slides, this is just representing that pointer. So this isn't really an array with 2 and 5 in it. This is an array that points to an object that has 2 that points to another object that has 5.
>> Bianco Gandolfo: Okay,

[00:01:36]
>> Bianco Gandolfo: Questions? Why do you think there are arrows? What does that look like to you?
>> Student2: A linked list.
>> Bianco Gandolfo: Looks like a linked list.
>> Bianco Gandolfo: Cool.
>> Student3: Is the 1, 2, 5, which is missing an arrow because you forgot it or?
>> Bianco Gandolfo: Yeah, the 2 to the 5 is missing an arrow.

[00:02:03]
I apologize. But, yeah, good catch. That's an array and part of it is a linked list, that would be funny. Yeah, whoa, that was interesting, I haven't thought about that before. Okay, so adding an Edge. How might we add an Edge here? So let's say we wanted to connect 3 with 5.

[00:02:32]
>> Bianco Gandolfo: How about-
>> Student3: Constant to the power of 2?
>> Bianco Gandolfo: Well, how will we do it?
>> Student3: Push the 5 onto the 3 and the 3 onto the 5.
>> Bianco Gandolfo: Yep.
>> Speaker 2: Do we believe him?
>> Student1: No.
>> Bianco Gandolfo: [LAUGH] Yeah, that's what it is. Yeah, so you just push it onto the end.

[00:02:56]
This was an array implementation, but whenever you see array, you can think this could maybe also be a linked list, and there's pros and cons to both.
>> Student4: Is that still considered constant even though we're doing it twice? We're always doing it twice.
>> Bianco Gandolfo: Yeah, so when you say, so this would be, it would be 0 of 2, which is 0 of 1, we just reduce it to the-

[00:03:21]
>> Student4: We know that that was a time constraint is, it's not variable to a certain degree-
>> Speaker 2: Yeah, we wanna think about it in terms of like, what is the word? What's the word guys? We think about time complexity in terms of magnitudes rather than exacts.
>> Student5: It's exact then it's constant.

[00:03:42]
>> Student1: Right, part of it.
>> Bianco Gandolfo: If it's exact then it's like 0 of 2. But constant is 0 of 1, but 0 of 2 is 0 of 1.
>> Student4: Okay. [LAUGH]
>> Bianco Gandolfo: It's like an order of magnitude since 2 doesn't, there's no end involved, so it's just like whatever it is you just have to do to two things.

[00:04:01]
And this is, kind of gray, kind of hand wavy, but anyway. Okay, so adding an Edge, removing an Edge, a little bit different. We can splice it out, maybe. What's the time complexity of this one?
>> Student4: It's very [INAUDIBLE] for you to find it, right?
>> Bianco Gandolfo: Hmm.
>> Student4: You need to find it each time.

[00:04:32]
It's just not constant.
>> Bianco Gandolfo: Yeah. So index of, right, remember I was saying this is the thing that we should be paying attention to when we're talking about time complexity of these methods. Index of, if you imagine, so what index of does is it takes a value and it searches, right?

[00:04:53]
The array for the thing, once it finds the thing it returns it, right? Any search is gonna be, that's not totally true, any linear search like this is gonna be linear, right? The worst case is gonna be at the very end, and you're gonna have to go all the way to the very end to find it.

[00:05:09]
Now, that's how we have to think about it. So that's linear, so this is also linear. What about splice?
>> Student4: Splice is constant, so we have the index already, right?
>> Bianco Gandolfo: Well-
>> Student5: It's an array already.
>> Student6: We have move over everything afterwards.
>> Bianco Gandolfo: Yeah, so if you spliced off the very first thing, then you would have to move everything over in index, right?

[00:05:38]
Hence, why linked list is a good idea for this, right? We don't wanna have to worry about the added time complexity. We're already doing work on a graph, and that's pretty data intensive data structure. So we wanna minimize this as much as possible, and so we can just use a linked list.

[00:05:59]
>> Speaker 2: Awesome.
>> Bianco Gandolfo: All right, so let's just compare for a second. Adjacency List and Adjacency Matrix, side by side, it's not so different, right?