Hi again, welcome to another episode of my suffering in CS261 at Oregon State University :)
Today, I actually wanted to talk about a pretty fun (but frustrating) problem: implementing a circular doubly linked list in C!
A Circular Doubly Linked List???
So we implemented a doubly linked list in the prior post. What is the difference between that and a circular doubly linked list?
As the name implies, the circular doubly linked list is circular, which is to say that there is one sentinel as opposed to two, and the single sentinel points to both the beginning and end of the circular linked list. If you started at the sentinel (or theoretically any link for that matter) and started traversing in either direction, eventually, you would get back to where you started!
Ok… how do we do this?
Let’s define the structs first:
Pretty familiar stuff. In fact, this is “simpler” than the doubly linked list we already implemented since we only have to deal with one sentinel!
Initializing and creating the circular linked list is also pretty familiar:
The key difference here with the circular doubly linked list is that the single sentinel begins by pointing to itself in both directions.
So if you go to the
prev pointer, you end up back at the sentinel.
Let’s write a function to create a link (but not add it) to the circular linked list.
Now that we have this function, we can write a general function to add a new link to the circular linked list.
We will call this function
addLinkAfter, which will create a new link containing a specified value and add it after a specified link in the list.
The first chunk of code is creating a new link and specifying the pointers of the new link so that it points backwards to the exisiting link we are adding after and points forwards to the existing links
The second chunk is making sure that the currently existing link and the current link that is after it play nicely with the new link and point towards it in the circular linked list.
So far, pretty straightforward!
The last function we want to implement is the
This function is a little spicier.
A practice that I have been using in CS261 is to create temporary pointer variables such as
tmp here that allows me to manipulate values while still having a copy of the original (since C is pass by value).
I could have just skipped the line defining
tmp and just used
link instead for moving the pointers, but in more complicated functions I think this runs the risk of changing something you don’t necessarily want to change.
Finally, let’s write a function to destroy the circular list after we are done with it:
Here is an example of where it is helpful to have a
tmp variable defined since we don’t want to call
removeLink on our
current pointer since that will free all the memory, including the pointer to the next link.
If we instead keep
current to keep iterating along the circular list and
tmp for removal and freeing memory and make sure the
current is always ahead of
tmp, we won’t run into this issue.
Finally, let’s write two useful helper functions like we did for the regular doubly linked list:
Instead of using an
assert in the
We’ve finished implementing all the basic functions of the circular linked list!
Deques with a Circular Doubly Linked list
As we’ve done for previous data structures, we can now use the circular linked list to implement some abstract data structures.A Let’s start off by implementing a deque. Recall that the deque needs several functions:
Front(just look at the front element)
Back(just look at the back element)
Thankfully, most of these are pretty easy since we can just use the functions we’ve already written!
add functions, the positioning is all based around the sentinel.
When we add to the front of the deque we are adding a link right after our sentinel.
When we add to the back, we are adding a link right after the previous link of the sentinel.
We can follow the same logic for the other functions!
The key bit with the remove functions is that we have to make sure the size of the circular linked list is greater than 0. Otherwise, we’ll end up removing the sentinel itself and that would be bad news for us!
Reversing a circular doubly linked list
Now we get to the real fun part: reversing the list!
What is our goal with this? We know that with our circular linked list, if we start in one direction from the sentinel, say forward, we can access all the elements in the list in a certain order before returning back to the sentinel. After we reverse it, now if we travel in the opposite direction, we’ll now access the elements in the same order as when we traversed it forwards.
This sounds tricky because it is.
But it’s not impossible, and the function itself is actually pretty short!
The trick is to define a
tmp and a
current, kind of like what we did when we wrote the
destroy function above.
tmp stays one link ahead of current.
As we traverse the circular list, our goal at every link (defined as
current) is to switch the
next pointers with one another.
However, if we don’t have another pointer variable like
tmp, we’ll end up overwriting pointers in the link that we need.
current to point to the current link, the basic flow for each link is this:
tmpto be the pointer
tmpwhich is equal to the address
- Move on to the next link by setting
Steps 2 and 3 are what switch the
prev pointers for each link.
In code, these steps look like:
Now all the function is inserting this code block inside a
while loop so we can iterate through the entire circular list!
Easy peeze when you finally look at it :)