Learn

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

1.

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.

2.

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.

3.

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.

4.

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 if index is 0. If it is, set removedNode to head.
  • Use optional chaining to update the variable stored property head to the next node after the current head.
5.

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 the if statement that checks if the head is nil.
6.

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 function getNode(at:) and store this previous node in a constant named previous. If there is no previous node, the guard statement should return nil.
  • On the following new line after your guard statement, set removedNode to be the next node after previous.
7.

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.

8.

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.
9.

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.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?