A linked list implementation by John Keyes.
The simplest way is to clone the repository from GitHub:
git clone https://github.com/jkeyes/amzlist.git
Or you can download the repository in a ZIP file.
You can prepend items to a linked list, which adds each new Node as the head of the list:
from amzlist import LinkedList
lnkd_list = LinkedList()
lnkd_list.prepend("amazon.com")
lnkd_list.prepend("@")
lnkd_list.prepend("jkeyes")
You can also append. Note this is much slower as we must traverse the entire list to find where to insert the node:
lnkd_list.append("Why would you use append?")
It’s also possible to insert a node after another node:
from amzlist import Node
n_color = Node("Red")
n_answer = Node(42)
lnkd_list.prepend(n_color)
lnkd_list.insert(n_answer, n_color) # insert n_answer after n_color
To remove a node the remove method can be used:
lnkd_list.remove("Red")
Alternatively you can use push and pop to add and remove nodes from the list:
lnkd_list.push("Item 1")
lnkd_list.push("Item 2")
node = lnkd_list.pop()
node.data == "Item 2"
There are two methods to reverse the list, one uses an iterative approach and the other a recursive one:
rvsd_list = lnkd_list.reverse_iterative()
rvsd_list = lnkd_list.reverse_recursive()
If the LinkedList methods are used no cycles can be introduced. However, it is possible to introduct a cycle by directly manipulating the nodes:
lnkd_list = LinkedList()
node_john = Node('John')
lnkd_list.prepend(node_john)
node_james = Node('James')
lnkd_list.prepend(node_james)
node_joe = Node('Joe')
lnkd_list.prepend(node_joe)
# introduce a cycle
# Joe->James->John->Jules->John
node_jules = Node('Jules')
node_john.next = node_jules
node_jules.next = node_john
To prevent this you can create a strict LinkedList.
lnkd_list = LinkedList(strict=True)
...
node_jules.next = node_john
# Raises ValueError
WARNING: this is an EXTREMELY costly feature, as it requires traversal of the list for each Node that is added to the List (if the node being added has a value for next).
To run the testsuite you’ll need to setup the environment first:
cd amzlist
virtualenv venv
source venv/bin/activate
pip install -r requirements.txt
Then you can run the testsuite:
nosetests tests
You can also get a coverage report:
nosetests tests --with-coverage --cover-package amzlist
Browse the API Documentation.
If you want to generate the documentation use the following commands:
cd docs
make html # docs will be generated in _build/html