We have already identified some improvements that could be made to our SimpleLinkedList class. One simple addition we mentioned would be to add a size variable that keeps track of how many elements are in the list.
Adding a size variable would provide a few benefits. Currently, to find the size of the list, we would need to loop through all the nodes and count them. (This would take \(O(n)\) time.) If we kept a size variable updated as we add and remove elements, we could return the size in constant time, \(O(1)\text{.}\)
Once getting the size is cheap, we can use it to simplify the implementation of other methods by using it to do bounds checking before we start traversing the list. All of our traversal functions currently have to keep checking if they have hit a nullptr as they walk through the list. Instead, we can check the index against the size at the start of the function and throw an exception if it is out of bounds.
template<typename T>
T LinkedList<T>::retrieveAt(int index) const {
if (index < 0 || index >= size)
throw out_of_range("Bad index in retrieveAt");
ListNode<T>* current = head;
for (int i = 0; i < index; i++) {
current = current->next;
// No need to check for nullptr here
}
return current->data;
}
This does not come for free. Maintaining the size variable will add a slight amount of complexity to our code. We will need to remember to update the size variable whenever we add or remove an element.
void LinkedList<T>::insertStart(const T& value) {
// Do work to insert new node at start of list...
size++; //update size variable
}
void LinkedList<T>::removeAt(int index) {
//Do work to remove node at index...
size--; //update size variable
}
Insight27.11.1.
Usually we want to avoid storing the same data more than once. We already implicitly are storing the size of the list by the number of nodes it contains, so adding a size variable is a form of data duplication.
But, the small amount of extra record keeping involved with the size variable seems like a reasonable trade-off for the performance benefits it provides for a critical operation like getting the size of the list.
Another issue we have not addressed yet is working at the end of the list. Currently, if we want to add an element to the end of the list, we have to start at the head and walk through all the nodes until we reach the end. This takes \(O(n)\) time. If we kept a pointer to the tail node of the list, we could add elements to the end in constant time, \(O(1)\text{.}\)
Activity27.11.1.Singly Linked List with Tail Pointer.
This version of the linked list keeps track of the size of the list and a tail pointer to the last node in the list. It has started to insert 20 at the end of the list. Use > to step through the process.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
Now, adding an element to the end of the list only takes a few steps, regardless of how long the list is. We do have to worry about one special case - inserting into an empty list. In that case, the new node is both the head and the tail of the list.
void LinkedList<T>::insertEnd(T value) {
if (size == 0) {
// add a node and set both head and tail to point to it
} else {
// make the new node
// update the next pointer of the current tail to point to the new node
// update the list's tail pointer to point to the new node
}
size++;
}
As with size, maintaining a tail pointer will result in some extra complexity in our code. We will need to make sure to update the tail pointer whenever we add or remove elements from the end of the list. Here are some new special cases we will need to handle:
When inserting into an empty list insertStart needs to set both the head and tail pointers to point to the new node.
void LinkedList<T>::insertStart(const T& value) {
// ... do the insertion ...
// if list was empty, new node is also tail
if (size == 0)
tail = head;
size++;
}
...
void LinkedList<T>::removeAt(int index) {
// ... Make current point to the node before the one we are deleting ...
// ... do the removal ...
// Is there nothing left after current node? Then it is the new tail
if (current->next == nullptr)
tail = current;
size--;
}
Although this allows us to efficiently insert at the end of the list, we still can’t efficiently remove an element from the end of the list. To remove the last element, we need to set the tail pointer to the second-to-last node and set the next pointer of that node to nullptr. But we have no way to reach the second-to-last node without starting at the head and walking through the list.
