In programming, we often need to represent lists of values, such as the names of students in a section or their scores on the latest quiz.  

In the C language, declared arrays can be used to store lists. It's easy to enumerate the elements of a list stored in an array, and if you need to access or modify the ith list element for some arbitrary index I, that can be done in constant time, but arrays have disadvantages, too. 

When we declare them, we're required to say up front how big they are, that is, how many elements they can store and how big these elements are, which is determined by their type.  For instance, int arr(10) can store 10 items that are the size of an int.  

We can't change an array's size after declaration. We have to make a new array if we want to store more elements. The reason this limitation exists is that our program stores the whole array as a contiguous chunk of memory. Say this is the buffer where we stored in our array. There might be other variables located right next to the array in memory, so we can't just make the array bigger. 

Sometimes we'd like to trade the array's fast data access speed for a little more flexibility. Enter the linked list, another basic data structure you might not be as familiar with.  At a high level,  a linked list stores data in a sequence of nodes that are connected to each other with links, hence the name 'linked list.' As we'll see, this difference in design leads to different advantages and disadvantages than an array.  

Here's some C code for a very simple linked list of integers. You can see that we have represented each node in the list as a struct which contains 2 things,  an integer to store called 'val' and a link to the next node in the list which we represent as a pointer called 'next.' This way, we can track the entire list with just a single pointer to the 1st node, and then we can follow the next pointers to the 2nd node, to the 3rd node, to the 4th node, and so on, until we get to the end of the list. 

You might be able to see 1 advantage this has over the static array structure--with a linked list, we don't need a big chunk of memory altogether. The 1st node of the list could live at this place in memory, and the 2nd node could be all the way over here. We can get to all the nodes no matter where in memory they are, because starting at the 1st node, each node's next pointer tells us exactly where to go next.  

Additionally, we don't have to say up front how big a linked list will be the way we do with static arrays, since we can keep adding nodes to a list as long as there's space somewhere in memory for new nodes.  Therefore, linked lists are easy to resize dynamically. Say, later in the program we need to add more nodes into our list. To insert a new node into our list on the fly,  all we have to do is allocate memory for that node, plop in the data value, and then place it where we want by adjusting the appropriate pointers.  

For example, if we wanted to place a node in between the 2nd and 3rd nodes of the list,   we wouldn't have to move the 2nd or 3rd nodes at all.  Say we're inserting this red node. All we'd have to do is set the new node's next pointer to point to the 3rd node and then rewire the 2nd node's next pointer to point to our new node. So, we can resize our lists on the fly since our computer doesn't rely on indexing, but rather on linking using pointers to store them.  

However, a disadvantage of linked lists is that, unlike a static array,  the computer can't just jump to the middle of the list. Since the computer has to visit each node in the linked list to get to the next one,  it's going to take longer to find a particular node than it would in an array. To traverse the entire list takes time proportional to the length of the list, or O(n) in asymptotic notation.  On average, reaching any node also takes time proportional to n. 

Now, let's actually write some code that works with linked lists.  Let's say we want a linked list of integers. We can represent a node in our list again as a struct with 2 fields, an integer value called 'val' and a next pointer to the next node of the list.  Well, seems simple enough.  

Let's say we want to write a function which traverses the list and prints out the value stored in the last node of the list.  Well, that means we'll need to traverse all the nodes in the list to find the last one, but since we're not adding or deleting anything, we don't want to change the internal structure of the next pointers in the list.  

So, we'll need a pointer specifically for traversal which we'll call 'crawler.' It will crawl through all the elements of the list by following the chain of next pointers. All we have stored is a pointer to the 1st node, or 'head' of the list.  Head points to the 1st node.  It's of type pointer-to-node. 

To get the actual 1st node in the list,  we have to dereference this pointer, but before we can dereference it, we need to check if the pointer is null first. If it's null, the list is empty, and we should print out a message that, because the list is empty,  there is no last node.  But, let's say the list isn't empty.  If it's not, then we should crawl through the entire list until we get to the last node of the list, and how can we tell if we're looking at the last node in the list? 

Well, if a node's next pointer is null, we know we're at the end since the last next pointer would have no next node in the list to point to.  It's good practice to always keep the last node's next pointer initialized to null to have a standardized property which alerts us when we've reached the end of the list.  

