Linked Lists: Swift

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.

Removing a Specific Node 

Currently, we don't have an easy way of printing a linked list in a format that tells us about the nodes or data stored in them. 

For example, printing the linked list that stores the plants in a greenhouse in the code snippet below results in the text `Node.LinkedList` being output in the terminal. 

```swift
let greenhouse = LinkedList()
greenhouse.append("Bamboo")
greenhouse.append("Golden Pothos")
greenhouse.append("Snake Plant")
print(greenhouse)  // Prints Node.LinkedList 
```

To test the `append(:_)` method we created, let's create an extension to the `LinkedList` class using the `CustomStringConvertible` protocol. This extension will convert a linked list to a formatted `String` whenever the `print(_:separator:terminator:)` function is used.

The new `LinkedList` extension should do the following:

1. Format the data stored in each node from head to tail

2. Indicate the direction of the linked list by joining the data of each node with an arrow ` -> ` and spaces

3. Return the text `nil` when the linked list is empty

Let's get printing!

Printing All the Nodes in a List

Let’s implement a linked list in Swift. As you might recall, a linked list is a sequential chain of nodes. 

Remember that a node contains data and a link to the next node.

We are going to use the `Node` class you created in the last lesson. The code for the class `Node` can be found in the code editor of each exercise.

Depending on the end-use of the linked list, there are a variety of methods that we can define. For our use, we want to be able to:

- add a new node to the end (tail) of the list
- print out the nodes in the list in order from head to tail
- retrieve a node according to its position
remove a node from the list according to its position

Ready? Let’s get started!


Introduction: Linked Lists in Swift 

We now have a linked list class! But any linked list we create is empty and stays that way, which isn't very useful. 

In this exercise, we'll give `LinkedList` instances the ability to add nodes by making use of the previously defined `Node` class. 

We'll create a `LinkedList` instance method that will hold the code needed to store data in a node and update the variable stored properties of the linked list as well as the nodes in it.

The runtime efficiency of our append function should be constant, or `Θ(1)`. Since we are adding nodes to the `tail`, which we always have a reference to, the runtime is the same for all linked lists, no matter how many nodes are in them.


Appending a Node

Let's add some more functionality to our `LinkedList` class. If we can retrieve all the nodes from a linked list, we should also be able to access a specific node depending on its position. 

Just like appending to a linked list, we'll create a new method to find and return the data of a node at a specific index. This function should have a runtime efficiency of `Θ(n)` since the worst-case scenario would be to search through the entire length of the chain of nodes, `n`, for a node.