Singly Linked Lists

We get the size of the memory to allocate from sizeof *link (when link points to a struct link, it is the size of the struct). The sizeof operator cannot give us overflow—if you can represent a struct at all, then you can malloc() size for it. So, there is no need to worry about overflow, but of course we can still get an allocation error, so malloc() can return NULL, in which case we have to give up. We return a NULL pointer in return, so the user can handle the error. Otherwise, we set the value and next members.

Since C evaluates the function arguments before it calls a function, we will first evaluate new_link(3, 0) which creates a link with value 3 and a NULL pointer for next; see the top-right corner of Figure 11-1. Here, I have drawn the NULL pointer as a pointer that ends in a short line. I will generally draw NULL pointers that way or, when figures would otherwise get too messy, leave them out entirely. When illustrating data structures, I will draw the individual structs as boxes and the pointers as arrows.

we have a problem if any of the allocations fail. If the first allocation, new_link(3, 0), fails, we end up with a list of 1 and 2 instead of 1, 2, and 3. Not what we want, but not as bad as it could be. If one of the other new_link() calls fails, however, it is slightly worse. The failed call will look like an empty list, since the function returns NULL, but the input to the function call is an allocated link. If the function call fails, we lose access to that memory. Our program no longer has a pointer to it, and we have no way of getting one either, and so we cannot free() it. We should probably be more careful.

In the while-loop, list is a pointer that is either NULL (in which case we are done and leave the loop) or it points to a valid link. We need to free the link, but we also need to continue with its next pointer. If we free the link first, then we no longer have a valid pointer to the link, and thus we cannot safely get next, so we extract next first, then we free, and then we continue the loop.

It is the same pattern, and almost all loops through a list will follow this pattern.

It constructs the list from the array backward. Remember that new_link() prepends the new element to the list, so if we ran through the array from left to right, we would get a list with the elements in reverse. The variable list holds the head of the current list, and we update it to link at the end of the for-loop’s body, where we know that the allocation was successful.

There is no avoiding having to find the last link in the chain if we want to append. With a singly linked list, we only have direct access to the first link in the chain (but we will fix that later in this chapter with doubly linked lists). So, we need to search through as many links as there are. We cannot use the while (list) pattern now, however, because then when we find the end of the list, list will be NULL, and we are one past the link we want. We must find the last link, which is the link where next is NULL. So, we must use while (list->next) to get that. In the code, I have named the variable last to indicate that it is the last link we are searching for. However, this won’t work if we start out with a NULL pointer. Then we would dereference a NULL pointer when we write last->next, and that is undefined behavior (and almost guaranteed to crash our program). We have to handle an empty list as a special case.

If we append to an empty list, we want a list with a single element, so if the input to append() is NULL, we return a new link (with 0 as its next pointer). Otherwise, we can search for the last link, and once we have it, we can allocate a new link and make the next pointer in the last link point to it; see Figure 11-2. In the figure, the original link is the one from Figure 11-1, with three links, 1, 2, and 3, and we append 4 to the list.

That means that we create a new link for 4, with NULL for its next pointer, and then we change the old next pointer for link 3 (shown as a dashed pointer), so it is no longer NULL but points to the new link.

The allocation, however, can fail. We can still assign the result of the allocation to the last link’s next pointer—if the allocation fails, it then remains NULL—but we need to report the error. So if the allocation fails, we will return a NULL pointer. Otherwise, we return the original list. By returning the original list, we get the rule that append() either returns NULL, in case of an allocation failure, or returns the result of appending a value to a list—the list we get by appending the value to the input list. If the input is empty or contains values, we get the same result—the updated list.

The make_list() function can return a NULL pointer, so list1 might be NULL. If it is, then list2 is a completely new list. If it isn’t, and append() didn’t fail, then list1 and list2 are pointers to the same list. So, should you free() both lists or just one of them? If they are the same, you can only free one. If they are different, you must free both. You can test if they are the same, of course. This isn’t the most difficult issue that will come up with memory management in this section—it gets worse, but we will alleviate it with a small change to the code in the next section. Still, it illustrates that we have to worry about assigning the result of an append to a new list.

