Vectors can access a particular element via its index efficiently because they store their elements in a contiguous block of memory. This allows them to do some simple arithmetic to calculate the address of any element based on its index.
In a linked list however, the elements are scattered throughout memory, so there is no easy way to calculate the address of a particular element based on its position in the list. Thus, in a linked list, accessing an element by index requires traversing the list from the beginning and following next pointers until we reach the desired index.
The animation is set to auto step. Click Make current pointer and let it finish running. You will be pointing at index 0. Then click Advance current and let it run. Then click Advance current again and let it run. You should have a current pointer pointing at index 2 (the 8 node).
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.
To automate this in a retrieveAt function for our linked list, we can use a for loop that advances a current as many times as the desired index. After the loop finishes, our pointer will be pointing at the desired node, and we can return its data.
template <typename T>
T SimpleLinkedList<T>::retrieveAt(int index) const {
ListNode<T>* current = head;
for(int i = 0; i < index; i++) {
current = current->next;
}
return current->data;
}
Note27.8.1.
To make this function behave like the at function in std::vector, we would need to return a reference to the data instead of a copy, allowing for modification of the element directly.
But that would require the function to not be marked as const, since it would be modifying the list. Then, to support using .at() in both const and non-const contexts, we would need to provide two versions of the function: one const and one non-const.
We will avoid that complexity. If decide we there should be a way to change data in a node we could instead provide a separate function specifically for that purpose (something like .setAt(int index, constT& value)).
As long as our retrieveAt function is given a valid index, that logic will be correct. But what if the index is negative? That is clearly invalid. Or, what if the function is given an index that is larger than the number of elements in the list? In that case, the for loop will eventually try to do current = current->next; when current is nullptr, which will cause an error.
To handle those cases, we can add some checks. First, we can check if the index is negative at the start of the function and throw an exception if it is. We also should make sure that the list is not empty. If it is, any index is invalid.Then, inside the for loop, after moving current to the next node, we can check if current is nullptr. If it is, that means the index is out of range, and we can throw an exception in that case as well.
template <typename T>
T SimpleLinkedList<T>::retrieveAt(int index) const {
if (index < 0 || head == nullptr) {
throw std::out_of_range("Index out of range");
}
ListNode<T>* current = head;
for(int i = 0; i < index; i++) {
current = current->next;
if (current == nullptr) {
throw std::out_of_range("Index out of range");
}
}
return current->data;
}
Having to keep checking “did we go too far” (line 9) is a bit clunky. If we knew in advance how many elements were in the list, we could just check the index against that at the start of the function and avoid having to check inside the loop. (We will examine that possibility in a later section.)
Examining this function, we can see that in a list of \(n\) elements, this operation has a worst-case time complexity of \(O(n)\text{.}\) If we call .retrieveAt(n - 1), the loop will repeat \(n - 1\) times. This is much slower than doing the same operation on a std::vector, which has a time complexity of \(O(1)\text{.}\)
For this reason, although we generally like reusing existing logic to implement new functions, we will not want to use .retrieveAt() as a helper for other linked list functions. Imagine we implement a print function like this:
// Inefficient print function using retrieveAt()
template <typename T>
void SimpleLinkedList<T>::print() const {
int listSize = this->listSize();
for (int i = 0; i < listSize; i++) {
cout << this->retrieveAt(i) << " ";
}
cout << endl;
}
A call to .print() will result in an \(O(n^2)\) operation because we have a loop that runs \(n\) times, and each time through the loop we call .retrieveAt(i), which is an \(O(n)\) operation. Instead, we want to implement any functions that need to visit each element in the list by traversing the nodes directly, without using .retrieveAt().
void LinkedList<T>::printRange(int a, int b) const { #tag:b; depends:;
---
ListNode<T>* current = head; #tag:c; depends:b;
---
int i = 0; #tag:d; depends:b;
---
while (i < a) { #tag:e; depends:c,d;
---
current = current->next; // advance in a loop
i++; #tag:f; depends:e;
---
} // end of a loop #tag:g; depends:e;
---
while (i <= b) { #tag:i; depends:g;
---
cout << current->data << " "; #tag:j; depends:i;
---
current = current->next; // advance in b loop
i++; #tag:k; depends:j;
---
} // end of b loop #tag:l; depends:i;
---
cout << endl; #tag:n; depends:l;
---
} #tag:o; depends:n;
