[Section 6] [More Comfortable] [Rob Bowden] [Harvard University] [This is CS50.] [CS50.TV] 

We can head to our section of questions. I sent the URL for the space before. The beginning of the section of the questions say— apparently I'm not entirely unsick—is a very easy question of just what is valgrind? What does valgrind do? Anyone want to say what valgrind does? [Student] Checks memory leaks. Yeah, valgrind is a general memory checker. It, in the end, tells you if you have any memory leaks, which is mostly what we're using it for because if you want to do well in the problem set or if you want to get on the big board, you need to have no memory leaks whatsoever, and in case you have a memory leak that you can't find, also keep in mind that whenever you open a file and if you don't close it, that's a memory leak. 

A lot of people are looking for some node that they're not freeing when really, they didn't close the dictionary in the very first step. It also tells you if you have any invalid reads or writes, which means if you try and set a value that's beyond the end of the heap and it doesn't happen to seg fault but valgrind catches it, as you shouldn't actually be writing there, and so you definitely shouldn't have any of those either. How do you use valgrind? How do you use valgrind? 

It's a general question of kind of run it and look at the output. The output is overwhelming a lot of times. There's also fun errors where if you have some terribly wrong thing happening in a loop, then it will eventually say, "Way too many errors. I'm going to stop counting now." It's basically textual output that you have to parse. In the end, it will tell you any memory leaks that you have, how many blocks, which can be useful because if it's one block unfreed, then it's usually easier to find than 1,000 blocks unfreed. 1,000 blocks unfreed probably means you're not freeing your linked lists appropriately or something. That's valgrind. 

Now we have our section of questions, which you don't need to download. You can click on my name and pull them up in the space. Now click on me. Revision 1 will be stack, which we're doing first. Revision 2 will be queue, and Revision 3 will be the singly linked list. Starting off with our stack. As it says here, a stack is one of the most basic, fundamental data structures of computer science. The very prototypical example is the stack of trays in the dining hall. It's basically whenever you are being introduced to a stack, someone is going to say, "Oh, like a stack of trays." You stack the trays up. Then when you go to pull a tray, the first tray that's getting pulled is the last one that was put on the stack. The stack also—like it says here— we have the segment of memory called the stack. And why is it called the stack? 

Because like a stack data structure, it pushes and pops stack frames on the stack, where stack frames are like a specific call of a function. And like a stack, you will always have to return from a function call before you can get down into lower stack frames again. You can't have main call foo call bar and bar return to main directly. It's always got to follow the correct stack pushing and popping. The two operations, like I said, are push and pop. Those are universal terms. You should know push and pop in terms of stacks no matter what. We'll see queues are kind of different. It doesn't really have a universal term, but push and pop are universal for stacks. Push is just put on the stack. Pop is take off the stack. And we see here we have our typedef struct stack, so we have char** strings. Don't get scared by any **. This is going to end up being an array of strings or an array of pointers to characters, where pointers to characters tend to be strings. It doesn't have to be strings, but here, they're going to be strings. 

We have an array of strings. We have a size, which represents how many elements are currently on the stack, and then we have the capacity, which is how many elements can be on the stack. The capacity should start off as something greater than 1, but the size is going to start off as 0. Now, there are basically three different ways you can think of a stack. Well, there are probably more, but the two main ways are you can implement it using an array, or you can implement it using a linked list. Linked lists are kind of trivial to make stacks from. It is very easy to make a stack using linked lists, so here, we're going to make a stack using arrays, and then using arrays, there's also two ways you can think about it. Before, when I said we have a capacity for the stack, so we can fit an element on the stack. 

The one way it could happen is as soon as you hit 10 elements, then you're done. You might know that there is an upper bound of 10 things in the world that you'll never have more than 10 things on your stack, in which case you can have an upper bound on the size of your stack. Or you could have your stack be unbounded, but if you're doing an array, that means that every single time you hit 10 elements, then you're going to have to grow to 20 elements, and when you hit 20 elements, you're going to have to grow your array to 30 elements or 40 elements. You're going to need to increase the capacity, which is what we're going to do here. Every single time we reach the maximum size of our stack, when we push something else on, we're going to need to increase the capacity. Here, we have push declared as bool push (char* str). Char* str is the string that we are pushing onto the stack, and bool just says whether we succeeded or failed. 