If list1 is NULL, everything is fine. We prepend a link to it to get list2, and we can free both the NULL pointer in list1 and the link in list2. But if list1 has a chain of links, then list2 (if the prepend() succeeded) consists of one link and then a list that is shared with list1. When we free list1, we free all the links after the first in list2, so when we call free_list(list2), we can safely free the first link, but all the remaining are already gone. If we try to free() them, we get undefined behavior (and it won’t lead anywhere pleasant). Here, the problem isn’t that prepend() can sometimes give us a new list and sometimes an old list, but that it will provide us with a list where all but one link is shared with the old list. (Again, we will improve upon it in the next section.) I just want to show you the problems in a straightforward solution first, so you recognize that they exist, and will be careful in the future, and not conclude from a better solution that things are simple and that there is nothing to worry about. There most certainly is.

We will need to find the last link in the first list to add the second list to it, so we have a special case if x is empty. If it is, we return y. The concatenation of an empty list with another is the links in the second list, so that will work. Otherwise, we find the last link, and by setting its next pointer to point to the first link in y, we have concatenated them.

you now have three pointers to links, list1, list2, and list3. The list2 list is unchanged. It doesn’t matter if it was empty or not; we have not changed any of its links; we have just made the last link in list1 point to it. That is, we have made the last link in list1 point to it, if list1 wasn’t empty. If list1 was empty, then list3 is an alias for list2. If list1 was not empty, then list3 is an alias for (the modified) list1. This, of course, is an issue when we need to free the lists. If we free list2, then we have freed the tailing links in list2 (and list1 if it wasn’t empty). If we free list1, and it was empty to begin with, then we haven’t freed anything (because free(0) doesn’t do anything). But if list1 wasn’t empty, we have freed all three lists. We have freed list3 because it is an alias for the modified list1, and we have freed list2 because free_list() will free all the links in the list, and that includes those we got from list2. The only safe option is to free list3 and never list1 and list2 after appending them.

After appending two lists, you are best off by considering the input gone, and never look at it again. The first argument, unless empty, is modified, and the second argument is something you cannot safely free. If you do not want a concatenation operation that, in this way, destroys the input, you should program a version that makes a copy of the two lists instead. To test your understanding of linked lists, this is another good exercise that I recommend that you do.

It is a simple approach to implement the operation, but it is not a particularly good idea. The new_link() allocation can fail, and concatenate() won’t notice. So, we simply add allocation errors to the concatenate() function that is problematic enough as it is. It is not a bad idea to implement one operation using another in general, of course, but this particular choice is a poor one.

Figure 11-3 shows the steps in the function, when run on a list with the values 1, 2, 3, and 4, in that order. The original list, with its four links, is shown in A). In B), we have the pointers we set up before the while-loop. We have a special case if the input list is empty, since we will need to be able to refer to the next link in the list, and there isn’t one if it is empty, so we handle that before we get to this point. If the list isn’t empty, we get a pointer, next, to the second link in the list, we make reversed point to the first link, and we set the first link’s next to NULL. The reversed pointer will hold the reversed list, and the reversed list must end with the first link in the input, which is what it does at this point. An invariant in the loop will be that reversed holds the reversed links of those we have processed so far. The first link’s next pointer is set to NULL because reversed should end after that link. The old pointer values are shown as dashed lines and the new and unchanged pointers as solid lines.

Now we start the while-loop in C), and in it we get hold of the next link’s next value. We need it to continue the loop later, where we have changed the link that next points to. We only need it for that, so we do not do anything with next_next yet. Now, we get hold of the link that next points at, however, and prepend it to reversed. Prepending it to reversed makes it the first element in the list of reversed links so far, which upholds the invariant. The way we prepend is through updating pointers. The next link’s next pointer should point to reversed (changing it here is the reason we needed next_next), and reversed should point to next so that the link is now the front of the reversed list.

