Implement a Doubly-Linked List in Python

Read a bit about the Doubly-Linked List

Tasks

Make a new branch of your data structures repository. Call it dll On that branch implement a doubly-linked list. Your implementation should have the following methods:

  • push(val) will insert the value val at the head of the list
  • append(val) will append the value val at the tail of the list
  • pop() will pop the first value off the head of the list and return it. Raises an exception with an appropriate message if there are no values to return.
  • shift() will remove the last value from the tail of the list and return it. Raises an exception with an appropriate message if there are no values to return.
  • remove(val) will remove the first instance of val found in the list, starting from the head. If val is not present, it will raise an appropriate Python exception.

In addition to these methods above, your implementation also needs to be able to interact with the built-in len() function. It should return the size of the list.

NOTE: this data structure will not take any values on initialization.

Be sure to write tests to cover your new data structure. For each feature of your list, write the test that demonstrates it first, then implement the feature.

Update the README.md to include this new structure. In particular, add a paragraph explaining different use-cases where the singly or doubly-linked list might be more appropriate. It is a requirement that for each method of this data structure, you include in the README a description of its time complexity in Big-O notation! Expect to lose credit if you don’t have this.

Submitting Your Work

When you are done working and all your tests are passing, create a pull request from the dll branch to master. Copy the URL of the pull request and submit that using the URL input. After this is done, you may merge your branch back to master.

As usual, use the comment feature to submit questions, comments and reflections on the work you did for this assignment.