How can we fail? What is the only circumstance that you can think of where we would need to return false? Yeah. [Student] If it's full and we're using a bounded implementation. Yeah, so how do we define—he answered if it's full and we're using a bounded implementation. Then we will definitely return false. As soon as we hit 10 things in the array, we can't fit 11, so we return false. What if it is unbounded? Yeah. If you can't expand the array for some reason. Yeah, so memory is a limited resource, and eventually, if we keep pushing things onto the stack over and over again, we're going to try and allocate a bigger array to fit the larger capacity, and malloc or whatever we're using is going to return false. Well, malloc will return null. 

Remember, every single time you ever call malloc, you should be checking to see if it returns null or else that is a correctness deduction. Since we want to have an unbounded stack, the only case we're going to be returning false is if we try to increase the capacity and malloc or whatever returns false. Then pop takes no arguments, and it returns the string that is on the top of the stack. Whatever was most recently pushed on the stack is what pop is returning, and it also removes it from the stack. And notice that it returns null if there is nothing on the stack. It is always possible that the stack is empty. In Java, if you're used to that, or other languages, trying to pop from an empty stack might cause an exception or something. 

But in C, null is kind of a lot of the cases how we handle these problems. Returning null is how we're going to signify that the stack was empty. We've provided code that will test your stack's functionality, implement push and pop. This will not be a lot of code. I will—actually, before we do that, hint, hint— if you have not seen it, malloc is not the only function that allocates memory on the heap for you. There are a family of alloc functions. The first is malloc, which you're used to. Then there's calloc, which does the same thing as malloc, but it will zero everything out for you. If you've ever wanted to set everything to null after mallocing something you should have just used calloc in the first place instead of writing a for loop to zero out the entire block of memory. 

Realloc is like malloc and has a lot of special cases, but basically what realloc does is it takes a pointer that had already been allocated. Realloc is the function you want to be paying attention to here. It takes a pointer that had already been returned from malloc. Let's say you request from malloc a pointer of 10 bytes. Then later you realize you wanted 20 bytes, so you call realloc on that pointer with 20 bytes, and realloc will automatically copy over everything for you. If you just called malloc again, like I have a block of 10 bytes. Now I need a block of 20 bytes, so if I malloc 20 bytes, then I have to manually copy over the 10 bytes from the first thing into the second thing and then free the first thing. Realloc will handle that for you. 

Notice the signature is going to be void *, which is just returning a pointer to the block of memory, then void* ptr. You can think of void* as a generic pointer. Generally, you never deal with void*, but malloc is returning a void*, and then it's just used like this is actually going to be a char*. The previous void* that had been returned by malloc is now going to be passed to realloc, and then size is the new number of bytes you want to allocate, so your new capacity. I'll give you a couple minutes, and do it in our space. Start with Revision 1. I'll stop you after hopefully about enough time to implement push, and then I'll give you another break to do pop. But it really isn't that much code at all. The most code is probably the expanding stuff, expanding the capacity. Okay, no pressure to be completely done, but as long as you feel like you're on the right path, that's good. 

Does anyone have any code they feel comfortable with me pulling up? Yeah, I will, but does anyone have any code I can pull up? Okay, can you start, save it, whatever it is? I always forget that step. Okay, looking at push, do you want to explain your code? [Student] First of all, I increased the size. I guess maybe I should have that—anyway, I increased the size, and I see if it's less than the capacity. And if it's less than the capacity, I add to the array that we already have. And if it's not, I multiply the capacity by 2, and I reallocate the strings array to something with a bigger capacity size now. And then if that fails, I tell the user and return false, and if it's fine, then I put the string in the new spot. 

