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.
Instructions
Define a new function inside the LinkedList
class, named removeNode
. It should have an argument label of from
, a parameter named index
of Int
type, and return a Node
optional.
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 nil
.
We’ve already established with append(_:)
that the only valid indices are positive numbers or 0
.
Create a guard
statement inside of removeNode(from:)
that checks if the index
is greater than or equal to 0
and otherwise returns nil
.
In the case where the index
passed into removeNode(from:)
is 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, head
.
- Write an
if
statement that checks ifindex
is0
. If it is, setremovedNode
tohead
. - Use optional chaining to update the variable stored property
head
to 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
removedNode
outside and after theif
statement that checks if the head isnil
.
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
guard
statement that checks if there is a node one index before the node to be removed. Reuse the functiongetNode(at:)
and store this previous node in a constant namedprevious
. If there is no previous node, theguard
statement should returnnil
. - On the following new line after your guard statement, set
removedNode
to be the next node afterprevious
.
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.
Finally, if 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
return
statement to return the removed node.
It’s time to test out your removal function.
After the code to append to and print germanCars
, use 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.