When we move to D), we first update next, so it points to the new next link. We do it at the end of the loop body, but in the figure I have listed it as the first statement in the code since it is a change we make between C) and D). We now do the same operation as we did to get to C). We prepend the current next link to reversed, remembering the next->next link in next_next. After that, reversed holds the values 3, 2, and 1 (if you follow the solid lines from what reversed points to, that should be clear). In E), we handle the last link. Here, next_next becomes NULL, so we terminate the while-loop when we are done, and reversed holds the reversed list.

Manipulating pointers like this is an integral part of working with recursive data structures. The example is the most complex we will see in this chapter, but it is not unusually so. If you need to manipulate a data structure in a nontrivial way, it helps to draw how you want to rearrange the pointers, like in the figure. It can get complicated, but drawings help immensely.

It is a recursive solution that says that deleting all occurrences of val in an empty list is the empty list (what else would it be?). If the first link’s value is val, then the result is what we get from deleting val from the rest of the list, and finally if the first value is not val, then the result is the current value followed by the result of deleting val from the rest of the list. Here, “followed by” is handled by assigning the result of the recursive call to the current link’s next pointer. In the case where we delete a link, we get its next pointer before we free(), since otherwise we would need to dereference to a deleted link, which is undefined behavior.

then is list now a valid pointer? That depends. If the first link in list had the value 42, we have deleted that link, but list still points to it. It points to a deallocated chunk of memory, so it is not valid. If list was empty, or didn’t have 42 in its first link, then list now holds the updated list where all occurrences of 42 are deleted.

because you get the updated list back. It might be the same address as the input, when we do not delete the first link, but if we do get a different address back, it is the list without 42, which is what we want.

To sum up, in this section, we have seen how we can implement a recursive data structure, a singly linked list, using a struct with a member that is a pointer to the same struct’s type. We have also seen how we can implement various operations on the type. Although the data structure is simple, we have learned that there are many potential pitfalls with memory management. We have to deal with allocation errors, but that is the least of our worries. The real problem is freeing memory correctly once allocated.

Correctly freeing memory is practically always a concern with recursive data structures. The problem is that they tend to create aliases for the same memory. Here, when we concatenate, for example, we end up with one reference to the tail part of another list. If we delete the list through the tail reference, then the chain of links from the front will eventually run into freed memory, and we cannot handle that. If we free from the front, then the original reference to the second list will point to freed memory.

While such aliasing is sometimes unavoidable, we can often alleviate it with a better interface to the operations, and we will do that in the next section. The interface we have implemented here is horrible when it comes to safe memory management, I admit. But I wanted to show you a lousy solution before I showed you a good one, so you would be aware of the problems and appreciate the solution.

The solution in the next chapter involves a (very) slight change to how we represent lists, and naturally given the topic of the book, it involves a pointer. Then practically all our problems go away. In Chapter 15, we will see another approach to dealing with aliasing between recursive data structures.

Adding a Level of Indirection

The leading cause of our troubles with memory management was that our operations returned new lists that potentially referred to links the input also referred to. We can change the implementation such that we modify the input instead of returning new lists. We won’t have to create new copies for each list that we return, but we will implement the operations such that we do not create more than one list with a pointer to the same link. When we prepend or append, we update the existing list; when we concatenate, we move the links from one list to another, so the second list no longer holds them. This isn’t possible with the representation we used so far for lists—a pointer to a link—for two reasons. We cannot modify the calling variables, so they no longer point to a function’s input, and we cannot modify an empty list, represented as a NULL pointer. The solution to both is one level of indirection: a list will no longer be a pointer to a link, but a pointer to a pointer to a link.