[Rob B.] Also notice that we used a nice bitwise operator here to multiply by 2. Remember, left shift is always going to be multiplied by 2. Right shift is divided by 2 as long as you remember that it means divide by 2 as in an integer divided by 2. It might truncate a 1 here or there. But shift left by 1 is always going to be multiplied by 2, unless you overflow the bounds of the integer, and then it won't be. A side comment. I like to do—this isn't going to change the coding any way whatsoever, but I like to do something like this. It actually is going to make it slightly longer. Maybe this isn't the perfect case to show this, but I like to segment it into these blocks of— okay, if this if happens, then I'm going to do something, and then the function is done. I don't need to then scroll my eyes all the way down the function to see what happens after the else. It's if this if happens, then I just return. It also has the nice added benefit of everything beyond this is now shifted left once. I no longer need to—if you ever near ridiculously long lines, then those 4 bytes can help, and also the more left something is, the less overwhelmed you feel if like—okay, I have to remember I'm currently in a while loop inside of an else inside of a for loop. Anywhere you can do this return immediately, I kind of like. It's totally optional and not expected in any way. 

[Student] Should there be a size-- in the fail condition? The fail condition here is we failed to realloc, so yes. Notice how in the fail condition, presumably, unless we free stuff later, we're always going to fail no matter how many times we try to push something. If we keep pushing, we keep incrementing size, even though we are not putting anything onto the stack. Usually we don't increment the size until after we have successfully put it on the stack. We would do it, say, either here and here. And then instead of saying s.size ≤ capacity, it's less than capacity, only because we moved where everything was. 

And remember, the only place that we could possibly return false is here, where realloc returned null, and if you happen to remember standard error, maybe you might consider this a case where you want to print a standard error, so fprintf stderr instead of just printing directly to standard out. Again, that's not an expectation, but if it's an error, type printf, then you might want to make it print to standard error instead of standard out. 

Anyone have anything else to note? Yes. [Student] Can you go over the [inaudible]? [Rob B.] Yes, the actual binariness of it or just what it is? [Student] So you multiply it by 2? [Rob B.] Yeah, basically. In binary land, we always have our set of digits. Shifting this left by 1 basically inserts it here at the right side. Back to this, just remembering that everything in binary is a power of 2, so this represents 2 to the 0, this 2 to the 1, this 2 to the 2. By inserting a 0 to the right side now, we just shift everything over. What used to be 2 to the 0 is now 2 to the 1, is 2 to the 2. The right side that we inserted is necessarily going to be 0, which makes sense. If you ever multiply a number by 2, it's not going to end up odd, so the 2 to the 0 place should be 0, and this is what I half warned about before is if you do happen to shift beyond the number of bits in an integer, then this 1 is going to end up going off. That's the only worry if you happen to be dealing with really large capacities. But at that point, then you're dealing with an array of billions of things, which might not fit into memory anyway. 

Now we can get to pop, which is even easier. You could do it like if you happen to pop a whole bunch, and now you're at half capacity again. You could realloc to shrink the amount of memory you have, but you don't have to worry about that, so the only realloc case is going to be growing memory, never shrinking memory, which is going to make pop super easy. Now queues, which are going to be like stacks, but the order that you take things out is reversed. The prototypical example of a queue is a line, so I guess if you were English, I would have said a prototypical example of a queue is a queue. So like a line, if you're the first person in line, you expect to be the first person out of the line. If you're the last person in line, you are going to be the last person serviced. We call that FIFO pattern, whereas stack was LIFO pattern. Those words are pretty universal. 

Like stacks and unlike arrays, queues typically don't allow access to elements in the middle. Here, a stack, we have push and pop. Here, we happen to have called them enqueue and dequeue. I have also heard them called shift and unshift. I've heard people say push and pop to also apply to queues. I have heard insert, remove, so push and pop, if you are talking about stacks, you are pushing and popping. If you're talking about queues, you could pick the words you want to use for insertion and removal, and there is no consensus on what it should be called. But here, we have enqueue and dequeue. Now, the struct looks almost identical to the stack struct. But we have to keep track of head. I guess it says down here, but why do we need the head? The prototypes are basically identical to push and pop. You can think of it as push and pop. The only difference is pop is returning—instead of the last, it's returning the first. 2, 1, 3, 4, or something. And here's the start. Our queue is completely full, so there's four elements in it. The end of our queue is currently 2, and now we go to insert something else. 

When we want to insert that something else, what we did for the stack version is we extended our block of memory. What is the problem with this? [Student] You move the 2. What I said before about the end of the queue, this doesn't make sense that we start at 1, then we want to dequeue 1, then dequeue 3, then dequeue 4, then dequeue 2, then dequeue this one. We can't use realloc now, or at the very least, you have to use realloc in a different way. But you probably shouldn't just use realloc. You are going to have to manually copy your memory. 

