Let’s work on the last requirement for our
LinkedList class, the ability to remove a node from a linked list.
If we can find a node in a linked list, we can remove it by updating the references before and after the removed node. We’ll create a method inside of the
LinkedList class that allows for the removal of a specific node based on position and return its data.
The runtime efficiency of our node removal function should be
Θ(n) since like accessing a specific node, the worst-case scenario would require us to search through the entire chain of nodes,
n, for the node just before the node we want to remove.
Define a new function inside the
LinkedList class, named
removeNode. It should have an argument label of
from, a parameter named
Int type, and return a
You might see an error message in the terminal telling you that your code is
missing return in a function expected to return Node?. As we’ll be working throughout the rest of the exercise to complete this function including fixing this error you can safely ignore it.
The method should either return a
Node instance if there is a node at the given index or
nil if no node exists at that position in the linked list.
Create a variable named
removedNode of optional
Node inside of
removeNode(at:). This variable will be returned at the end of the function with the removed node or
We’ve already established with
append(_:) that the only valid indices are positive numbers or
guard statement inside of
removeNode(from:) that checks if the
index is greater than or equal to
0 and otherwise returns
In the case where the
index passed into
0, there is no need to search through the linked list since a reference to the first node is saved in the variable stored property,
- Write an
ifstatement that checks if
0. If it is, set
- Use optional chaining to update the variable stored property
headto the next node after the current head.
If the head node no longer exists after removal, the linked list is empty and the tail needs to be updated, as well.
Still inside the
if statement checking for
index == 0:
- Add another if statement that checks if head is nil
- If it is, then tail should be set to nil
Finally, with the removed node and both variable stored properties of the linked list updated, you can return the removed node.
- Return the variable
removedNodeoutside and after the
ifstatement that checks if the head is
What if the index is valid and not
0? Then the function should check that there is a node just before the node to remove. To maintain the linked list after removing a node, you’ll need to update the variable stored properties of this previous node.
- Create a
guardstatement that checks if there is a node one index before the node to be removed. Reuse the function
getNode(at:)and store this previous node in a constant named
previous. If there is no previous node, the
guardstatement should return
- On the following new line after your guard statement, set
removedNodeto be the next node after
The next case that the
removeNode(at:) method should be able to handle is when the node to remove does not exist. If there is a previous node but nothing after it, the linked list’s tail property should be updated to reflect this.
On a new line, create an
if statement that uses optional chaining to check if the next node after the previous node is
nil. If the next node is
nil, set the linked list’s tail to be the previous node.
removeNode(from:) has not already returned out of the function with
nil and all the variable stored properties of nodes and the linked list have been updated, the removed node can be returned.
- Maintain the linked list by updating the order of the nodes. On a new line, set the previous node’s next node to be the node after the removed node. Use optional chaining.
- Add a
returnstatement to return the removed node.
It’s time to test out your removal function.
After the code to append to and print
removeNode(from:) to remove the head from
germanCars and save it in a constant named
removedNode. Then print
germanCars again to see how the number and order of nodes in the linked list has changed.