Implement a Singly-Linked List in Python

Think back on our discussion of the linked list in class, and then read this article in wikipedia about linked lists.

Armed with this knowledge, implement a singly-linked list in Python:

Tasks

Create a GitHub repository, call it data-structures.

Add to the repository a README.md that explains that it will hold sample code for a number of classic data structures implemented in Python. Be sure to include a section of the README.md to list resources or collaborations you used in completing your data structures assignments. Also add an appropriate open source LICENSE (MIT is always a good choice), and a setup.py file. Ensure that setup.py makes it clear that this code base is for a number of data structures, and not just the one that you’re about to build.

When this preliminary work is finished, commit your changes and make a new branch in your repository called linked_list.

Check out your new branch. Add a Python module called linked_list.py.

In that module, write the required Python class(es) to implement a linked list. The list class should be named LinkedList. Your list implementation should support the following methods:

  • push(val) will insert the value ‘val’ at the head 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.
  • size() will return the length of the list
  • search(val) will return the node containing ‘val’ in the list, if present, else None
  • remove(node) will remove the given node from the list, wherever it might be (node must be an item in the list). If the node is not in the list, it should raise an exception with an appropriate message.
  • display() will return a unicode string representing the list as if it were a Python tuple literal: “(12, ‘sam’, 37, ‘tango’)”

In addition to these methods above, your implementation also needs to be able to interact with these built-in Python functions:

  • len(the_list) returns the size of the list
  • print(the_list) returns what the display() method returns

The constructor for your LinkedList class should allow optionally passing an iterable of values. This is the only optional parameter it should take. If an iterable is provided, the result will be a linked list instance containing the values in the iterable. The head of the list should be the last item in the iterable:

LinkedList([1, 2, 3]) => (3)->(2)->(1)

You must not use the Python list or tuple type to solve this problem.

Include pytest unit tests for your linked list class in a file called test_linked_list.py. Use Test Driven Development principles for each method of your class, including the constructor. First implement a test that would verify that the method works. Run pytest to show that it fails, then implement the code needed to make it pass. Be thorough in your testing.

Testing that the general cases of your code work the way that they’re supposed to is a good start, but is not sufficient for the type of comprehensive test suites that I want you to write. Ensure that you cover failure modes and possible edge-cases. The tests you write are as much a part of this assignment as the linked list itself, and without them your code is considered broken and ungradeable.

Submitting Your Work

When you have finished your work and all your tests are passing, create a new Pull Request from your linked_list branch back to your master branch. For your submission, provide a link to that pull request.

Once you have submitted the assignment, you may merge the pull request back to master. I’ll still be able to interact with it properly.