There are two functions to copy memory. There's memcopy and memmove. I'm currently reading the man pages to see which one you're going to want to use. Okay, memcopy, the difference is that memcopy and memmove, one handles the case correctly where you're copying into a region that happens to overlap the region you're copying from. Memcopy does not handle it. Memmove does. You can think of the problem as— let's say I want to copy this guy, these four to this guy over. In the end, what the array should look like after the copy is 2, 1, 2, 1, 3, 4, and then some stuff at the end. But this is dependent on the order in which we actually copy, since if we don't consider the fact that the region we're copying into overlaps the one we're copying from, then we might do like start here, copy the 2 into the place we want to go, then move our pointers forward. 

Now we're going to be here and here, and now we want to copy this guy over this guy and move our pointers forward. What we're going to end up getting is 2, 1, 2, 1, 2, 1 instead of the appropriate 2, 1, 2, 1, 3, 4 because 2, 1 overrode the original 3, 4. Memmove handles that correctly. In this case, basically just always use memmove because it handles it correctly. It generally does not perform any worse. The idea is instead of starting from the beginning and copying this way like we just did here, it starts from the end and copies in, and in that case, you can never have a problem. There is no performance lost. Always use memmove. Never worry about memcopy. And that's where you're going to have to separately memmove the wrapped-around portion of your queue. No worries if not completely done. This is more difficult than stack, push, and pop. 

Anyone have any code we could work with? Even if completely incomplete? [Student] Yeah, it's completely incomplete, though. Completely incomplete is fine as long as we—can you save the revision? I forget that every single time. Okay, ignoring what happens when we need to resize things. Completely ignore resize. Explain this code. I'm checking first of all if the size is less than the copy first of all and then after that, I insert—I take head + size, and I make sure it wraps around the capacity of the array, and I insert the new string at that position. Then I increase the size and return true. 

[Rob B.] This is definitely one of those cases where you're going to want to be using mod. Any kind of case where you have wrapping around, if you think wrapping around, the immediate thought should be mod. As a quick optimization/make your code one line shorter, you notice that the line immediately following this one is just size++, so you merge that into this line, size++. Now down here, we have the case where we do not have enough memory, so we are increasing our capacity by 2. I guess you could have the same problem here, but we can ignore it now, where if you failed to increase your capacity, then you're going to want to decrease your capacity by 2 again. Another short note is just like you can do +=, you can also do <<=. Almost anything can go before equals, +=, |=, &=, <<=. Char* new is our new block of memory. Oh, over here. 

What do people think about the type of our new block of memory? [Student] It should be char**. Thinking back to our struct up here, strings is what we are reallocating. We are making an entire new dynamic storage for the elements in the queue. What we're going to be assigning to your strings is what we're mallocing right now, and so new is going to be a char**. It's going to be an array of strings. Then what is the case under which we're going to return false? [Student] Should we be doing the char*? [Rob B.] Yes, good call. [Student] What was that? [Rob B.] We wanted to do size of char* because we are no longer— this would actually be a very big problem because sizeof(char) would be 1. Sizeof char* is going to be 4, so a lot of times when you're dealing with ints, you tend to get away with it because size of int and size of int* on a 32-bit system are going to be the same thing. But here, sizeof(char) and sizeof(char*) are now going to be the same thing. 

What is the circumstance where we return false? [Student] New is null. Yeah, if new is null, we return false, and I'm going to throw down here— [Student] [inaudible] [Rob B.] Yeah, this is fine. You could either do 2 times capacity or capacity shift 1 and then only set it down here or whatever. We'll do it as we had it. Capacity >>= 1. And you're never going to have to worry about losing the 1's place because you left shifted by 1, so the 1's place is necessarily a 0, so right shifting by 1, you're still going to be fine. [Student] Do you need to do that before return? [Rob B.] Yes, this makes absolutely no sense. 

Now assume we're going to end up returning true to the end. The way we're going to do these memmoves, we need to be careful with how we do them. Does anyone have any suggestions for how we do them? Here's our start. Inevitably, we want to start at the beginning again and copy things in from there, 1, 3, 4, 2. How do you do that? First, I have to look at the man page for memmove again. Memmove, order of arguments is always important. We want our destination first, source second, size third. There are a lot of functions which reverse source and destination. Destination, source tends to be consistent somewhat. Move, what is it returning? It returns a pointer to destination, for whatever reason you might want that. I can picture read it, but we want to move into our destination. 