We allocate a list at the beginning, to get that over with. If the allocation fails, we will have to report an error, so we might as well do that up front. After that, we can use the list’s links as we used the link pointer in the previous version. It is initially the empty list, and as we update it, we add the links to the list. The code is exactly as before, except that we have to free the entire list if we get an allocation failure. We call free_list() to do that. We also called free_list() in the previous version, but that function only deleted links—we had no distinction between lists and links there—but you cannot use the free_links() function here.

If we successfully allocate all the links, we return the list, and here we have improved upon the interface of the previous function. With the make_list() from the last section, we could not distinguish between a failure and an empty list. We could, of course, check n before we called the function and that way determine if we expected to get an empty list back, but both empty lists and errors would give us NULL pointers. With our new representation, NULL is not an empty list and vice versa. An empty list is a pointer to a NULL pointer, and that is different from a NULL pointer. The new make_list() function gives us NULL if we have an error, and a list otherwise, and an empty list cannot be confused for NULL.

Could we get such an operation? Not quite, but very close.

Since last_next() gives us the address where we should write val_link or y’s links, we need to dereference before we assign, thus the *last_next(x) expression.

I will wait with implementing these two functions again until the next section, though. There, we try a slightly different representation, and I can cut off a line or two in the implementation because of that. It is a very minor change, however, so if you are up for it, you should give the functions a go now, before you read on.

Adding a Dummy Element

Adding a level of indirection solves many problems, but a related trick in my experience solves many more. If you have a data structure where you need to deal with special cases, such as empty lists represented by NULL pointers, more often than not, the special cases go away if you add one or more “dummy” elements to the structure. If you write code where you need to test that one or more pointers are NULL or not, quite often you can make the code simpler by assuring that they are not NULL. Add objects to the data structure that do not represent real data, but are there as dummies.

Singly linked lists are simple, so we won’t gain much from trying them here—we got most of the benefits in the previous section where we changed lists from pointers to links to pointers to pointers to links—we got rid of NULL as the representation of empty lists. So, the approach might underwhelm you in its usefulness. We gain a little more in the next chapter, but you will have to take my word for it when I say that for complex data structures, you can often gain a lot. We won’t have room for sufficiently interesting data structures in this book for me to show you. In any case, even if we only gain a little, you will see that with a simple dummy element at the beginning of each list, we gain all the benefits we got in the previous section, and in a few places, we write slightly simpler code.

Well, on with it. A list is once again a pointer to links, but we will never accept that a list is NULL, unless it is to return an error from a function. Instead, a list consists of one element that we do not consider part of the data it holds. It is a “head” or a “dummy” link. If you allocate a list, you allocate a link. If you put a list on the stack, you put a link on the stack (and then work with its address as the list). But the first link is not part of the real data.

Here, we didn’t gain much over the second list representation, but I find this code more readable, and it is a step up compared to the first implementation we made. If we had gone directly to the dummy link solution, you would probably agree that we gained something going here.

We could also have used this algorithm without the dummy element (I left implementing delete_value() as an exercise in the previous section, and you can try implementing this solution). Without the dummy element, however, it is harder to set the first front pointer.

We started out with simple code for a linked list, but with various issues related to memory management. We resolved those issues by adding a level of indirection, so lists became more than pointers to links. That first step helped us remove aliases between links that could potentially be disastrous when freeing memory. If we are careful with how we write functions, we can avoid them, as long as we can modify our input lists. Adding a dummy element to the beginning of each list didn’t add much on top of that, yet still I will suggest that you always reach for a dummy element when you need a level of indirection. You get the indirection for free—you already have all the code needed to work with real elements, and you can reuse it for dummy elements—and you usually avoid a few special cases for free when you take that approach.

We got rid of memory management issues by removing the chance of aliases through different references, but this is, of course, only an option when we do not need different variables to share data. If you cannot avoid that multiple variables or structures refer to the same allocated data, you must have a strategy for how to delete it. The right strategy can be highly application dependent, but we will see some general approaches later in the book. For now, as long as our functions do not leak memory and leave the input and output in a consistent state that the user can rely on, we will be satisfied.

Doubly Linked Lists

