Insight 27.9.1.
In a singly linked list, there is no way to go backwards.
Section 27.9 Remove At an Index
Say we want to remove the third element from our linked list (index 2). Based on the previous section, we might start by making a current pointer that points at the head of the list and then advancing it 2 times.
You would end up in a situation like the one shown below:
Now imagine what needs to happen to successfully remove the node containing 8. We need to delete the node that contains 8. But we also need to change the next pointer in the node containing 15 so that it points to the node containing 12. That way the list remains connected after we delete the 8 node.
But how do we get access to the node containing 15? Our current pointer is pointing at the 8 node, and we have no way to get back to the previous node in the list! Our SimpleLinkedList is what is referred to as a singly linked list - each node only has a pointer to the next node in the list, and no pointer to the previous node.
As with storing the size of the list, adding pointers to previous nodes would make certain operations easier, but it would also add complexity and overhead to every operation that modifies the list. We will explore doing so later. For now, we will stick with a singly linked list and figure out how to work within its limitations.
Although we can’t reach back to access the previous node, it is easy to reach forward. If we advance our current pointer one less time, it will be pointing at the node before the one we want to remove (15 in this list). From there, we can access the node we want to remove (the 8 node) via the next pointer.
So, to add or remove an element at a particular index, we need to stop our current pointer at the node before the one we want to add or remove.
Activity 27.9.1. Linked List Remove At.
The animation has already created a current pointer and advanced it once. Try using
Delete Next to remove the node at index 2 (the node containing 8).
Instructions.
When the
> button is highlighted, an animation is prepared to run. Use the Step button to step through the animation one step at a time.
When no animation is in progress, you can use the data controls to start a new animation.
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.
-
Core Controls.
-
<<: Skip to the beginning of the animation. -
<: Step backwards one step in the animation. -
>: Step forward one step in the animation. -
>>: Skip to the end of the animation. -
Auto Step Speed Set to anything other than off to automatically step through the animation at the selected speed.
-
Zoom Set the zoom level. You can also use Ctrl + Mouse Wheel to zoom in and out.
-
- Data Controls.
In code, this would look something like this:
void SimpleLinkedList<T>::removeAt(int index) {
ListNode<T>* current = head;
// Move current to the node before the desired index
for(int i = 0; i < index - 1; i++) {
current = current->next;
}
ListNode<T>* toDelete = current->next;
current->next = toDelete->next;
delete toDelete;
}
This code assumes that the index is valid. In a real implementation, we would need to add checks for negative indices and indices that are too large. (For the rest of the SimpleLinkedList methods, we will omit bounds checking for simplicity.)
There is another issue to consider for our
removeAt: what if we want to remove the first node (at index 0)?
Our logic assumes we will be modifying the node before the one we want to remove, but there is no node before the first node! The first node is a special case—it is tracked by the head pointer instead of the next pointer of a previous node.
Fortunately, we already have a function
removeStart that handles removing the first node. So, if the index is 0, we can just call removeStart.
void SimpleLinkedList<T>::removeAt(int index) {
if(index == 0) {
removeStart();
return;
}
ListNode<T>* current = head;
// Move current to the node before the desired index
for(int i = 0; i < index - 1; i++) {
current = current->next;
}
ListNode<T>* toDelete = current->next;
current->next = toDelete->next;
delete toDelete;
}
Checkpoint 27.9.1.
Instead of advancing the current pointer index - 1 times, we can use a trailing pointer that is always one node behind the current pointer. Design the logic for this approach.
You have attempted of activities on this page.