What is our destination going to be? [Student] New. [Rob B.] Yes, and where are we copying from? The first thing we are copying is this 1, 3, 4. What is the—this 1, 3, 4. What is the address of this 1? What is the address of that 1? [Student] [inaudible] [Rob B.] Head + the address of the first element. How do we get the first element in the array? [Student] Queue. [Rob B.] Yes, q.strings. Remember, here, our head is 1. Darn it. I just think it's magically— Here, our head is 1. I'm going to change my color too. And here is strings. This, we can either write it as we did over here with heads + q.strings. A lot of people also write it &q.strings[head]. This isn't really any less efficient. You might think of it as you are dereferencing it and then getting the address of, but the compiler is going to translate it to what we had before anyway, q.strings + head. Either way you want to think of it. 

And how many bytes do we want to copy? [Student] Capacity - head. Capacity - head. And then you could always write out an example to figure out if that's right. [Student] It needs to be divided by 2 then. Yeah, so I guess we could use size. We still have size being— using size, we have size equal to 4. Our size is 4. Our head is 1. We want to copy these 3 elements. That's the sanity check that size - head is correctly 3. And coming back here, like we said before, if we used capacity, then we'd have to divide by 2 because we've already grown our capacity, so instead, we're going to use size. That copies that portion. Now, we need to copy the other portion, the portion that is left of the start. 

That's going to memmove into what position? [Student] Plus size - head. Yes, so we have already copied in size - head bytes, and so where we want to copy the remaining bytes is new and then size minus—well, the number of bytes we've already copied in. And then where are we copying from? [Student] Q.strings[0]. [Rob B.] Yes, q.strings. We could either do &q.strings[0]. This is significantly less common than this. If it's just going to be 0, then you'll tend to see q.strings. That's where we're copying from. How many bytes do we have left to copy?>>[Student] 10. Right. [Student] Do we have to multiply 5 - 10 times the size of the bytes or something? Yeah, so this is where—what exactly are we copying? [Student] [inaudible] What is the type of the thing we're copying? [Student] [inaudible] Yeah, so the char*s that we're copying, we don't know where those are coming from. Well, where they're pointing to, like the strings, we end up pushing it onto the queue or enqueuing onto the queue. Where those are coming from, we have no idea. We just need to keep track of the char*s themselves. We don't want to copy size - head bytes. We want to copy size - head char*s, so we're going to multiply this by sizeof(char*). Same down here, head * sizeof(char*). 

[Student] What about [inaudible]? This right here? [Student] No, below that, the size - head. [Rob B.] This right here? Pointer arithmetic. How pointer arithmetic is going to work is it automatically multiplies by the size of the type that we're dealing with. Just like over here, new + (size - head) is exactly equivalent to &new[size - head] until we expect that to work correctly, since if we're dealing with an int array, then we don't index by int— or if it's of size of 5 and you want the 4th element, then we index into the int array[4]. You don't—[4] * size of int. That handles it automatically, and this case is literally equivalent, so the bracket syntax is just going to be converted to this as soon as you compile. That's something you need to be careful of that when you are adding size - head you are adding not one byte. You're adding one char*, which can be one bytes or whatever. 

Other questions? Okay, dequeue is going to be easier. I'll give you a minute to implement. Oh, and I guess this is the same situation where what the enqueue case, if we're enqueuing null, maybe we want to handle it, maybe we don't. We won't do it again here, but same as our stack case. If we enqueue null, we might want to disregard it. Anyone have some code I can pull up? [Student] I just have dequeue. Version 2 is that—okay. You want to explain? [Student] First, you make sure there's something in the queue and that the size is going down by 1. You need to do that, and then you return the head and then move the head up 1. Okay, so there is a corner case we have to consider. Yeah. [Student] If your head is at the last element, then you don't want head to point outside of the array. 

