Now let's look at list processing in detail and provide a significant number of operations on linear Linked list whose operations will include: Count, so that will tell us how many elements are in the list. Concatenate, that'll take two lists and link them together. Insert, that will put an element into a list, and delete, that will remove an element for list. Those are four of the fundamental operations on lists, and it'll let us get more practice with both pointers, recursion, lists processing, and in some cases, allocation off the stack namely using malloc as well. So let's start with count. That's very simple. Count is going to work at by just navigating through a list and each time through we'll add one as we go along until we get to the sat null link which is null link, and we can do this by recursion or by iteration but I'm going to show it through recursion and you should be able to go off and write it iteratively as well with something like a while statement. So recursion. If we're at the null, that will be the base case, and that means, for example, if we had an empty list, the list is of length zero. But if the head of the list isn't empty, then we add one and then we move to the next element in the list. Then recur by calling count again. So there'll be a one added each time through each element until we get to the end. Very trivially that all recursively count the length of a list. A little more nontrivial application, which we will also do recursively is to do concatenation, and while that's a little bit of a poor drawing, sorry for it, make your own. There's two lists h1 and h2. H1 is non-empty, and we're concatenating h1 to h2, and that means h1 is going to chain along until it gets to this null pointer, and that sits next here, and rather than go off to null which is the end of list one, we're going to instead link it up to what was h2. So that's how we'll concatenate list one to list two. We've done an assert. Remember asserts are a macro sharp define which does a test and we'll abort if the condition isn't true. This in some sense is a precondition which is saying, the first list pointed at by h1 is not null, if that is not null, we chain and we find null. Each time through the recursive step, we keep concatenation until we hit null. In which case, we take h1 next and link it to h2. Just as we said in the above diagram, and that now concatenates. So again, very straightforward to do especially if you understand recursion. So again, h1 in that form of concatenation must be pointed at a non empty lists. But again as an exercise, if you understand this material you should be able to make it works even if h1 is empty. In which case, you should just report h2 as the beginning of the discarded list. So you could test on h1 being empty, and if h1 is the null list just return the second list and you could add that so it would work in either case. Now, let's look at the insert of an element. So I'll have a particular element that we'll want inserted at a particular position, and that'll be between a p1 and a p2. So somewhere, for example we might search this list and look for a particular element if it was alphabetized, and we need to add another record alphabetized by something in this field, and when we find p1 and its adjacent element p2, we're going to take the element pointed out by queue and shove it in the middle. Notice this will be a lot simpler operation than to do something equivalent with an array. So lists have value and can improve on efficiency when certain kinds of operations are needed that are difficult or expensive for array operations. So here's how to do the insert. First, the last element, the element to insert, we assert that p1 next is p2, so they're adjacent elements, then we say p1 next pointed q, q next point should p2, and we're done. The element's been inserted. We're going to leave delete for our next video where we'll show delete in real code.
