Create a doubly linked list class in Python.

Doubly Linked Lists: Python

Since doubly linked lists have a tail property, we don't have to iterate through the entire list to add to the tail like we did with a singly linked list. The new method will mirror what we did in our `.add_to_head()` method:
- Start by checking to see if there is a current tail to the list
- If there is (meaning the list is not empty), then we want to reset the pointers at the tail of the list:
 - Set the current tail's next node to the new tail
 - Set the new tail's previous node to the current tail
- Update the tail property to be the new tail
- Finally, if there isn't a current head to the list (meaning the list was empty):
 - Update the head property to be the new tail since that node will be both the head and tail 


Adding to the Tail

Now that we've learned about doubly linked lists, let’s implement one in Python. 

As a reminder, a _doubly linked list_ is a sequential chain of nodes, just like a singly linked list. The nodes we used for our _singly_ linked lists contained two elements:
- A value
- A link to the next node    

The difference between a doubly linked list and a singly linked list is that in a doubly linked list, the nodes have pointers to the previous node as well as the next node. This means that the doubly linked list data structure has a tail property in addition to a head property, which allows for traversal in both directions.

So the nodes we will use for our doubly linked list contain three elements:
- A value
- A pointer to the previous node
- A pointer to the next node


Depending on the end-use of the doubly 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 head (beginning) of the list
- Add a new node to the tail (end) of the list
- Remove a node from the head of the list
- Remove a node from the tail of the list
- Find and remove a specific node by its value
- Print out the nodes in the list in order from head to tail


To start, we are going to look at the updated `Node` class and create the constructor.

Ready? Let’s go!

**Note:** We will reuse the `.stringify_list()` method from our `LinkedList` class, but we're going to create the rest of the methods ourselves. 


Node Class and Constructor

You finished your `DoublyLinkedList` class! Now we're going to use that class to model a subway line. A doubly linked list is a great data structure to use to model a subway, as both have a first and last element, and are comprised of nodes (or stops) with links to the elements before and after them.

We will add to and remove stops from our subway line, and print it out to see what we’ve done. The `.stringify_list()` method is the same as the one from the `LinkedList` class and has been provided for you.


Using the List

The doubly linked list's tail property allows us to remove the tail just as easily as we could remove the head. In fact, like with the `.add_to_head()` and `.add_to_tail()` methods, the `.remove_tail()` method will closely mirror the `.remove_head()` method:
- Start by checking if there's a current tail to the list. 
 - If there isn't, The list is empty, so there's nothing to remove, and the method ends 
- Otherwise, update the list's tail to be the current tail's previous node
- If the updated tail is not `None` (meaning the list had more than one element when we started):
 - Set the tail's next node to `None` since there should be no node after the tail of the list
- If the removed tail was also the head of the list (meaning there was only one element in the list):
 - Call `.remove_head()` to make the necessary changes to the head of the list
- Finally, return the old tail's data


Removing the Tail

Now that we've found the node that we want to remove from the list (or returned `None` if it didn't exist), it's time to actually remove the node. This means resetting the pointers around the node. 

There are three cases here:
- The node was the head of the list, in which case we can just call `.remove_head()`
- The node was the tail of the list, in which case we can just call `.remove_tail()`
- The node was somewhere in the middle of the list, in which case we will need to manually change the pointers for its previous and next nodes


Removing by Value II

In addition to removing the head and the tail of the list, it would also be useful to be able to remove a specific element from anywhere in the list. 

Imagine that you have a list of errands to run. You don't always do your errands in order, so when you finish doing your laundry and want to cross it off, that could be somewhere in the middle of the list. We are going to build a `.remove_by_value()` method that will allow you to cross off (remove) that errand no matter where it is in the list.

In order to do this:
- Iterate through the list to find the matching node 
- If there is no matching element in the list:
 - Return `None`
- If there is a matching node, we will then check to see if it is the head or tail of the list: 
 - If so, call the corresponding `.remove_head()` or `.remove_tail()` method 
- If not, that means the node was somewhere in the middle of the list. In that case: 
 - Remove it by resetting the pointers of its previous and next nodes 
- Finally, return the node's value property


Removing by Value I

Due to the added tail property, removing the head of the list in a doubly linked list is a little more complicated than doing so in a singly linked list:
- Start by checking if there's a current head to the list. 
 - If there isn't, the list is empty, so there's nothing to remove and the method ends 
- Otherwise, update the list's head to be the current head's next node
- If the updated head is not `None` (meaning the list had more than one element when we started):
 - Set the head's previous node to `None` since there should be no node before the head of the list
- If the removed head was also the tail of the list (meaning there was only one element in the list):
 - Call `.remove_tail()` to make the necessary changes to the tail of the list (we will create this method in the next exercise!)
- Finally, return the removed head's value


Removing the Head

In a singly linked list, we can add to the head of the list by checking to see if it already has a head. We then either set the new node as the head (if there was no head) or update the head property, and link the past head to the new head.

Since a doubly linked list has an additional tail property and is built with nodes that each have two pointers, there are a few more steps:
- Start by checking to see if there is a current head to the list
- If there is (meaning the list is not empty), then we want to reset the pointers at the head of the list:
 - Set the current head's previous node to the new head
 - Set the new head's next node to the current head
- Update the head property to be the new head
- Finally, if there isn't a current tail to the list (meaning the list was empty):
 - Update the tail property to be the new head since that node will be both the head and tail of the list


Adding to the Head

Congratulations, you have created a doubly linked list class in Python!

We did this by:
- Using our `Node` class to hold the value and links between nodes
- Implementing a `DoublyLinkedList` class to handle external operations on the list, like adding and removing nodes
- Creating an instance of our list, and using the `.stringify_list()` method to track the changes we made