Yeah, so as soon as head hits the end of our array, when we dequeue, our head should be modded back to 0. Unfortunately, we can't do that in one step. I guess the way I'd probably fix it is this is going to be a char*, what we're returning, whatever your variable name wants to be. Then we want to mod head by our capacity and then return ret. A lot of people here they might do— this is the case of—you'll see people do if head is greater than capacity, do head - capacity. And that's just working around what mod is. Head mod = capacity is much cleaner of a wrapping around than if head greater than capacity head - capacity. 

Questions? Okay, the last thing we have left is our linked list. You might be used to some of the linked list behavior if you did linked lists in your hash tables, if you did a hash table. I strongly recommend doing a hash table. You might have already done a trie, but tries are more difficult. In theory, they're asymptotically better. But just look at the big board, and tries never do better, and they take up more memory. Everything about tries ends up being worse for more work. It's what David Malan's solution always is is he always posts his trie solution, and let's see where he currently is. What was he under, David J? He's #18, so that's not terribly bad, and that's going to be one of the best tries you can think of or one of the best tries of a trie. Is it not even his original solution? I feel like trie solutions tend to be more in this range of RAM usage. 

Go down to the very top, and RAM usage is in the single digits. Go down towards the bottom, and then you start seeing tries where you get absolutely massive RAM usage, and tries are more difficult. Not entirely worth it but an educational experience if you did one. The last thing is our linked list, and these three things, stacks, queues, and linked lists, any future thing you ever do in computer science will assume you have familiarity with these things. They are just so fundamental to everything. 

Linked lists, and here we have a singly linked list is going to be our implementation. What does singly linked mean as opposed to doubly linked? Yes. [Student] It only points to the next pointer rather than to the pointers, like the one preceding it and the one after it. Yeah, so in picture format, what did I just do? I have two things. I have picture and picture. In picture format, our singly linked lists, inevitably, we have some kind of pointer to the head of our list, and then within our list, we just have pointers, and maybe this points to null. It's going to be your typical drawing of a singly linked list. A doubly linked list, you can go backwards. If I give you any node in the list, then you can necessarily get to any other node in the list if it is a doubly linked list. But if I get you the third node in the list and it's a singly linked list, no way you're ever going to get to the first and second nodes. And there's benefits and detriments, and one obvious one is you take up more size, and you have to keep track of where these things are pointing now. But we only care about singly linked. 

A few things we're going to have to implement. Your typedef struct node, int i: struct node* next; node. That typedef should be burned into your minds. Quiz 1 should be like give a typedef of a linked list node, and you should be able to immediately scribble that down without even thinking about it. I guess a couple questions, why do we need struct here? Why can't we say node*? [Student] [inaudible] Yeah. The only thing that defines a node as a thing is the typedef itself. But as of this point, when we're kind of parsing through this struct node definition, we have not finished our typedef yet, so since the typedef has not finished, node does not exist. But struct node does, and this node in here, this could also be called anything else. This could be called n. It could be called linked list node. It could be called anything. But this struct node needs to be called the same thing as this struct node. What you call this has to also be here, and so that also answers the second point of the question which is why—a lot of times when you see structs and typedefs of structs, you'll see anonymous structs where you'll just see typedef struct, implementation of struct, dictionary, or whatever. 

Why here do we need to say node? Why can't it be an anonymous struct? It's almost the same answer. [Student] You need to refer to it within the struct. Yeah, within the struct, you need to refer to the struct itself. If you don't give the struct a name, if it's an anonymous struct, you can't refer to it. And last but not least—these should all be somewhat straightforward, and they should help you realize if you're writing this down that you're doing something wrong if these sorts of things don't make sense. Last but not least, why does this have to be struct node*? Why can't it just be struct node next? [Student] Pointer to the next struct. That's inevitably what we want. Why could it never be struct node next? Why does it have to be struct node* next? Yeah. [Student] It's like an infinite loop. Yeah. [Student] It would all be in one. Yeah, just think of how we would do size of or something. Size of a struct is basically + or - some pattern here or there. It's basically going to be the sum of the sizes of the things in the struct. This right here, without changing anything, the size is going to be easy. Size of struct node is going to be size of i + size of next. Size of i is going to be 4. Size of next is going to be 4. Size of struct node is going to be 8. If we don't have the *, thinking of sizeof, then sizeof(i) is going to be 4. Size of struct node next is going to be size of i + size of struct node next + size of i + size of struct node next. It would be an infinite recursion of nodes. This is why this is how things have to be. 