So, if crawler → next is null,  remember that the arrow syntax is a shortcut for dereferencing a pointer to a struct, then accessing its next field equivalent to the awkward:  (*crawler).next.  Once we've found the last node,  we want to print crawler → val, the value in the current node which we know is the last one.  Otherwise, if we're not yet at the last node in the list,  we have to move on to the next node in the list and check if that's the last one.  To do this, we just set our crawler pointer to point to the current node's next value, that is, the next node in the list. This is done by setting  crawler = crawler → next.  Then we repeat this process, with a loop for instance, until we find the last node. So, for instance, if crawler was pointing to head, we set crawler to point to crawler → next, which is the same as the next field of the 1st node. So, now our crawler is pointing to the 2nd node, and, again, we repeat this with a loop, until we've found the last node, that is,  where the node's next pointer is pointing to null.  And there we have it, we've found the last node in the list, and to print its value,  we just use crawler → val.  

Traversing isn't so bad, but what about inserting? Lets say we want to insert an integer into the 4th position in an integer list.  That is between the current 3rd and 4th nodes.  Again, we have to traverse the list just to get to the 3rd element, the one we're inserting after.  So, we create a crawler pointer again to traverse the list, check if our head pointer is null, and if it's not, point our crawler pointer at the head node.  So, we're at the 1st element.  We have to go forward 2 more elements before we can insert, so we can use a for loop int i = 1; i < 3; i++ and in each iteration of the loop, advance our crawler pointer forward by 1 node by checking if the current node's next field is null, and if it's not, move our crawler pointer to the next node by setting it equal to the current node's next pointer.  So, since our for loop says to do that twice,  we've reached the 3rd node, and once our crawler pointer has reached the node after which we want to insert our new integer,  how do we actually do the inserting? 

Well, our new integer has to be inserted into the list as part of its own node struct, since this is really a sequence of nodes. So, let's make a new pointer to node called 'new_node,'  and set it to point to memory that we now allocate on the heap for the node itself, and how much memory do we need to allocate? Well, the size of a node, and we want to set its val field to the integer that we want to insert.  Let's say, 6.  Now, the node contains our integer value.  It's also good practice to initialize the new node's next field to point to null, but now what? 

We have to change the internal structure of the list and the next pointers contained in the list's existing 3rd and 4th nodes.  Since the next pointers determine the order of the list, and since we're inserting our new node right into the middle of the list, it can be a bit tricky.  This is because, remember, our computer only knows the location of nodes in the list because of the next pointers stored in the previous nodes.  So, if we ever lost track of any of these locations,  say by changing one of the next pointers in our list,  for instance, say we changed the 3rd node's next field to point to some node over here.  We'd be out of luck, because we wouldn't have any idea where to find the rest of the list, and that's obviously really bad.  So, we have to be really careful about the order in which we manipulate our next pointers during insertion.  

So, to simplify this, let's say that our first 4 nodes are called A, B, C, and D, with the arrows representing the chain of pointers that connect the nodes.  So, we need to insert our new node in between nodes C and D.  It's critical to do it in the right order, and I'll show you why.  

Let's look at the wrong way to do it first.  Hey, we know the new node has to come right after C, so let's set C's next pointer to point to new_node. All right, seems okay, we just have to finish up now by  making the new node's next pointer point to D, but wait, how can we do that? The only thing that could tell us where D was, was the next pointer previously stored in C, but we just rewrote that pointer to point to the new node, so we no longer have any clue where D is in memory, and we've lost the rest of the list.  Not good at all.  

So, how do we do this right? First, point the new node's next pointer at D. Now, both the new node's and C's next pointers are pointing to the same node, D, but that's fine. Now we can point C's next pointer at the new node.  So, we've done this without losing any data.  In code, C is the current node that the traversal pointer crawler is pointing to, and D is represented by the node pointed to by the current node's next field, or crawler → next.  So, we first set the new node's next pointer to point to crawler → next, the same way we said new_node's next pointer should  point to D in the illustration.  Then, we can set the current node's next pointer to our new node, just as we had to wait to point C to new_node in the drawing.  Now everything's in order, and we didn't lose track of any data, and we were able to just stick our new node in the middle of the list  without rebuilding the whole thing or even shifting any elements the way we would have had to with a fixed-length array.  

So, linked lists are a basic, but important, dynamic data structure which have both advantages and disadvantages compared to arrays and other data structures, and as is often the case in computer science,  it's important to know when to use each tool, so you can pick the right tool for the right job. 

For more practice, try writing functions to delete nodes from a linked list-- remember to be careful about the order in which you rearrange your next pointers to ensure that you don't lose a chunk of your list-- or a function to count the nodes in a linked list, or a fun one, to reverse the order of all of the nodes in a linked list.  

My name is Jackson Steinkamp, this is CS50.