With singly linked lists, we have immediate access to the first link in the chain, and we have to search through the list to access others. If we need to delete a link, we need to have a pointer to the link that goes before it and the link that goes after it, so we can connect those. We have access to the next link through the next pointer, but the previous one is something we must keep track of as we search through the list, or we must find it by searching from the beginning. Inserting a new link y after another, x, is easy. We simply need to point y->next = x->next and then x->next = y. But inserting y before x requires that we have access to the link before x (so we can insert after that link), which again requires that we have a pointer to it from whatever algorithm we are implementing, or that we search for it. With doubly linked lists , we keep track of both the link before and after any given link. We have two pointers, prev for the previous link and next for the next link.

With two pointers, we have more special cases to worry about. Either or both of the pointers can be NULL, so a straightforward implementation leaves a lot of case checking. However, as I hinted in the previous section, adding dummy elements can greatly reduce the need for special cases. If we add a dummy link at the beginning and end of each list (see Figure 11-4), all the real links always have non-NULL prev and next pointers, and that makes it very easy to manipulate lists.

As long as a link pointer isn’t NULL, its prev and next pointers aren’t NULL either. That means that we can access the data in neighboring links, and as long as those aren’t dummy links, their prev and next pointers aren’t NULL either.

This isn’t perfect, though. We don’t have to check if a link’s prev and next are NULL, if it is a real and not a dummy link, but there are cases where we need a link’s neighbors to also have non-NULL prev and next links. That means that we have to check if the neighbors are dummies, which leaves almost as many special cases to check for. Our code will get simpler if we can ensure that even the dummy links have neighbors, but what should we make them point to?

A simple solution is the so-called circular list . We will use one dummy link per list, called head. Its next is the first real link in the list, and its prev is the last real link in the list. If the list is empty, the head’s two pointers point to the head itself; see Figure 11-5. With this representation, all links have neighbors.

A circular list doesn’t have to have a dummy element as its head, and some algorithms and data structures depend on circular lists where any link can function as the head (so we can move the head to adapt to data we process). For our purposes, however, having a dummy is easier, as it gives us a representation of empty lists that isn’t a NULL pointer.

to create a head for an empty list.

This doesn’t free the links it holds, however, so we need code to do that first, if we need it.

It also clears the head, that is, sets it to an empty list, so we don’t risk accessing deallocated links after we have freed them.

This is a macro, so we can set the list pointer to NULL after we have freed it. That can make the code safer at times, but of course only if x is the only reference to the list. But it should be, if we free it, so greater problems are present if that isn’t the case.

Use free_links() if you have a stack-allocated head, but free_list() if you have allocated the list on the heap.

Link Operations

When we connect x and y, we move the next pointer in x to y, and we lose access to the links that followed x; see Figure 11-6. Likewise, we lose access to the links preceding y when we point y->prev to x. The link before y still points to y with its next, and the link after x still points to x with its prev, but unless we have access to those links from somewhere else, they are lost to us (which means we would leak memory if we didn’t handle this correctly). As the figure also illustrates, it is quite possible to put links in an inconsistent state, where for a link x, x->prev->next != x or x->next->prev != x. This is something we should avoid doing in our code, but intermediate states in an update often look like this.

But now you get a copy of that in any compilation unit that includes the definition, including the linkage symbol, and that will certainly give you linker errors!

Instead, and this is the standard solution, you can declare an inline function static, as I have done. If so, if the function isn’t inlined, the compiler will generate a function, but it will only be visible from within the compilation unit, so you don’t get linker errors. However, you do get duplicated code for everything that the compiler doesn’t inline. It isn’t perfect, and you can set up your compilation environment to do better, but it suffices for us here.

It ensures that x at least is in a consistent state with respect to its neighbors.

This code exploits that x has a next link that we can update. If next or prev pointers could be NULL, we would have to handle special cases. Because we have a dummy head, this is not an issue.