Again, definitely memorize that, or at least understand it enough that you can be able to reason through what it should look like. The things we're going to want to implement. If length of the list— you could cheat and keep around a global length or something, but we're not going to do that. We're going to count the length of the list. We have contains, so that's basically like a search, so we have a linked list of integers to see if this integer is in the linked list. Prepend is going to insert at the beginning of the list. Append is going to insert at the end. Insert_sorted is going to insert into the sorted position in the list. Insert_sorted kind of assumes that you never used prepend or append in bad ways. 

Insert_sorted when you're implementing insert_sorted— let's say we have our linked list. This is what it currently looks like, 2, 4, 5. I want to insert 3, so as long as the list itself is already sorted, it's easy to find where 3 belongs. I start at 2. Okay, 3 is greater than 2, so I want to keep going. Oh, 4 is too big, so I know 3 is going to go in between 2 and 4, and I have to fix pointers and all that stuff. But if we did not strictly use insert_sorted, like let's just say I prepend 6, then my linked list is going to become this. It now makes no sense, so for insert_sorted, you can just assume that the list is sorted, even though operations exist which can cause it to not be sorted, and that's it. Find a helpful insert—so those are the main things you're going to have to implement. 

For now, take a minute to do length and contains, and those should be relatively quick. Nearing closing time, so anyone have anything for length or contains? They're going to be almost identical. [Student] Length. Let's see, revision. Okay. You want to explain? [Student] I just create a pointer node and initialize it to first, which is our global variable, and then I check to see if it's null so I don't get a seg fault and return 0 if that's the case. Otherwise, I loop through, keeping track of within integer how many times I've accessed the next element of the list and in the same increment operation also access that actual element, and then I continuously make the check to see if it's null, and if it's null, then it aborts and just returns the number of elements I've accessed. 

[Rob B.] Does anyone have any comments on anything? This looks fine correctness wise. [Student] I don't think you need the node == null. Yeah, so if node == null return 0. But if node == null then this—oh, there is a correctness issue. It was just you're returning i, but it's not in scope right now. You just need int i, so i = 0. But if node is null, then i is still going to be 0, and we're going to return 0, so this case is identical. Another common thing is to keep the declaration of node inside of the for loop. You could say—oh, no. Let's keep it as this. I would probably put int i = 0 here, then node* node = first in here. And this is probably how—getting rid of this now. This is probably how I would have written it. You could also—looking at it like this. This for loop structure right here should be almost as natural to you as for int i = 0 i is less than length of array i++. If that's how you iterate over an array, this is how you iterate over a linked list. 

This should be second nature at some point. With that in mind, this is going to be almost the same thing. You're going to want to iterate over a linked list. If the node—I have no idea what the value is called. Node i. If the value at that node = i return true, and that's it. Notice that the only way we ever return false is if we iterate over the entire linked list and never return true, so that's what this does. As a side note—we probably won't get to append or prepend. 

Quick last note. If you see the static keyword, so let's say static int count = 0, then we do count++, you can basically think of it as a global variable, even though I just said this isn't how we're going to implement length. I'm doing this here, and then count++. Any way we can enter a node into our linked list we are incrementing our count. The point of this is what the static keyword means. If I just had int count = 0 that would be a regular old global variable. What static int count means is that it is a global variable for this file. It is impossible for some other file, like think of pset 5, if you have started. You have both speller.c, and you have dictionary.c, and if you just declare a thing global, then anything in speller.c can be accessed in dictionary.c and vice versa. Global variables are accessible by any .c file, but static variables are only accessible from within the file itself, so inside of spell checker or inside of dictionary.c, this is kind of how I would declare my variable for the size of my array or the size of my number of words in the dictionary. Since I don't want to declare a global variable that anyone has access to, I really only care about it for my own purposes. 

The good thing about this is also the whole name collision stuff. If some other file tries to use a global variable called count, things go very, very wrong, so this nicely keeps things safe, and only you can access it, and no one else can, and if someone else declares a global variable called count, then it won't interfere with your static variable called count. That's what static is. It is a file global variable. 

Questions on anything? All set. Bye. [CS50.TV]