Linked lists are a topic I frequently discuss with students. So for this month’s blog post, I want to present a linked-list practice problem. A problem like this wouldn’t be out of place in a second-term programming course or a first-year data structures course. I actually based it off a question I got back in the first year of my undergrad (CMPUT 115 at the University of Alberta, January-April 2002). I remember the broad strokes of that question after all these years, because it was one of the first problems that made me appreciate how computer science is more than just programming, and that it truly is a science.
Consider a traditional singly-linked list:
- We keep a reference (or pointer) to the head element of the list; and,
- Each element has a reference to the next element, except
- The tail element has a reference to
null.
We can insert elements at the start of this list very quickly, in $\mathcal{O}\left(1\right)$ time. However, inserting a new element at the end of the list requires us to traverse the entire list, taking $\mathcal{O}\left(n\right)$ time (where $n$ is the number of elements in the list).
Now, let’s consider a different singly-linked list structure:
- We keep a reference to the tail element of the list (not to the head); and,
- Each element has a reference to the next element, except
- The tail element has a reference to the head element (not to
NULL).
This structure is called a singly-linked circular list with a tail pointer.
- In pseudocode, describe how you would insert a new element at the start of a singly-linked circular list with a tail pointer.
- In pseudocode, describe how you would insert a new element at the end of this list. Remember that you’ll have to update the overall reference you’re maintaining to the list’s tail.
- In pseudocode, describe how you would find whether a given value is in the list. In particular, how will you know when you’ve searched the entire list, if the list doesn’t contain the value?
If you’re in a programming course:
- Implement a singly-linked circular list with a tail pointer. The list should hold integer data, as in the diagram. You should be able to add a new element to the start of the list, add a new element to the end, and search the list to determine whether or not it contains a given value.
If you’re in a data-structures course:
- What is the runtime, in big-$\mathcal{O}$ notation, for inserting a new element at the start of the list? How about for inserting a new element at the end? And, what is the runtime for searching the list for a given value?
Working together on practice problems like this one can be part of any tutoring session. For more discussions, and to arrange for personalized tutoring for yourself or your study group, check out Vancouver Computer Science Tutoring.