This assumes that x has a prev link, which is a valid link, but this is also guaranteed by the dummy link. Of course, both x and x->prev might be the dummy, but the code doesn’t look at the value we store in the links, so it doesn’t care. A link is a link, as far as this code is concerned.

`

The time we could gain from inlining is small compared to the overhead there is in allocating memory, so there would be little gain in inlining here.

Except for allocating a new link, there isn’t much new here. We use connect_neighbours() instead of insert_after() because we have already set the new link’s neighbors in the allocation, but we could just as easily have called insert_after().

This is just a wrapper around insert_val_after() where we get the prev link from before. There is no need for a function here.

If we want to remove a link from a list, we should make its previous and next links point past it; the previous link’s next should point to the link’s next, and the next link’s prev should point to the link’s prev (see Figure 11-8).

We will leave the link’s pointers alone, so they still point to the original previous and next link. After we have unlinked it, it might still be useful to have access to them, even though the link is no longer part of the list.

List Operations

We didn’t have to define these macros, of course. We could equally well have used the existing. But giving them alternative names can make the intent of our code more explicit. A drawback is, of course, that compiler errors might get harder to read, as the compiler will have to explain the expansion of macros when it encounters an error. So it is a question of taste which you prefer.

We allocate the head as the first operation (and report an error if we couldn’t). After that, we append the array elements one by one. If there is an allocation error in the append() operation, we free the list and return NULL. Otherwise, we have successfully created the list and can return it.

When we have to run through all the links in a list, things are a little different. We start with the head of the list, as we did when we introduced a dummy for the singly linked lists. That doesn’t change. We can get the first link we need to look at using the front() macro that gives us the next link in the head. But where we earlier continued iterating through next pointers until we hit NULL, we need a different termination condition. With a circular list, we never reach NULL. When we are done with all the links, we will have returned to the head of the list. That is what we must compare each link against.

We get the first link with front(x). If the list is empty, we will get the head back, so it is possible that link == x. When that happens, we never enter the loop, which is what we want. If there are no elements in the list, then we shouldn’t print any. If link is not x, we iterate. We print the current value and move link to the next link. Once link progresses all the way back to the head, the loop condition link != x is false, and we terminate.

To concatenate two lists, x and y, putting the result in x, we must connect the last element in x, last(x), to the first in y, front(y), and then connect the last link in y, last(y), to x; see Figure 11-9. In A), we have the two lists before the operations. When we connect last(x) to front(y), we go to B). Both x and y are in inconsistent states because their last(x) and front(y) links do not point back to them, but that is fine. We don’t need consistency yet. We connect last(y) to x, C), and now x->prev points to last(y), and if we follow the links from x along the circle, we go through all the links from x and y and end up in x when we have seen them all.

Getting the last elements is faster with circular lists than with the singly linked lists we had in the previous section. There, getting the last link in a list took time proportional to the number of links in the list, but here it takes constant time. Concatenate is thus a constant time operation with our current lists, whereas it was a linear time operation before.

We don’t delete y, but we empty it. The caller must free it if they no longer need it. We could free it here that just changes the API. It is a design choice.

This process looks like something that would have special cases if x, y, or both are empty, since then there is overlap between the various front(), back(), and head links. By luck more than design, this isn’t the case. The same procedure works when one or both lists are empty. Consider the case where x is empty, and thus x = back(x); see Figure 11-10. When we connect back(x) with front(y), we move x->prev so it points at front(y), and front(y)->prev points to x. This doesn’t change back(y), and when we connect back(y) to x, x->prev becomes back(y), and once again we have a circle of all the links starting and ending in x (and an inconsistent y that we clear at the end).

If y is empty (see Figure 11-11), y = front(y) = last(y). We connect last(x) to front(y) = y and get the case in B), where last(x)->next points to y and y->prev points to last(x), which makes last(x)=last(y) (remember that last(y) is the link that y->prev points to). Then, when we connect last(y) to x in C), we point last(x) back to x (x->prev to last(y) which it was pointing to already). The y list is broken, which is always the case after concatenation, but x is back in its original state, which is what we want when we concatenate it with an empty list.

If both lists are empty, Figure 11-12 A), connecting last(x) to front(y) means pointing x->next to y and y->prev to x, B). That makes back(y) = x, so when we connect back(y) to x, we set x->next back to x, and we are back where we started with respect to x. We once again broke y, but who cares about y?

Cases where either list consists of one element do not need special treatment either. If front(x)=last(x) or front(y)=last(y), we only touch one of their pointers in the connect() operations, and the concatenation works as if they were different links.

Deleting all occurrences of a value is similar to the singly linked case, except that we do not need to keep track of the previous link, so we can remove one. Each link already has a pointer to the previous link, and unlinking and deleting individual links is easy. You still need to get the current link’s next pointer before you delete it, though, because once you have freed a link, you cannot get their content.

1

2

When we swap the prev and next pointers in a link, we leave the list in an inconsistent state. The link’s neighbors do not point back at it. However, if we swap all the way around the list, we will have a consistent, reversed, list. Consider the example in Figure 11-13 where we reverse a list containing elements 1, 2, and 3. The next pointers are drawn as solid lines and the prev pointers as dashed lines. To read the links in order, you follow the solid arrows from front(x) and back to x. In A), before we reverse the list, you get 1, 2, and 3. Now, when reversing, we start by pointing p at x, A), and flip its prev/next to go to B). The flipped pointers are shown as thicker lines. To get to the next link, we cannot use p->next—it would take us to last(x) and not front(x)—but we can take p->prev to get to its previous next. It will take us to the link containing 1, and we are in the state in B). At this point, the list is not in a consistent state. From p, we can follow next pointers around the links we haven’t processed until we get to x, but the link x doesn’t match its neighbors. We will fix that as we process the links.

Once again, we switch p->next and p->prev, and we end up in C). We still have the unprocessed links in front of us—good because we need to process them—and the links x and 1 are correctly wired; 1 is last(x), which it should be in the reversed list, and 1’s next pointer connects it to x. The links between 1 and 2 are not wired correctly, but when we move on to D, they will be. Generally, from p->prev, we can follow next pointers back to x, and get the processed links, in reverse order from where we started. The links following p, i.e., the links we visit if we follow next pointers starting at p, gives us the unprocessed links in the original order. As we move on, and in the example that is the last step, we flip the pointers in link 3 to go to E), and now we have a consistent list. For all links q, q == q->prev->next and q == q->next->prev, and from x, we can run around the circle to get all the links. But since all the links were swapped, we run around the circle counterclockwise, and we get the links in reversed order.

If we start with an empty list, we still swap x’s prev and next pointers, since we use a do-while loop rather than the usual while loop. We use the do-while because we do not want to terminate at the first link, which will be x. This, however, is not a problem. If x is empty, then swapping prev and next gives us the original (empty) list back.

The only complication with copying is that we need to deal with allocation errors. That means that we need to check if the head is successfully allocated, and we need to check the status of each append(). If we see an error from append(), we must free the list we have already created before we return NULL, so we do not leak memory.

The test (p == x) && (q == y) is true if we reached the end of both x and y, and false otherwise.

Sorting Doubly Linked Lists

There is nothing particularly special about sorting doubly linked lists, so this section is not here to teach you anything new about sorting. But sorting linked lists involves moving pointers around, and so it serves as an excellent excuse to learn more about that. With linked lists, we cannot access elements in constant time, as we can in an array, so we cannot use every algorithm for sorting, but many of the classical algorithms still work, and we will see some of those.

We iterate until p->next hits x. Usually, we stop when p reaches back to x, but in this case, we want to compare two consecutive links, and we do not want to compare a value with the dummy head, so we stop one link early. In the iteration, we check if the current value is larger than the next. If it is, those two links at least are out of order, and the list isn’t sorted. If all links are smaller or equal to the next, then the list is sorted.